有一个数字n和一个值。我们必须找到所有n位数字,其中s的所有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)
计数(数字,总和)
输入: 数字位数,给定值。
输出:计算多少个数字。
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(数字,总和)
输入: 数字位数,给定值。
输出:该类型的数字有多少个数字。
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