資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告