n桁の非減少数の総数

すべての桁（最初の桁を除く）が前の桁より小さくない場合、数値は減少しないと言われます。このアルゴリズムでは、N桁の数字の中に減少しない数字がいくつあるかを見つける必要があります。

count（n、d）を、長さがnで、文字dで終わる非減少数がいくつあるかをカウントする関数とすると、次のような関係を記述できます。

$$ count（n、d）=\ displaystyle \ sum \ Limits_ {i =0} ^ d count（n-1、i）\\ total =\ displaystyle \ sum \ limits_ {d =0} ^ {n-1 } count（n-1、d）$$

入力と出力

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.

アルゴリズム

countNumbers(n)

入力： 与えられた値。

出力： n桁の数値から減少しない値の数。

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

例

#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);
}

出力

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