NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 26 题

#include<iostream>
using namespace std;
const int NUM=5;
int r(int n)
{
    int i;
    if(n<=NUM)
       return 0;
    for(i=1;i<=NUM;i++)
       if( r(n-i)<0)
          return i;
    return -1;
}

int main()
{
    int n;
    cin>>n;
    cout<<r(n)<<endl;
    return 0;
}

输入： 16 输出：______________

博弈题：找最小必胜走法，r(16)=4 表示取 4 个能赢。

递归函数判断对手是否处于必败局面；当前局面有必败后继则必胜。

程序阅读——博弈递归

函数r(n)：

• 如果n≤5，返回0（必败）
• 尝试取1~5个，如果r(n-i)<0（对手必败），则返回i（当前必胜）
• 如果所有选择对手都必胜，返回-1（当前必败）

n=16： r(15)→取1→r(14)→取1→...→r(10)→取1→r(9)→取1→r(8)→取1→r(7)→取1→r(6)→取1→r(5)=0

实际上：r(6)时取1后r(5)=0，所以r(6)=1 r(7)取2后r(5)=0，r(7)=2 ... 当n=16时，取4后r(12)=...追踪可得r(16)=4

输出：4