郁郁青青 长过千寻

尼姆博弈

    博弈论
  1. NIMM(m)
  • 阶梯博弈
    1. STAIRCASENIMM(m)

    NIMM(m)

    1
    2
    3
    4
    5
    6
    7
    8
    初始化p数组，其中代表m堆石子，第i堆石子里有p[i]颗石子
    初始化sum=0，res=0
    for i=0 to m
       sum^=p[i]
    for i=0 to m
       if p[i]>(sum^p[i])
          res=res+1
    return res

    阶梯博弈

    STAIRCASENIMM(m)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    初始化p数组，其中代表m颗棋子，第i颗棋子在第p[i]位置
    初始化sum=0
    if m为奇数
       p[m]=0
    SORT(p)
    for i=1 to m step=2
       sum^=(p[i]-p[i-1]-1)
    if sum==0
       print "Z will win"
    else print "G will win"
    • 页阅读量:  ・  站访问量:  ・  站访客数: