下面这一段代码为什么无法求解出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-14 14:29:42 浏览: 19
这段代码在计算不包含数字 4 的数的个数时存在问题。主要原因是在递归调用 `dfs` 函数时,没有正确地传递参数 pre(前一位数字)。
为了修改这段代码,我们需要做以下几个步骤:
1. 添加一个新的参数 `pre`,用于表示前一位数字的取值。
2. 在递归调用 `dfs` 函数时,将当前位数的取值 `i` 作为参数传递给下一层递归,同时将当前位数的取值作为前一位数传递给下一层递归。
3. 在循环中,判断如果当前位数的取值 `i` 等于 4,则跳过当前循环,排除数字 4。
4. 在递归调用 `dfs` 函数时,传入当前位数的取值 `i` 作为前一位数字的参数。
下面是修改后的代码:
```cpp
const int maxn = 12;
int dp[maxn];
int digit[10] = {0};
int dfs(int len, bool ismax, int pre) {
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, i);
}
if (!ismax) dp[len] = ans;
return ans;
}
```
通过以上修改,代码现在正确地传递了前一位数字的取值,并将其作为参数传递给下一层递归。这样,递归调用 `dfs` 函数时就可以正确地判断是否需要排除以 4 开头的数字,从而求解出不包含数字 4 的数的个数。
相关推荐
![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)
![](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)