下面这一段代码为什么无法求解出0~n中不包含数字4的数的个数?应当如何修改: const int maxn = 12; int dp[maxn]; int digit[10] = {0}; int dfs(int len, bool ismax) { // ismax为数位上界变量 if(len == 0) return 1; if(!ismax && dp[len] != -1) return dp[len]; int ans = 0, maxx = ismax ? digit[len] : 9; for(int i = 0; i <= len; i++) { if(i == 4) continue; //if(pre == 6 && i == 2) continue; ans += dfs(len - 1, ismax && i == maxx); } if(!ismax) dp[len] = ans; return ans; }
时间: 2024-04-13 09:31:13 浏览: 27
这段代码无法求解出0~n中不包含数字4的数的个数的原因是在循环中没有对数字4进行排除操作。需要修改的地方是在for循环内部加入对数字4的判断,如果i等于4,则跳过当前循环。修改后的代码如下:
```cpp
const int maxn = 12;
int dp[maxn];
int digit[10] = {0};
int dfs(int len, bool ismax) {
if(len == 0) return 1;
if(!ismax && dp[len] != -1) return dp[len];
int ans = 0, maxx = ismax ? digit[len] : 9;
for(int i = 0; i <= len; i++) {
if(i == 4) continue; // 排除数字4
ans += dfs(len - 1, ismax && i == maxx);
}
if(!ismax) dp[len] = ans;
return ans;
}
```
这样修改后,代码会正确地求解出0~n中不包含数字4的数的个数。
相关问题
下面这一段代码为什么无法求解出0~n中不包含数字4的数的个数?应当如何修改: const int maxn = 12; int dp[maxn]; int digit[10] = {0}; int dfs(int len, bool ismax) { // ismax为数位上界变量 if(len == 0) return 1; if(!ismax && dp[len] != -1) return dp[len]; int ans = 0, maxx = ismax ? digit[len] : 9; for(int i = 0; i <= len; i++) { if(i == 4) continue; ans += dfs(len - 1, ismax && i == maxx); } if(!ismax) dp[len] = ans; return ans; }
这段代码无法正确求解出0~n中不包含数字4的数的个数的原因是在循环中应该从1开始而不是从0开始。另外,对于数字4的判断应该是在递归调用之前进行,而不是在循环内部。修改后的代码如下:
```cpp
const int maxn = 12;
int dp[maxn];
int digit[10] = {0};
int dfs(int len, bool ismax) {
if(len == 0) return 1;
if(!ismax && dp[len] != -1) return dp[len];
int ans = 0, maxx = ismax ? digit[len] : 9;
for(int i = 1; i <= maxx; i++) {
if(i == 4) continue; // 排除数字4
ans += dfs(len - 1, ismax && i == maxx);
}
if(!ismax) dp[len] = ans;
return ans;
}
```
这样修改后,代码会正确地求解出0~n中不包含数字4的数的个数。
用c++写出条件如下的代码:用筛法求之N内的素数 输入N 输出0~N的素数
以下是用 C++ 写的用筛法求解从 0 到 N 之间的素数的代码:
```c++
#include<iostream>
using namespace std;
const int MAXN = 100000; // 素数个数上限
bool is_prime[MAXN+1]; // 标记数组,初始全部为 true
void sieve(int n) { // 筛选法求素数
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
for (int j = i*i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
}
int main() {
int n;
cin >> n;
fill(is_prime, is_prime+n+1, true); // 初始化为全部为素数
sieve(n); // 筛选素数
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
cout << i << " "; // 输出素数
}
}
cout << endl;
return 0;
}
```
这段代码中,首先定义了一个常量 `MAXN` 表示素数的个数上限,以及一个布尔类型的标记数组 `is_prime`,用于标记某个数是否为素数。在主函数中,首先输入一个数 `n`,然后将标记数组全部初始化为 `true`,并调用 `sieve` 函数进行筛选素数。在 `sieve` 函数中,首先将 `0` 和 `1` 标记为非素数,然后从 `2` 开始遍历到 `n`,如果这个数是素数,就将它的倍数全部标记为非素数,最后返回主函数。在主函数中,遍历 `2` 到 `n` 之间的所有数,如果这个数是素数,就输出它。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)