数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中计算范围内的数字，其偶数位和奇数位数字之和的差为素数
给定两个数字start和end作为范围变量。目标是找到在这个范围[start,end]内，且偶数位数字和与奇数位数字和的差为素数的数字个数。
也就是说，（偶数位数字和） - （奇数位数字和）= 素数
让我们通过例子来理解。
例如
输入 - start = 230, end = 270
输出 - 偶数位和与奇数位和的差为素数的数字个数为：6
解释 - 在230到270之间的满足条件的数字是
240 (4-2 = 2), 250 (5-2 = 3), 251 (5-3 = 2), 261 (6-3 = 3), 262 (6-4 = 2), 270 (7-2 = 5)。
这些差值都是2、3和5，都是素数。
输入 - start = 1101, end = 1120
输出 - 偶数位和与奇数位和的差为素数的数字个数为：1
解释 - 在1101到1120之间满足条件的数字是
1120 (3-1 = 2)。2是素数。
下面程序中使用的算法如下
在这个程序中，我们使用动态规划的方法，存储具有素数差（偶数位数字和与奇数位数字和的差）的数字个数。这个数组将是arr[size][90][90][2]。这里size是10的幂。因此，最大的输入数字将是10size。
在对函数check(int place, int eve, int od, int temp, vector<int> vec)的每次递归调用中，我们将从左到右放置数字0到9来构建一个数字。
在arr[size][x][y][temp]中，x是直到x位置偶数位数字的和，y是直到y位置奇数位数字的和。使用存储所有小于100的素数的数组arr_2[]检查所需的差是否为素数。
- 将变量start和end作为输入。
- 使用全局数组arr[size][90][90][2]和数组arr_2[]存储小于100的素数。
- 函数check(int place, int eve, int od, int temp, vector<int> vec)将当前数字位置作为place，当前偶数位数字和作为eve，奇数位数字和作为od，temp的值以及包含数字的向量vec作为参数。
- 它递归地填充arr[place][eve][od][temp]中的值。
- 将当前元素的初始值设置为count=0。
- 对于当前位置，使用if(place == vec.size())检查是否为最后一位。如果是，则检查该位置是奇数位还是偶数位。
- 如果if(vec.size() & 1)结果为真，则当前位置为奇数位，因此交换eve和od，因为它是一个奇数长度的数字。
- 计算temp_2作为eve-od的差值。
- 使用for循环遍历arr_2[]并检查是否找到temp_2。如果是，则它是素数。因此返回1，否则返回0。
- 如果arr[place][eve][od][temp]已经被计算，则它将不为-1，因此返回它。
- 如果temp不为零，则设置temp_3=9。Temp_3是我们可以放置的数字的最大限制。如果它是0，则放置vec[place]，否则数字已经更小，所以放置任何数字，例如9。
- 遍历从0到temp_3的数字。如果当前位置是奇数位，则更新set_odd = set_odd + i;（之前的奇数位数字和 + 当前数字i）。
- 如果当前位置是偶数位，则更新set_even = set_even + i;（之前的偶数位数字和 + 当前数字i）。
- 设置count += check(place + 1, set_even, set_odd, set_temp, vec);并返回arr[place][eve][od][temp] = count。
- 函数place_prime(int val)获取数字val并生成一个向量vec，其中包含从LSB到MSB的数字。
- 将整个数组arr[][][][]设置为-1。
- 设置count = check(0, 0, 0, 0, vec)，它将在最后返回结果。
- 返回count作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
const int size = 18;
int arr[size][90][90][2];
//firt 100 prime Numbers
int arr_2[] = {
2,
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
};
int check(int place, int eve, int od, int temp, vector < int > vec) {
int count;
int temp_3;
if (place == vec.size()) {
if (vec.size() & 1) {
swap(od, eve);
}
int temp_2 = eve - od;
for (int i = 0; i < 24; i++) {
if (temp_2 == arr_2[i]) {
return 1;
}
}
return 0;
}
if (arr[place][eve][od][temp] != -1) {
int set = arr[place][eve][od][temp];
return set;
}
if (temp) {
temp_3 = 9;
} else {
temp_3 = vec[place];
}
for (int i = 0; i <= temp_3; i++) {
int set_temp = temp;
int set_even = eve;
int set_odd = od;
if (i < vec[place]) {
set_temp = 1;
}
if (place & 1) {
set_odd = set_odd + i;
} else {
set_even = set_even + i;
}
count += check(place + 1, set_even, set_odd, set_temp, vec);
}
return arr[place][eve][od][temp] = count;
}
int place_prime(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));
int count = check(0, 0, 0, 0, vec);
return count;
}
int main() {
int start = 20, end = 80;
int count = place_prime(end) - place_prime(start - 1);
cout << "Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: " << count;
return 0;
}如果我们运行上面的代码，它将生成以下输出：
输出
Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: 15
更新于：2021年1月29日
223 次查看
广告