n সংখ্যা সহ অ-হ্রাসমান সংখ্যার মোট সংখ্যা

একটি সংখ্যাকে অ-হ্রাস বলা হয় যখন সমস্ত সংখ্যা (প্রথম স্থান ব্যতীত) তার আগের সংখ্যার চেয়ে ছোট না হয়৷ এই অ্যালগরিদমের জন্য, আমাদের খুঁজে বের করতে হবে একটি N-সংখ্যার সংখ্যায় কতগুলি অক্ষয় সংখ্যা রয়েছে৷

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