C语言 现有21根火柴 两个轮流取 一种解法：小学生奥数题：9根火柴棒 两个人轮流取

设r为桌上剩下的火柴棒数量(开始时奇数，中间可以是偶数)，当前轮到某个人取火柴，h为他手上的火柴棒，0表示偶数，1表示奇数，y为他的最终的火柴棒数量，0表示偶数，1表示奇数，定义函数f(r,h)，如果此人最终能够获得偶数根火柴棒则f(r,h)的值为0，否则为1。

容易得到：

桌上r=1根，手上h根，取1根，因此f(1,h)=1+h；

桌上r=2根，手上h根，如果h为0，则取2根，否则取1根(最后一根留给对手)，因此f(2,h)=0；

桌上r=3根，手上h根，如果h为0，则取2根(最后一根留给对手)，否则取3根，因此f(3,h)=0；；

一般地，对于r>=4，如果取k根，1<=k<=3，则轮到对手从r-k根火柴棒中取1~3根火柴，由于火柴棒总数是奇数，因此此时对手手上的火柴棒奇偶状况是(1+r+h)，则对手的f值为f(r-k,1+r+h)，自己的f值则为1+f(r-k,1+r+h)，只要k=1,2,3中有一个1+f(r-k,1+r+h)为偶数，那么f(r,h)就是偶数，因此：

f(r,h) = (1+ f(r-1,1+r+h))*( 1+ f(r-2,1+r+h))*(

1+f(r-3,1+r+h))，对于任意r>3；

特别地，

f(2n,h) = (1+f(2n-1,1+h))*( 1+f(2n-2,1+h))*(

1+f(2n-3,1+h))，对于任意n>1；

f(2n+1,h) = (1+f(2n,h))*( 1+f(2n-1,h))*(

1+f(2n-2,h))，对于任意n>1；

由此可以得到：

f(4,h) = (1+ f(3,1+h))*( 1+f(2,1+h))*( 1+f(1,1+h)) =

(1+0)*(1+0)*(1+1+1+h) = 1+h;

f(5,h) = (1+f(4,h))*(1+f(3,h))*(1+f(2,h)) = (1+1+h)*(1+0)*(1+0)

= h;

f(6,h) = (1+ f(5,1+h))*( 1+ f(4,1+h))*( 1+ f(3,1+h)) =

(1+1+h)*(1+1+1+h)*(1+0) = h(1+h) = 0;

f(7,h) = (1+f(6,h))*(1+f(5,h))*(1+f(4,h)) = (1+0)*(1+h)*(1+1+h)

= h*(h+1) = 0;

f(8,h) = (1+ f(7,1+h))*( 1+ f(6,1+h))*( 1+ f(5,1+h)) =

(1+0)*(1+0)*(1+1+h) = h;

f(9,h) = (1+f(8,h))*(1+f(7,h))*(1+f(6,h)) = (1+h)*(1+0)*(1+0) =

1+h;

......

如果开始时桌上有9跟火柴，那么对于先取火柴的人，f(9,0)=1，因此先取火柴的人最终得到的火柴总数是奇数(假设对方不犯错误)。

事实上，可以有如下的公式：对于任意n>=1，

f(8n+1) = 1+h;

f(8n+2) = 0;

f(8n+3) = 0;

f(8n+4) = 1+h;

f(8n+5) = h;

f(8n+6) = 0;

f(8n+7) = 0;

f(8n+8) = h;

上述公式可以用数学归纳法证明：

n=1时上述公式成立，假设n时公式成立，现在要证明对n+1公式成立：

f(8(n+1)+1,h) = (1+f(8n+8,h))*(1+f(8n+7,h))*(1+f(8n+6,h)) =

(1+h)*(1+0)*(1+0) = (1+h)*1*1;

f(8(n+1)+2,h) =

(1+f(8(n+1)+1,1+h))*(1+f(8(n+1),1+h))*(1+f(8n+7,1+h)) =

(1+1+1+h)*(1+1+h)*(1+0) = (1+h)h*1 = 0;

f(8(n+1)+3,h) =

(1+f(8(n+1)+2,h))*(1+f(8(n+1)+1,h))*(1+f(8(n+1),h)) =

(1+0)*(1+1+h)*(1+h) = 1*h(1+h) = 0; (因为h和h+1中必有一个是偶数)

f(8(n+1)+4,h) = (1+ f(8(n+1)+3,1+h))*( 1+ f(8(n+1)+2,1+h))*( 1+

f(8(n+1)+1,1+h)) = (1+0)*(1+0)*(1+1+1+h) = 1*1*(1+h) = 1+h;

f(8(n+1)+5,h) =

(1+f(8(n+1)+4,h))*(1+f(8(n+1)+3,h))*(1+f(8(n+1)+2,h)) =

(1+1+h)*(1+0)*(1+0) = h*1*1 = h;

f(8(n+1)+6,h) =

(1+f(8(n+1)+5,1+h))*(1+f(8(n+1)+4,1+h))*(1+f(8(n+1)+3,1+h)) =

(1+1+h)*(1+1+1+h)*(1+0) = h(1+h)*1 = 0;

f(8(n+1)+7,h) =

(1+f(8(n+1)+6,h))*(1+f(8(n+1)+5,h))*(1+f(8(n+1)+4,h)) =

(1+0)*(1+h)*(1+1+h) = 1*(1+h)*h = 0;

f(8(n+1)+8,h) =

(1+f(8(n+1)+7,1+h))*(1+f(8(n+1)+6,1+h))*(1+f(8(n+1)+5,1+h)) =

(1+0)*(1+0)*(1+1+h) = h;

也就是说，如果开始时桌上是奇数根火柴，假如是8n+1(9,17,25…)，那么先取火柴的人最终得到的火柴棒总数是奇数(假设对手不犯错误)，其他情况(8n+3,8n+5,8n+7)下，先取火柴的人最终得到的火柴棒总数是偶数。

另外，上述公式其实也提供了制胜或最优的取法，例如，假设到某一步轮到你取火柴，你手上有h根火柴，桌上剩下r根火柴，那么你应该取几根火柴？假设r=8n+6，根据上述公式：

f(8(n+1)+6,h) =

(1+f(8(n+1)+5,1+h))*(1+f(8(n+1)+4,1+h))*(1+f(8(n+1)+3,1+h)) =

(1+1+h)*(1+1+1+h)*(1+0) = h(1+h)*1 = 0;

此次取3根火柴的结果是(1+f(8(n+1)+3,1+h))=1，因此不是正确的取法，如果手上的火柴数h是偶数，那么取1根火柴，否则取2根火柴。r为其他数的话，以此类推。

C语言 现有21根火柴 两个轮流取 一种解法：小学生奥数题：9根火柴棒 两个人轮流取 每次只能取1 2或3根 取完为止 总数为偶数者为胜...