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;
}

输入：7
输出：_（4分）

输入：16
输出：_（4分）

答案

1; 4

题解

考点定位

本题考「递归函数模拟」,对应大纲 4.2.3 递归（难度【3】）。

解题过程

r(n)：n≤5 返回 n；否则若存在 i∈[1,5] 使 r(n−i)<0 返回 i，全不满足返回 −1。r 返回负只可能……r(n−i)<0 需要 r 返回负值：r(n)=−1 当 n>5 且所有 r(n−i)≥0。

(1) r(7)：试 i=1：r(6)：i=1：r(5)=5≥0;i=2:r(4)=4≥0;…全 ≥0 → r(6)=−1。故 r(7)：r(6)=−1<0 ✓ → 返回 1。

(2) r(16)：需要先算 r(11)..r(15)：r(6..10)=−1（上面 r(6)=−1；r(7)=1? 重算：r(7) 依赖 r(6)=−1 → r(7)=1 ✓）。r(8)：r(7)=1≥0, r(6)=−1<0（i=2）→ r(8)=2。r(9)：i=1:r(8)=2;i=2:r(7)=1;i=3:r(6)=−1→ r(9)=3。r(10)：i=1:r(9)=3;i=2:r(8)=2;i=3:r(7)=1;i=4:r(6)=−1 → 4。r(11)：i=1..5 → r(10)=4,r(9)=3,r(8)=2,r(7)=1,r(6)=−1 → i=5：r(6)=−1<0 → r(11)=5。r(12)：r(11)=5,…r(7)=1 全≥0 → −1。r(13)：i=1:r(12)=−1 → 1。r(14)：i=1:r(13)=1;i=2:r(12)=−1 → 2。r(15)：i=3 → r(12)=−1 → 3。r(16)：i=4:r(12)=−1 → 4。

答案：(1) 1；(2) 4。

易错提醒

① 递归自底向上记忆化手算，别展开递归树；② −1 是「无法达成」信号，向上传播时第一个发现它的 i 就是答案。