简答题
偏难
#7405
吃糖果2(2023.12) 现有n(50 > n > 0)个糖果,每天只能吃2个或者3个,请计算共有多少种不同的吃法吃完糖果。 时间限制:1000 内存限制:6…
吃糖果2(2023.12)
现有n(50 > n > 0)个糖果,每天只能吃2个或者3个,请计算共有多少种不同的吃法吃完糖果。
时间限制:1000
内存限制:65536
输入
输入的每一行包括一组测试数据,即为糖果数n。最后一行为0,表示测试结束。
输出
每一行输出对应一行输入的结果,即为吃法的数目。
样例输入
1 2 3 4 12 0
样例输出
0 1 1 1 12
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// C++参考代码1
#include <bits/stdc++.h>
using namespace std;
int a[52] = {0, 0, 1, 1};
int f(int n) {
if (n <= 3)
return a[n];
if (a[n] > 0)
return a[n];
a[n] = f(n - 2) + f(n - 3);
return a[n];
}
int main() {
int n;
while (true) {
cin >> n;
if (n == 0)
break;
cout << f(n) << endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// C++参考代码2
#include <iostream>
#include <vector>
int countWays(int n) {
std::vector<int> dp(n + 1, 0);
dp[0] = 1; // 初始条件
for (int i = 1; i <= n; i++) {
if (i >= 2) {
dp[i] += dp[i - 2];
}
if (i >= 3) {
dp[i] += dp[i - 3];
}
}
return dp[n];
}
int main() {
int n;
while (std::cin >> n && n != 0) {
int ways = countWays(n);
std::cout << ways << std::endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// C语言参考代码
#include <stdio.h>
int countWays(int n) {
if (n == 0 || n == 1)
return 0;
else if (n == 2)
return 1;
else if (n == 3)
return 1;
else
return countWays(n - 2) + countWays(n - 3);
}
int main() {
int n;
while (scanf("%d", &n) == 1 && n != 0) {
int ways = countWays(n);
printf("%d\n", ways);
}
return 0;
}</pre>
这道题暂未补解析。