实验1-2

实验1-2

如题：

思路：

使用动态规划的思想（DP思路，即一个大一点规模的问题可以被拆解为更小的，更容易解决的问题）

首先，定义一个数组 dp，用来存储每个数的分解式个数。 dp[i] 表示当前数 i 的不同分解式的个数。

接下来，从数 2 开始循环，逐个计算每个数的分解式个数。dp[i] = 0，防止数组越界。

然后，通过枚举当前数的所有因子来计算分解式个数。使用一个内部循环，从因子

j = 1 开始，一直到 i/2（因为因子的最大可能值是 i/2）。对于每个因子 j，计算

i % j == 0。如果是整除关系，说明 j 是 i 的一个因子。

在这种情况下，我们根据递推公式 dp[i] += dp[j] 来计算当前数的分解式个数。dp[j] 表示之前计算的拥有因子 j 的数的分解式个数。

根据递推公式，我们将之前计算的结果 dp[j] 累加到 dp[i] 上。这样就实现了动态规划的思想，利用已知的结果计算新的结果。

最后，循环结束后，返回数组 dp[n] 的值，即正整数 n 的不同分解式的个数。

代码：

以n=12，

第十一次循环（i = 12）：

• dp[12] = 0
• 内层循环（j = 1）：12 % 1 == 0，所以 dp[12] += dp[1] = 0 + 1 = 1
• 内层循环（j = 2）：12 % 2 == 0，所以 dp[12] += dp[2] = 1 + 1 = 2
• 内层循环（j = 3）：12 % 3 == 0，所以 dp[12] += dp[3] = 2 + 1 = 3
• 内层循环（j = 4）：12 % 4 == 0，所以 dp[12] += dp[4] = 3 + 2 = 5
• 内层循环（j = 5）：12 % 5 != 0，跳过
• 内层循环（j = 6）：12 % 6 == 0，所以 dp[12] += dp[6] = 5 + 3 = 8
• 内层循环完毕
• dp[12] = 8

#include<stdio.h>int countSum(int n){int dp[n+1]; //存储每个数的分解式个数dp[1] = 1;  // 输入 1 的时候为 1for(int i = 2; i <= n; i++){dp[i] = 0;  //用 dp[j] 计算 dp[i]for(int j = 1; j <= i/2; j++){ //因子的最大可能值是 i/2, 题目意思防止 1*12，,12*1if(i % j == 0){           //整除关系，说明 j 是 i 的一个因子//dp[i] 则是待计算的当前数 i 的分解式个数, dp[j] 表示之前计算的拥有因子 j 的数的分解式个数dp[i] += dp[j];      //一个数的分解式个数等于因子的分解式个数之和}}}return dp[n];
}int main(){int n;scanf("%d", &n);int count = countSum(n);printf("%d", count);return 0;}

很好，随机测试几个数，没啥问题，复制粘贴

好好好

最后一个测试点超时

做出一些修改

j 因子的范围从1到 i/2 改为2到 根号i

j 因子，对应的因子 i/j（ !=j ），并将两个因子的分解式个数都累加到dp[i]中

    for(int i = 2; i <= n; i++){dp[i] = 1;  //用 dp[j] 计算 dp[i]int limit = sqrt(i);for(int j = 2; j <= limit; j++){ //因子的最大可能值是根号 iif(i % j == 0){           //整除关系，说明 j 是 i 的一个因子//dp[i] 则是待计算的当前数 i 的分解式个数, dp[j] 表示之前计算的拥有因子 j 的数的分解式个数int other_factor = i / j;dp[i] += dp[j];if(other_factor != j){    //因子 i/j（!=j），将两个因子的分解式个数都累加到dp[i]中dp[i] += dp[other_factor];}}}}

n的取值越大还是耗时小高，但是过了所有测试点

---

使用递归

#include <stdio.h>int total = 0;void solve(int n) {if (n == 1)total++;else {for (int i = 2; i <= n; i++)if (n % i == 0)solve(n / i);}
}int main() {int n;scanf("%d", &n);solve(n);printf("%d", total);return 0;
}