資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中計算數字個數（小於或等於 N 且數字和為給定值）
給定一個包含數字的字串 str 和一個總和 total 作為輸入。目標是找到小於等於 str 的數字，其各位數字之和等於 total。
讓我們透過例子來理解。
例如
輸入 - N=”110” sum=5
輸出 - 小於或等於 N 且數字和為給定值的數字個數為：7
解釋 - 小於或等於 110 且數字和等於 5 的數字為：
5、14、23、32、41、50 和 104。
輸入 - N=”1000” sum=3
輸出 - 小於或等於 N 且數字和為給定值的數字個數為：10
解釋 - 小於或等於 1000 且數字和等於 3 的數字為：
3、12、21、30、102、111、120、201、210 和 300。
下面程式中使用的方案如下
在這種方案中，我們將使用動態規劃將數字及其數字的和儲存在陣列 arr[18][2][162] 中。這裡 18 表示最多 18 位數字，2 表示值 0 和 1。而 162 表示如果所有 18 位數字都是 9，則可能的最大和 (18*9=162)。
元素 arr[i][j][k] 的值表示考慮前 i 位數字的數字個數，其中 j 為 0 或 1，具體取決於當前構造的數字的第 i 位是否小於或大於 N 中的前 i 位數字。（如果 N 為 123 且 i 為 2，則我們將檢查 2 位數字是否等於或大於 12。如果等於 12，則 j 在 arr[i][j][k] 中將為 1，否則 j 將為 0）。索引 k 將是 arr[i][j][k] 中前 i 位數字的和。
如果 i=N 的位數且 k=輸入的和，則結果為 1，否則為 0。
為了填充下一位數字（第 i+1 位），我們將檢查 j。如果 j 為 1，則前 i-1 位數字等於 N 的前 i-1 位數字，因此下一位數字只能取 0 到第 i+1 位數字之間的值，以使其 <= N。
如果 j 為 0，則前 i-1 位數字小於 N 中的前 i-1 位數字。因此，我們可以將 0 到 9 之間的任何值放在下一位數字（第 i+1 位）的位置，它仍然小於 N。
最後將結果作為最終計數返回。
- 獲取表示數字 N 的字串 str 和 total 作為數字之和。
- 獲取陣列 arr[18][2][162] 並使用 memset 將其初始化為 -1。
- 函式 count_digits(int i, bool check, int temp, int total, string str, int size) 遞迴地填充 arr[][][]，並在最後返回小於或等於 N 且數字和為給定值的數字個數。
- 如果當前數字位數 i 等於 N 的位數，且當前和 temp 等於輸入的和 total，則返回 1，否則返回 0。
- 獲取計數 count = arr[i][check][temp]。如果它不等於 -1，則返回 count 作為結果。
- 獲取臨時變數 check_2（布林值）和 temp_2。（整數）。
- 使用 for 迴圈遍歷數字 0 到 9，並比較 check 是否為 1 或 0。如果為 1，則將當前數字 ch 與 str[i] 比較。如果它更大，則中斷迴圈（不做任何事）。
- 設定 check_2 = check || ch < str[i]。
- 設定 temp_2 = temp + (ch - '0') 作為當前和。
- 將 count_digits(i + 1, check_2, temp_2, total, str, size) 新增到 count 中，以遞迴計算數字之和。
- 最後返回 count 作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, ing str, int size) {
if (i == size) {
if (temp == total) {
return 1;
} else {
return 0;
}
}
int count = arr[i][check][temp];
if (count != -1) {
return count;
}
count = 0;
bool check_2;
int temp_2;
for (char ch = '0'; ch <= '9'; ch++) {
if (!check) {
if (ch > str[i]) {
break;
}
}
check_2 = check || ch < str[i];
temp_2 = temp + (ch - '0');
count += count_digits(i + 1, check_2, temp_2, total, str, size);
}
return count;
}
int main() {
string str = "1101";
int size = str.size();
int total = 5;
memset(arr, -1, sizeof(arr));
cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size);
return 0;
}如果我們執行上面的程式碼，它將生成以下輸出：
輸出
Count of numbers smaller than or equal to N with given digit sum are: 26
2K+ 次瀏覽
