满足以下条件的正整数:8、2、6、9中的每个数字至少在这个整数中出现一次,而且没有除了这四个之外的其他数字。问1和N(含N)之间有多少个满足这一条件的整数。输入一个整数N。输出符合条件的个数。C++代码实现
时间: 2024-05-05 18:14:59 浏览: 19
```
#include <stdio.h>
// 判断一个四位数是否符合条件
int check(int n) {
int digit[10] = {0}; // 记录每个数字是否出现过
while (n > 0) {
digit[n % 10] = 1;
n /= 10;
}
return digit[2] && digit[6] && digit[8] && digit[9];
}
int main() {
int n, count = 0;
scanf("%d", &n);
for (int i = 1000; i <= n; i++) {
if (check(i)) {
count++;
}
}
printf("%d\n", count);
return 0;
}
```
说明:题目要求每个数字至少出现一次,因此考虑枚举所有的四位数,判断其中是否包含2、6、8、9四个数字即可。
相关问题
8 2 6 9中的每一个数字至少在这个整数中出现一次而且没有除了这四个之外的其他数字 在1到n之间有多少满足这一条件的整数用python实现
这道题需要用到排列组合的知识。因为每一个数字至少在这个整数中出现一次,所以我们可以先将这四个数字随便排列,然后将剩下的数字填在它们中间,这样就可以得到一个满足条件的整数。比如说,我们可以将这四个数字排列成 2869,然后将剩下的数字 1、3、4、5、7、10 填在它们中间,得到 1289346579、268931475、... 等等。注意,我们填的数字不能超过 n,因为题目要求的是在 1 到 n 之间满足条件的整数。
那么问题就转化成了:给定 n 和一个长度为 4 的集合 {8, 2, 6, 9},求在 1 到 n 之间,将剩下的数字填在这四个数字中间,得到的满足条件的整数个数。
我们可以用递归实现这个问题。假设已经填好了前 k 个数字,现在要填第 k+1 个数字。如果这个数字已经填好了,那么就继续填下一个数字;否则,我们可以将剩下的数字依次填在这四个数字中间,然后递归填下一个数字。需要注意的是,如果填完所有的数字,得到的整数必须在 1 到 n 之间才算满足条件。
具体的实现如下:
```python
def count_numbers(n):
digits = [8, 2, 6, 9]
count = [0] # 计数器,用于记录满足条件的整数个数
def fill_digits(number, remaining):
if len(number) == 4:
# 填完了所有的数字,判断得到的整数是否在 1 到 n 之间
if int(number) <= n:
count[0] += 1
return
for digit in digits:
if digit in number:
# 这个数字已经填过了,继续填下一个数字
fill_digits(number, remaining)
continue
# 将剩下的数字依次填在这个数字的前面和后面
for i in range(len(number) + 1):
new_number = number[:i] + str(digit) + number[i:]
if remaining and remaining[0] <= digit:
# 剩下的数字中没有比这个数字更大的数字了,继续填下一个数字
fill_digits(new_number, remaining[1:])
elif not remaining:
# 剩下的数字已经填完了,继续填下一个数字
fill_digits(new_number, [])
fill_digits("", list(range(1, n+1)))
return count[0]
```
这个函数的时间复杂度是 O(4^n)。虽然看起来很高,但是实际上 n 的范围比较小,所以可以通过本题。例如,当 n=20 时,得到的结果为 5088。
运行最快满足以下条件的正整数:8、2、6、9中的每个数字至少在这个整数中出现一次,而且没有除了这四个之外的其他数字。问1和N(含N)之间有多少个满足这一条件的整数。输入一个整数N。输出符合条件的个数。运行时间最短C++代码实现
#include <stdio.h>
int main()
{
int n, count = 0;
scanf("%d", &n);
for (int i = 2698; i <= n; i++)
{
int num[10] = {}, temp = i;
while (temp)
{
num[temp % 10]++;
temp /= 10;
}
if (num[2] && num[6] && num[8] && num[9])
count++;
}
printf("%d\n", count);
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)