递推关系式的推导与求解

掌握递推关系式的推导以及递推问题求解。

递推关系式描述「第 n 项（或第 n 个状态）如何由更小的 n 表示」。解题步骤通常是：找状态含义 → 写关系式 → 确定初值 → 循环或数组计算到目标 n。有时可化简为只保留前一两项，节省空间。

四级卷面常给生活情境（格子、传球、涂色），要求写出关系或求第 k 项。手推前几项核对关系是否自洽；关系写对后，实现多为 for 循环，注意数组下标与题意是否从 0 或 1 开始。

// 每步可 +1 或 +2，到 n 的方案数
int dp[20];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= 10; ++i)
    dp[i] = dp[i-1] + dp[i-2];
cout << dp[10];

关系式不必一次写完美；用 n=1,2,3 的小例子验证，再推广到一般 n。

某算法的递推关系式为 $T(n) = T(n-1) + n$ （ $n$ 为正整数）及 $T(0) = 1$ ，则该算法的时间复杂度为 $O(n^2)$ 。

√（正确）

×（错误）

编程题

Recamán

C++时间 1 s内存 512 MB标准输入输出

小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的：

数列的第一项 $a_1$ 是 $1$ ；
如果 $a_{k-1}-k$ 是正整数并且没有在数列中出现过，那么数列的第 $k$ 项 $a_k$ 为 $a_{k-1}-k$ ，否则为 $a_{k-1}+k$ 。

小杨想知道 Recamán 数列的前 $n$ 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。

输入格式

第一行，一个正整数 $n$ 。

输出格式

一行， $n$ 个空格分隔的整数，表示 Recamán 数列的前 $n$ 项从小到大排序后的结果。

样例

输入 1

输出 1

1 2 3 6 7

样例解释

对于样例 1， $n=5$ ：

$a_1=1$ ；
$a_1-2=-1$ ，不是正整数，因此 $a_2=a_1+2=3$ ；
$a_2-3=0$ ，不是正整数，因此 $a_3=a_2+3=6$ ；
$a_3-4=2$ ，是正整数，且没有在数列中出现过，因此 $a_4=a_3-4=2$ ；
$a_4-5=-3$ ，不是正整数，因此 $a_5=a_4+5=7$ 。

$a_1,a_2,a_3,a_4,a_5$ 从小到大排序的结果为 $1,2,3,6,7$ 。

输入 2

输出 2

1 2 3 6 7 12 13 20

数据范围

对于所有数据点，保证 $1\le n\le 3\, 000$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

小杨正在爬楼梯，需要爬 $n$ 阶才能到达楼顶。如果每次可以爬 $1$ 个或 $2$ 个台阶，下面代码采用递推算法来计算一共有多少种不同的方法可以爬到楼顶，则横线上应填写（）。

int f(int n) {
    if (n == 1 || n == 2)
        return n;

    int f1 = 1;
    int f2 = 2;
    int res = 0;
    for (int i = 3; i <= n; i++) {
        ________________________________     // 在此处填入代码
    }
    return res;
}

res += f1 + f2;
f1 = f2;
f2 = res;

res = f1 + f2;
f1 = f2;
f2 = res;

res += f1 + f2;
f2 = res;
f1 = f2;

res = f1 + f2;
f2 = res;
f1 = f2;

考虑最坏情况下冒泡排序算法的时间复杂度，$ T(n) $ 为待排序数字的数目为 $ n $ 的复杂度，则其递推关系式为 $ T(n) = T(n - 1) + n $，$ T(0) = 1 $。

√（正确）

×（错误）

小杨正在爬楼梯，需要 $n$ 阶才能到达楼顶，每次可以爬 $1$ 阶或 $2$ 阶，求小杨有多少种不同的方法可以爬到楼顶，横线上应填写（）。

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1;
    int prev1 = 2;
    int current = 0;
    for (int i = 3; i <= n; ++i) {
        ________________    // 在此处填入代码
    }
    return current;
}

prev2 = prev1;
prev1 = current;
current = prev1 + prev2;

current = prev1 + prev2;
prev2 = prev1;
prev1 = current;

current = prev1 + prev2;
prev1 = current;
prev2 = prev1;

prev1 = current;
prev2 = prev1;
current = prev1 + prev2;

考虑用如下递推方式计算斐波那契数列，时间复杂度是 $O(n)$ 。

int n = 10;
int f[20];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++)
    f[i] = f[i - 1] + f[i - 2];

√（正确）

×（错误）

执行 climb(6) 的返回值为（）。

int climb(int n){
    if(n <= 2) return n;
    int a = 1, b = 2, c = 0;
    for(int i = 3; i <= n; i++){
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

$8$

$13$

$5$

$10$

小杨的机器人正在能量踏板上跳跃，踏板编号为 $1,2,\ldots,n$ 。跳到第 $n$ 块踏板的方案数满足递推式 $f(n)=f(n-1)+f(n-2)$ 。若 $f(1)=1$ ， $f(2)=2$ ，则运行以下代码计算 jump(5) 的结果是（）。

int jump(int n) {
    if (n <= 2)
        return n;
    int a = 1, b = 2, c = 0;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

$5$

$8$

$13$

$21$