資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告