C语言m块饼每天吃1块或者2块,吃到完为止。问有多少种不同的吃法。注意:第1天吃2块第2天吃1块和第1天吃1块第2天吃2块,是两种不同的吃法。
时间: 2024-05-02 22:17:29 浏览: 14
这是一个典型的斐波那契数列问题,可以使用递归或动态规划来解决。
假设吃n块饼干有f(n)种不同的吃法,那么可以得到以下递推式:
f(n) = f(n-1) + f(n-2)
其中f(1) = 1, f(2) = 2。这个递推式的意思是,吃n块饼干的不同吃法数等于吃n-1块饼干的不同吃法数和吃n-2块饼干的不同吃法数之和。
使用递归来实现:
```c
#include <stdio.h>
int eat_cookie(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return eat_cookie(n-1) + eat_cookie(n-2);
}
int main() {
int n;
printf("请输入饼干的数量:");
scanf("%d", &n);
printf("有%d种不同的吃法\n", eat_cookie(n));
return 0;
}
```
使用动态规划来实现:
```c
#include <stdio.h>
int eat_cookie(int n) {
int f1 = 1;
int f2 = 2;
int f3;
if (n == 1) {
return f1;
}
if (n == 2) {
return f2;
}
for (int i = 3; i <= n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
int main() {
int n;
printf("请输入饼干的数量:");
scanf("%d", &n);
printf("有%d种不同的吃法\n", eat_cookie(n));
return 0;
}
```
两种方法的时间复杂度都是O(n),但是递归方法由于需要不断调用函数,会在n较大时导致栈溢出或者运行时间过长。所以建议使用动态规划的方法来实现。