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³。

算法思路

这道题可以使用深度优先搜索（DFS）来解决。我们可以从数字 n 开始，递归地尝试加入下一个数字。在每次尝试加入数字时，需要判断该数字是否超过当前数列最后一项的一半。如果超过，则放弃该尝试；否则，继续递归搜索。

代码实现

#include <iostream>
using namespace std;
int n, cnt;
void dfs(int x, int last) {//x表示当前数列的长度，last表示上一个加入的数字
    if (x > n) {//如果当前长度超过了n，那么直接返回
        return;
    }
    cnt++;//合法的数列个数加1
    for (int i = last; i <= n / 2; i++) {//从last到n/2枚举下一个加入的数字
        dfs(x + 1, i);//x+1表示加入一个数字后的长度，i表示加入的数字
    }
}
int main() {
    cin >> n;
    dfs(1, 1);//从1开始加入数字
    cout << cnt << endl;//输出合法的数列个数
    return 0;
}

总结

本题的解法体现了深度优先搜索在解决组合问题时的优势。通过递归地枚举所有可能的方案，可以得到最终的答案。在实际编程时，需要仔细考虑边界条件和剪枝策略，以提高程序效率。