資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢數字位數之和等於給定值的數字
有一個數字 n 和一個值。我們必須找到所有 n 位數，其中所有 n 位數的和等於給定值。這裡 0 不算作數字。
數字 n 必須在 1 到 100 的範圍內，值必須在 1 到 500 的範圍內。
輸入和輸出
Input: This algorithm takes number of digits, and the sum value. Let the digit count is 3. and sum is 15. Output: Display the number of different 3-digit numbers whose sum is 15. The result is 69. (There are 69 different 3-digit numbers whose sum is 15)
演算法
count(digit, sum)
輸入：數字的位數，給定值。
輸出：計算有多少個數字。
Begin if digit = 0, then return true when sum = 0 if memTable[digit, sum] is not vacant, then return memTable[digit, sum] answer := 0 for i := 0 to 9 do if sum – i >= 0, then answer := answer + count(digit – 1, sum - i) done return memTable[digit, sum] := answer End
numberCount(digit, sum)
輸入：數字的位數，給定值。
輸出：有多少個這種型別的數字。
Begin define memTable and make all space vacant res := 0 for i := 1 to 9, do if sum – i >= 0, then res := res + count(digit – 1, sum - i) done return result End
示例
#include<iostream>
#define ROW 101
#define COL 501
using namespace std;
unsigned long long int memTable[ROW][COL];
unsigned long long int count(int digit, int sum) {
if (digit == 0) //for 0 digit number check if the sum is 0 or not
return sum == 0;
if (memTable[digit][sum] != -1) //when subproblem has found the result, return it
return memTable[digit][sum];
unsigned long long int ans = 0; //set the answer to 0 for first time
for (int i=0; i<10; i++) //count for each digit and find numbers starting with it
if (sum-i >= 0)
ans += count(digit-1, sum-i);
return memTable[digit][sum] = ans;
}
unsigned long long int numberCount(int digit, int sum) {
for(int i = 0; i<ROW; i++) //initially all entries of memorization table is -1
for(int j = 0; j<ROW; j++)
memTable[i][j] = -1;
unsigned long long int result = 0;
for (int i = 1; i <= 9; i++) //count for each digit and find numbers starting with it
if (sum-i >= 0)
result += count(digit-1, sum-i);
return result;
}
int main() {
int digit, sum;
cout << "Enter digit count: "; cin >> digit;
cout << "Enter Sum: "; cin >> sum;
cout << "Number of values: " << numberCount(digit, sum);
}輸出
Enter digit count: 3 Enter Sum: 15 Number of values: 69
更新於： 2020年6月16日
1K+ 瀏覽量
廣告