NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 26 题

阅读程序写结果：

#include <iostream>
using namespace std;

const int NUM = 5;

int r(int n)
{
    int i;
    if (n <= NUM)
        return n;
    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;
}

（1） 输入：7 输出：_________（4分）

（2） 输入：16 输出：_________（4分）

这题表面是递归，实则是博弈论里的‘必胜/必败态’判断。拿到题先想：r(n-i)<0代表什么？代表对手必败，那当前玩家就能赢，直接返回i。所以核心就是顺着递归把每个n标记成‘必胜（正数）’还是‘必败（-1）’，再按题目给的n填数。

最容易掉进两个坑：一是只盯着r(n-i)的返回值大小，忘了-1才是必败态，看到r(n-i)是正数就以为对方还能赢，从而漏掉返回i的机会；二是把r(7)算成-1，因为误以为r(6)到r(2)全是正数，没意识到r(6)本身会触发r(5-i)<0的条件，导致r(6)=-1，进而让r(7)正确返回1。另外，r(16)的递归层数多，手算容易漏掉某一层，导致把必胜步数算错，比如算成1或2而不是4。

递归分析

核心概念与命题视角

函数r(n)是典型的博弈论模型：面对一堆n个物品，每次最多取NUM（5个）。如果存在一种取法i（1≤i≤5），使得取完后对手面对的状态r(n-i)是必败态（即返回-1），那么当前玩家就能赢，直接返回i；否则无论怎么取，对手都能赢，函数返回-1。

命题人挖坑点： 1. 返回值含义：正数代表必胜且第一步应取的数量，-1代表必败。很多学生看到r(n-i)<0就只想到“输”，忽略了此时应该返回i。 2. 递归层数：r(16)需要反复调用，容易在手动推演时漏掉某一层，导致错误判断。 3. 边界处理：n≤NUM时直接返回n，这是必胜态，因为可以一次全取完。