阅读程序(第三题):整数划分的动态规划

ty930448 组合题 共 个子题

阅读下面程序,完成后面的判断题和单选题。判断题正确填 A,错误填 B。程序读入一个整数 n(0 ≤ n ≤ 1000)。

#include <algorithm>
#include <cstdio>
#include <cstring>

const int MAXN = 1005;
const int MOD = 1000000007;

int n;
long long f[MAXN], g[MAXN];

int main() {
    scanf("%d", &n);
    f[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            f[j] = (f[j] + f[j - i]) % MOD;
    g[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = n; j >= i; --j)
            g[j] = (g[j] + g[j - i]) % MOD;
    printf("%lld %lld\n", f[n], g[n]);
    return 0;
}

子题 判断题

判断题:f[n] 表示把 n 拆分成若干个正整数之和(不计顺序、允许相同整数重复出现)的方案数。( )

A

正确

B

错误

子题 判断题

判断题:当输入为 20 时,程序输出 64 627。( )

A

正确

B

错误

子题 判断题

判断题:若把第 15 行的 `for (int j = i; j <= n; ++j)` 改为 `for (int j = n; j >= i; --j)`,其余不变,则修改后输出的第一个数表示把 n 拆分成若干个互不相同的正整数之和的方案数。( )

A

正确

B

错误

子题 单选题

当输入为 50 时,程序输出的两个数依次是( )。

A

204226 444793

B

3658 204226

C

204226 3658

D

5604 296

子题 单选题

该程序的时间复杂度和空间复杂度分别为( )。

A

O(n) 与 O(n)

B

O(n²) 与 O(n)

C

O(n²) 与 O(n²)

D

O(n³) 与 O(n)

子题 单选题

若把第 19 行的 `for (int j = n; j >= i; --j)` 改为 `for (int j = i; j <= n; ++j)`,其余不变,则当输入为 10 时,程序输出为( )。

A

42 10

B

42 42

C

10 10

D

10 42

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧