NOIP2001 普及组 - 数的计算：递归求解合法数列个数

题目描述

给出自然数 'n'，要求按如下方式构造数列：

1. 只有一个数字 'n' 的数列是一个合法的数列。
2. 在一个合法的数列的末尾加入一个自然数，但是这个自然数不能超过该数列最后一项的一半，可以得到一个新的合法数列。

请你求出，一共有多少个合法的数列。两个合法数列 'a', 'b' 不同当且仅当两数列长度不同或存在一个正整数 'i' ≤ '|a|'，使得 'a_i' ≠ 'b_i'。

输入格式

输入只有一行一个整数，表示 'n'。

输出格式

输出一行一个整数，表示合法的数列个数。

样例 #1

样例输入 #1

6

样例输出 #1

6

提示

样例 1 解释

满足条件的数列为：

• '6'
• '6, 1'
• '6, 2'
• '6, 3'
• '6, 2, 1'
• '6, 3, 1'

数据规模与约定

对于全部的测试点，保证 '1' ≤ 'n' ≤ '10³'。

代码实现 (C++)

#include <iostream>

using namespace std;

int n;
int ans;//记录答案

void dfs(int sum, int last) {

    if (sum == n) {
        ans++;
        return;
    }

    for (int i = last; i <= n - sum; i++) {//从 last 到 n - sum 只需要枚举到 n - sum 就行了
        dfs(sum + i, i);
    }
}

int main() {

    cin >> n;
    dfs(0, 1);//初始和为 0，最小可选数为 1

    cout << ans << endl;

    return 0;
}

解题思路

使用递归的方式来解决问题。

1. 定义递归函数 dfs(sum, last)
   • 参数 sum 表示当前数列的元素和
   • 参数 last 表示当前数列的最后一个元素
2. 递归终止条件： 当 sum 等于 'n' 时，表示找到一个合法的数列，答案加一。
3. 递归过程： 循环枚举下一个元素 'i'，满足 'i' 不超过 'last' 的一半。
4. 递归调用： 递归调用 dfs(sum + i, i)，继续构造下一个元素。

代码分析

• ans 变量： 用于记录合法数列的个数。
• dfs(0, 1)： 初始化递归调用，初始和为 0，最小可选数为 1。
• for 循环： 枚举下一个元素 'i'，从 'last' 开始枚举，直到 'n - sum'。
• dfs(sum + i, i)： 递归调用，将当前元素 'i' 加入数列，并继续构造下一个元素。

总结

本题使用递归的方式，通过不断枚举下一个元素，最终计算出所有合法数列的个数。代码清晰简洁，易于理解。递归是一种常用的算法技巧，能够有效解决许多问题，例如树的遍历、迷宫问题等等。