Tổng số các số không giảm có n chữ số

Một số được cho là không giảm khi tất cả các chữ số (trừ chữ số đầu tiên) không nhỏ hơn chữ số trước của nó. Đối với thuật toán này, chúng ta phải tìm xem có bao nhiêu số không giảm trong một số gồm N.

Hãy để count (n, d) là một hàm đếm có bao nhiêu số không giảm có độ dài n và kết thúc bằng chữ cái d, sau đó chúng ta có thể viết quan hệ như sau.

$$ count (n, d) =\ displaystyle \ sum \ limit_ {i =0} ^ d count (n-1, i) \\ total =\ displaystyle \ sum \ limit_ {d =0} ^ {n-1 } đếm (n-1, d) $$

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

Input:
Number of digits, say 3.
Output:
The possible non decreasing numbers. Here it is 220.
Non decreasing numbers are like 111, 112, 123, 789, 569 etc.

Thuật toán

countNumbers(n)

Đầu vào: Giá trị đã cho.

Đầu ra: Số lượng các giá trị không giảm từ số n chữ số.

Begin
   define count matrix of order (10 x n+1), and fill with 0
   for i := 0 to 9, do
      count[i, 1] := 1
   done

   for digit := 0 to 9, do
      for len := 2 to n, do
         for x := 0 to digit, do
            count[digit, len] := count[digit, len] + count[x, len-1]
         done
      done
   done

   nonDecNum := 0
   for i := 0 to 9, do
      nonDecNum := nonDecNum + count[i, n]
   done

   return nonDecNum
End

Ví dụ

#include<iostream>
using namespace std;

long long int countNumbers(int n) {
   long long int count[10][n+1];    //to store total non decreasing number starting with i digit and length j

   for(int i = 0; i<10; i++)
      for(int j = 0; j<n+1; j++)
         count[i][j] = 0;     //initially set all elements to 0

   for (int i = 0; i < 10; i++)    //set non decreasing numbers of 1 digit
      count[i][1] = 1;

   for (int digit = 0; digit <= 9; digit++) {     //for all digits 0-9
      for (int len = 2; len <= n; len++) {       //for those numbers (length 2 to n)
         for (int x = 0; x <= digit; x++)
            count[digit][len] += count[x][len-1];     //last digit x <= digit, add with number of len-1
      }
   }

   long long int nonDecNum = 0;

   for (int i = 0; i < 10; i++)    //total non decreasing numbers starting with 0-9
      nonDecNum += count[i][n];
   return nonDecNum;
}

int main() {
   int n = 3;
   cout << "Enter number of digits: "; cin >> n;
   cout << "Total non decreasing numbers: " << countNumbers(n);
}

Đầu ra

Enter number of digits: 3
Total non decreasing numbers: 220