替我写一段C语言程序,要求使用动态规划思想:一条小路有n块砖,每一步可以前进一块或两块砖。初始位置为第一块砖,问:恰好到达最后一块砖的不同走法有多少种。输入时,输入一个数字,表示砖块数n。输出为一个数字,表示走法数对100007取模后的值。(当输入为171878时,输出为79163)
时间: 2023-06-25 11:05:34 浏览: 46
以下是动态规划思想的C语言程序:
```c
#include <stdio.h>
#define MOD 100007
int main() {
int n;
scanf("%d", &n);
int dp[3] = {1, 1, 0}; // dp数组,dp[0]表示当前位置为第0块砖时的走法数,dp[1]表示当前位置为第1块砖时的走法数,dp[2]表示当前位置为第2块砖时的走法数
for (int i = 3; i <= n; i++) {
dp[2] = (dp[0] + dp[1]) % MOD;
dp[0] = dp[1];
dp[1] = dp[2];
}
printf("%d\n", dp[2]);
return 0;
}
```
解释:对于第i(i >= 3)块砖,可以从第i-1块砖或第i-2块砖到达,所以到达第i块砖的走法数为到达第i-1块砖的走法数与到达第i-2块砖的走法数之和。因此我们可以用一个长度为3的dp数组来存储当前位置为第i-2、i-1、i块砖时的走法数,每次循环更新dp数组即可。最终答案即为dp[2]对100007取模后的值。
相关问题
用C语言实现一条小路有n块地板,每一步可以前进一块或两块地板。初始位置为第一块,问:恰好到达最后一块地板的不同走法有多少种
这个问题可以使用动态规划来解决。
令 $dp[i]$ 表示到达第 $i$ 块地板的不同走法数目。
对于第 $i$ 块地板,可以从第 $i-1$ 块地板走一步到达,也可以从第 $i-2$ 块地板走两步到达。因此,$dp[i]$ 可以由 $dp[i-1]$ 和 $dp[i-2]$ 推导出来:
$$dp[i] = dp[i-1] + dp[i-2]$$
初始状态为 $dp[1] = 1$,$dp[2] = 2$。
最终答案为 $dp[n]$。
以下是使用 C 语言实现的代码:
```c
#include <stdio.h>
int main() {
int n;
printf("请输入地板的块数:");
scanf("%d", &n);
int dp[n+1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
printf("恰好到达最后一块地板的不同走法有 %d 种\n", dp[n]);
return 0;
}
```
输入地板的块数后,程序会输出恰好到达最后一块地板的不同走法数目。
用c语言写一段程序,要求:由键盘输入一个整数n,并且计算n的阶乘,并且输出。
好的,可以使用以下代码实现:
```
#include <stdio.h>
int main() {
int n, i;
unsigned long long factorial = 1;
printf("请输入一个整数n:");
scanf("%d", &n);
if (n < 0) {
printf("负数没有阶乘!\n");
} else {
for (i = 1; i <= n; ++i) {
factorial *= i;
}
printf("%d的阶乘为%llu\n", n, factorial);
}
return 0;
}
```
代码中使用了一个循环来计算n的阶乘,因为n的阶乘可能非常大,所以使用了`unsigned long long`类型来存储结果,这个类型可以存储的整数范围比`int`类型大。