一个正整数的每一位都由 0 或 1 构成,我们就称这个数为 01 数。 现在给你一个任务,给你一个整数 n ,需要你计算出 1 ~ n 范围内有多少个 01 数。C语言
时间: 2024-02-09 21:11:15 浏览: 83
好的,这是一个有趣的问题。我可以为您提供以下C语言代码来解决此问题:
```c
#include <stdio.h>
int count(int n) {
int dp[n + 1][2];
dp[0][0] = 1;
dp[0][1] = 1;
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
dp[i][1] = dp[i - 1][0];
}
return dp[n][0] + dp[n][1];
}
int main() {
int n;
printf("请输入一个整数n:");
scanf("%d", &n);
printf("1~%d范围内的01数有%d个。", n, count(n));
return 0;
}
```
在这个代码中,我们使用动态规划来解决这个问题。我们定义 `dp[i][0]` 表示 i 位 01 数中以 0 结尾的个数, `dp[i][1]` 表示 i 位 01 数中以 1 结尾的个数。根据这个定义,我们可以得到以下递推式:
```
dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
dp[i][1] = dp[i - 1][0]
```
这个递推式的含义是,对于 i 位的 01 数,以 0 结尾的数可以由 i - 1 位的任意一个 01 数在末尾加上 0 得到,以 1 结尾的数只能由 i - 1 位的以 0 结尾的 01 数在末尾加上 1 得到。
最终的结果就是 `dp[n][0] + dp[n][1]`。
希望这个代码可以解决您的问题。
阅读全文