এমন সংখ্যা খুঁজুন যার অঙ্কের যোগফল একটি মানের সমান

এখানে একটি সংখ্যা n এবং একটি মান রয়েছে৷ আমাদের সমস্ত n ডিজিটের সংখ্যা খুঁজে বের করতে হবে, যেখানে সমস্ত n সংখ্যার যোগফল s প্রদত্ত মানের সমান। এখানে 0 একটি সংখ্যা হিসাবে গণনা করা হয় না।

n সংখ্যাটি 1 থেকে 100 এর মধ্যে হতে হবে এবং মান অবশ্যই 1 থেকে 500 এর মধ্যে হতে হবে।

ইনপুট এবং আউটপুট

Input:
This algorithm takes number of digits, and the sum value.
Let the digit count is 3. and sum is 15.
Output:
Display the number of different 3-digit numbers whose sum is 15.
The result is 69. (There are 69 different 3-digit numbers whose sum is 15)

অ্যালগরিদম

গণনা (অঙ্ক, যোগফল)

ইনপুট: সংখ্যার অঙ্ক, প্রদত্ত মান।

আউটপুট: কয়টি সংখ্যা গণনা করুন।

Begin
   if digit = 0, then
      return true when sum = 0

   if memTable[digit, sum] is not vacant, then
      return memTable[digit, sum]
   answer := 0

   for i := 0 to 9 do
      if sum – i >= 0, then
         answer := answer + count(digit – 1, sum - i)
   done

   return memTable[digit, sum] := answer
End

numberCount(digit, sum)

ইনপুট:৷ সংখ্যার অঙ্ক, প্রদত্ত মান।

আউটপুট: এই ধরণের সংখ্যার কত সংখ্যা।

Begin
   define memTable and make all space vacant
   res := 0

   for i := 1 to 9, do
      if sum – i >= 0, then
         res := res + count(digit – 1, sum - i)
   done

   return result
End

উদাহরণ

#include<iostream>
#define ROW 101
#define COL 501
using namespace std;

unsigned long long int memTable[ROW][COL];

unsigned long long int count(int digit, int sum) {
   if (digit == 0)    //for 0 digit number check if the sum is 0 or not
      return sum == 0;

   if (memTable[digit][sum] != -1)    //when subproblem has found the result, return it
      return memTable[digit][sum];

   unsigned long long int ans = 0;    //set the answer to 0 for first time

   for (int i=0; i<10; i++)    //count for each digit and find numbers starting with it
      if (sum-i >= 0)
         ans += count(digit-1, sum-i);
   return memTable[digit][sum] = ans;
}

unsigned long long int numberCount(int digit, int sum) {
   for(int i = 0; i<ROW; i++)    //initially all entries of memorization table is -1
      for(int j = 0; j<ROW; j++)
         memTable[i][j] = -1;
               
   unsigned long long int result = 0;
   for (int i = 1; i <= 9; i++)    //count for each digit and find numbers starting with it
      if (sum-i >= 0)
         result += count(digit-1, sum-i);
   return result;
}

int main() {
   int digit, sum;
   cout << "Enter digit count: "; cin >> digit;
   cout << "Enter Sum: "; cin >> sum;
   cout << "Number of values: " << numberCount(digit, sum);
}

আউটপুট

Enter digit count: 3
Enter Sum: 15
Number of values: 69