Tìm số có tổng chữ số bằng giá trị cho trước

Có một số n và một giá trị. Ta phải tìm tất cả các số n chữ số, nơi tổng của tất cả n chữ số bằng giá trị cho trước. Ở đây 0 không được tính là một chữ số.

Số n phải nằm trong khoảng 1 đến 100, và giá trị phải nằm trong khoảng 1 đến 500.

Đầu vào và Đầu ra

Đầu vào: Thuật toán này nhận số chữ số và giá trị tổng. Giả sử số chữ số là 3 và tổng là 15.
Đầu ra: Hiển thị số lượng các số 3 chữ số khác nhau có tổng là 15. Kết quả là 69. (Có 69 số 3 chữ số khác nhau có tổng là 15)

Thuật toán

count(digit, sum)

Đầu vào: Số chữ số của số, giá trị cho trước.

Đầu ra: Đếm bao nhiêu số thỏa mãn.

Bắt đầu
  nếu digit = 0 thì
    trả về true khi sum = 0
  nếu memTable[digit, sum] không rỗng thì
    trả về memTable[digit, sum]
  answer := 0
  với i := 0 đến 9 làm
    nếu sum - i >= 0 thì
      answer := answer + count(digit - 1, sum - i)
    kết thúc
  kết thúc
  trả về memTable[digit, sum] := answer
Kết thúc

numberCount(digit, sum)

Đầu vào: Số chữ số của số, giá trị cho trước.

Đầu ra: Bao nhiêu số loại đó.

Bắt đầu
  định nghĩa memTable và làm cho tất cả ô trống
  res := 0
  với i := 1 đến 9, làm
    nếu sum - i >= 0 thì
      res := res + count(digit - 1, sum - i)
    kết thúc
  kết thúc
  trả về result
Kết thúc

Ví dụ (C++)

#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)
    // cho số 0 chữ số kiểm tra xem tổng có bằng 0 không
    return sum == 0;
  if (memTable[digit][sum] != -1)
    // khi bài toán con đã tìm thấy kết quả, trả về nó
    return memTable[digit][sum];
  
  unsigned long long int ans = 0;
  // đặt câu trả lời về 0 lần đầu
  for (int i = 0; i < 10; i++)
    // đếm cho mỗi chữ số và tìm số bắt đầu bằng nó
    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++)
    // ban đầu tất cả mục của bảng ghi nhớ là -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++)
    // đếm cho mỗi chữ số và tìm số bắt đầu bằng nó
    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);
}

Đầu ra

Enter digit count: 3
Enter Sum: 15
Number of values: 69