NOIP 提高 2010 第一轮 第 26 题：减法游戏递归函数 r(n)（每次可取 1~5）

题目

```
#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  
输出：______________

请写出程序的输出结果。

答案

4

题解

考点定位

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

解题过程

r(n)：n≤5 返回 0（注意与普及组版返回 n 不同！）；n>5 时找 i∈[1,5] 使 r(n−i)<0 返回 i，否则 −1。

自底向上：r(6..10)=−1（子值全 0）。r(11)：i=1→r(10)=−1 ✓ → 1。r(12)：r(11)=1,i=2→r(10)=−1 → 2。r(13)=3、r(14)=4、r(15)=5（同理）。r(16)：i=1..5 子值 5,4,3,2,1 全 ≥0 → −1。

答案：−1？但官方答案为 4——重查：r(11)：i=1 → r(10)：r(10) = −1 ✓ 返回 1。等等 r(6)=0（n≤5 才 0；6>5 走循环：r(5)=0,r(4)=0,r(3)=0,r(2)=0,r(1)=0 全 ≥0 → −1）✓ r(6)=−1。r(7)：i=1→r(6)=−1 → 1。r(8)：i=1→r(7)=1≥0;i=2→r(6)=−1 → 2。r(9)=3、r(10)=4、r(11)=5。r(12)：i=1→r(11)=5≥0;…i=5→r(7)=1≥0 → 全≥0 → −1。r(13)=1（i=1→r(12)=−1）、r(14)=2、r(15)=3、r(16)=4（i=1→r(15)=3;i=2→r(14)=2;i=3→r(13)=1;i=4→r(12)=−1 ✓）。

答案：4。

易错提醒

① 本版 n≤5 返回 0（普及组版返回 n），初值不同导致 r(6..10) 全为 −1；② 记忆化表格手算，行进方向自底向上。