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)$$

इनपुट और आउटपुट

इनपुट: अंकों की संख्या, मान लें 3।
आउटपुट: संभावित नॉन-डिक्रीजिंग संख्याएं। यहां यह 220 है।
नॉन-डिक्रीजिंग संख्याएं जैसे 111, 112, 123, 789, 569 आदि।

एल्गोरिदम

countNumbers(n)

इनपुट: दिया गया मान
आउटपुट: n अंकों की संख्याओं से नॉन-डिक्रीजिंग मानों की संख्या

शुरुआत
    (10 x n+1) ऑर्डर की count मैट्रिक्स परिभाषित करें, और 0 से भरें
    i := 0 से 9 तक, करें
        count[i, 1] := 1
    पूर्ण
    digit := 0 से 9 तक, करें
        len := 2 से n तक, करें
            x := 0 से digit तक, करें
                count[digit, len] := count[digit, len] + count[x, len-1]
            पूर्ण
        पूर्ण
    पूर्ण
    nonDecNum := 0
    i := 0 से 9 तक, करें
        nonDecNum := nonDecNum + count[i, n]
    पूर्ण
    वापस nonDecNum
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

long long int countNumbers(int n) {
    long long int count[10][n+1];
    
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < n+1; j++)
            count[i][j] = 0;
    
    for (int i = 0; i < 10; i++)
        count[i][1] = 1;
    
    for (int digit = 0; digit <= 9; digit++) {
        for (int len = 2; len <= n; len++) {
            for (int x = 0; x <= digit; x++)
                count[digit][len] += count[x][len-1];
        }
    }
    
    long long int nonDecNum = 0;
    for (int i = 0; i < 10; i++)
        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