จำนวนรวมของตัวเลขที่ไม่ลดลงด้วย 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 } จำนวน (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