数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中计算范围内数字出现 d 数字恰好 K 次的个数
给定一个整数范围，从变量 start 开始到变量 end 结束，以及变量 k 和 d。任务是计算该范围内数字 d 出现的次数，使得 d 恰好出现 k 次。
例如
输入 - int start = 10, int end = 100, d = 4 且 K = 2
输出 - 范围内数字 d 出现恰好 K 次的个数为：1
说明 - 范围从 10 到 100。因此，数字 d 即 4 恰好出现 k 即 2 次的数字是 44，因此计数为 1。
输入 - int start = 10, end = 100, d = 6 且 m = 1
输出 - 范围内数字 d 出现恰好 K 次的个数为：1
说明 - 范围从 10 到 100。因此，数字 d 即 4 恰好出现 k 即 1 次的数字是 16、26、36、46、56、76、86 和 96，因此计数为 8。我们不会考虑 66，因为 6 出现的次数超过了 k 次。
下面程序中使用的方案如下
- 创建一个从变量 start 到变量 end 的整数范围，并声明变量 d 和 k 并输入值。将数据传递给函数以进行进一步处理。
- 创建一个向量类型变量，例如 vec。
- 启动循环，直到变量 start 中的值。现在，在循环内部，将值作为 val % 10 推送到向量中，并将 val 设置为 val / 10。
- 通过传递 vec.begin() 和 vec.end() 作为参数，调用 STL 中的 reverse 函数。
- 使用 memset 将数组中的值设置为 -1。
- 返回 set_total(0, 0, 0, vec)，这是一个函数，它将检查偶数位置 d 的数字是否可以被 m 整除
- 在 set_total 函数内部 -
- 检查 IF place 等于向量的尺寸，然后检查 IF temp = k，然后返回 1 或返回 0。
- 检查 IF arr[place][temp][val][rem] 不等于 -1，然后返回 arr[place][temp][val][rem] 中的值。
- 声明一个变量 count 来存储结果。
- 声明一个变量 temp_2，如果 val 等于 1 则将其设置为 9，否则将其设置为 vec[place]。
- 从 i 为 0 开始循环到 temp_2，并检查 IF i 等于 d，然后检查 IF d 不等于 0 或 d 为 0 且 rem = 1，然后将 total 增加 1
- 声明一个变量为 temp_2 并将其设置为 val
- 检查 IF i 小于 vec[place]，则将 temp_2 设置为 1
- 将 count 设置为对函数 set_total 的递归调用
- 返回 arr[place][temp][val] = count。
示例
#include <bits/stdc++.h>
using namespace std;
const int MAX = 20;
int arr[MAX][MAX][2][2];
int d, K;
int set_total(int place, int temp, int val, int rem, vector < int > vec) {
if (place == vec.size()) {
if (temp == K) {
return 1;
}
return 0;
}
if (arr[place][temp][val][rem] != -1) {
return arr[place][temp][val][rem];
}
int count = 0;
int temp_2 = (val ? 9 : vec[place]);
for (int i = 0; i <= temp_2; i++) {
int total = temp;
if (i == d) {
if (d != 0 || (!d && rem)) {
total++;
}
}
int total_2 = val;
if (i < vec[place]) {
total_2 = 1;
}
count += set_total(place + 1, total, total_2, rem || (i != 0), vec);
}
return arr[place][temp][val][rem] = count;
}
int occurrence_d(int val) {
vector < int > vec;
while (val) {
vec.push_back(val % 10);
val = val / 10;
}
reverse(vec.begin(), vec.end());
memset(arr, -1, sizeof(arr));
return set_total(0, 0, 0, 0, vec);
}
int main() {
int start = 10;
int end = 100;
d = 4, K = 2;
int count = occurrence_d(end) - occurrence_d(start - 1);
cout << "Count of Numbers in a Range where digit d occurs exactly K times are: " << count;
return 0;
}如果我们运行以上代码，它将生成以下输出 -
输出
Count of Numbers in a Range where digit d occurs exactly K times are: 1
更新于： 2021年1月29日
267 次浏览
广告