用c语言写一个代码:一个正整数的每一位都由 0 或 1 构成,我们就称这个数为 01 数。 现在给你一个任务,给你一个整数 n ,需要你计算出 1 ~ n 范围内有多少个 01 数。 输入格式 一行,一个整数 n。( 1 ≤ n ≤ 109) 输出格式 一个整数,表示 01 数的数量。
时间: 2024-02-09 12:11:05 浏览: 21
这个问题可以用动态规划(DP)来解决。我们可以从小到大枚举每个数字,然后根据上一个数字的01数,得到当前数字的01数。
具体来说,我们可以用两个状态来表示当前数字的01数:
- f0[i]:表示以数i的最后一位为0的01数的数量
- f1[i]:表示以数i的最后一位为1的01数的数量
对于一个数i,如果它的最后一位为0,则可以在它前面添加一个0或者1来得到一个新的01数,所以有:
- f0[i] = f0[i-1] + f1[i-1]
如果它的最后一位为1,则只能在它前面添加一个0来得到一个新的01数,所以有:
- f1[i] = f0[i-1]
最终的答案为f0[n] + f1[n]。
以下是完整的代码实现:
```c
#include <stdio.h>
int main() {
long long f0 = 1, f1 = 1, n, i, tmp;
scanf("%lld", &n);
for (i = 2; i <= n; i++) {
tmp = f0;
f0 = f0 + f1;
f1 = tmp;
}
printf("%lld\n", f0 + f1);
return 0;
}
```
注意在计算时,需要使用long long类型来存储f0和f1的值,因为它们可能非常大。
相关问题
一个正整数的每一位都由 0 或 1 构成,我们就称这个数为 01 数。 现在给你一个任务,给你一个整数 n ,需要你计算出 1 ~ n 范围内有多少个 01 数。C语言
好的,这是一个有趣的问题。我可以为您提供以下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]`。
希望这个代码可以解决您的问题。
C语言从键盘上输入一个正整数给int变量num,输出由8~11位构成的数
好的,我可以帮您解决这个问题。以下是一种可能的实现方式:
```c
#include <stdio.h>
int main() {
int num;
printf("请输入一个正整数:");
scanf("%d", &num);
printf("构成的数为:%d\n", num % 100000000);
return 0;
}
```
这段代码中,我们首先从键盘上读入一个正整数,然后使用取模运算符 `%` 得到该正整数的后8位,即由8~11位构成的数。最后将这个数输出到屏幕上。需要注意的是,如果输入的正整数不足8位,则输出的结果可能不是由8~11位构成的数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)