একটি সংখ্যা n এবং একটি মান দেওয়া আছে। আমাদের সব n-ডিজিট সংখ্যা খুঁজে বের করতে হবে, যাদের সব ডিজিটের যোগফল s দেওয়া মানের সমান। এখানে ০ কে ডিজিট হিসেবে গণনা করা হয় না।
সংখ্যা n-এর পরিসর ১ থেকে ১০০, এবং মানটির পরিসর ১ থেকে ৫০০ হতে হবে।
ইনপুট এবং আউটপুট
ইনপুট: এই অ্যালগরিদম ডিজিটের সংখ্যা এবং যোগফলের মান নেয়। ডিজিট কাউন্ট ৩, এবং যোগফল ১৫। আউটপুট: যোগফল ১৫ হয় এমন ৩-ডিজিট সংখ্যাগুলোর সংখ্যা প্রদর্শন করুন। ফলাফল: ৬৯। (১৫ যোগফল দিয়ে ৬৯টি ভিন্ন ৩-ডিজিট সংখ্যা রয়েছে)
এলগরিদম
count(digit, sum)
ইনপুট: সংখ্যার ডিজিট, দেওয়া মান।
আউটপুট: কতগুলো সংখ্যা আছে তা গণনা করুন।
শুরু
যদি digit = 0, তবে
return true যখন sum = 0
যদি memTable[digit, sum] খালি না থাকে, তবে
return memTable[digit, sum]
answer := 0
i := 0 থেকে 9 পর্যন্ত, করুন
যদি sum - i >= 0, তবে
answer := answer + count(digit - 1, sum - i)
শর্ত শেষ
শেষ লুপ
return memTable[digit, sum] := answer
শেষ
numberCount(digit, sum)
ইনপুট: সংখ্যার ডিজিট, দেওয়া মান।
আউটপুট: কতগুলো সস্ত্র সংখ্যা আছে।
শুরু
memTable সংজ্ঞায়িত করুন এবং সব স্পেস খালি করুন
res := 0
i := 1 থেকে 9 পর্যন্ত, করুন
যদি sum - i >= 0, তবে
res := res + count(digit - 1, sum - i)
শর্ত শেষ
শেষ লুপ
return result
শেষ
উদাহরণ (C++ কোড)
#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) // ০ ডিজিট সংখ্যা হলে চেক করুন যোগফল ০ কিনা
return sum == 0;
if (memTable[digit][sum] != -1) // সাবপ্রব্লেম ফলাফল পাওয়া গেলে ফেরত দিন
return memTable[digit][sum];
unsigned long long int ans = 0; // প্রথমবার আンサー ০ সেট করুন
for (int i = 0; i < 10; i++) // প্রতিটি ডিজিটের জন্য গণনা করুন এবং সেটি দিয়ে শুরু হওয়া সংখ্যা খুঁজে বের করুন
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++) // প্রাথমিকভাবে মেমোরাইজেশন টেবিলের সব এন্ট্রি -১
for(int j = 0; j < ROW; j++)
memTable[i][j] = -1;
unsigned long long int result = 0;
for (int i = 1; i <= 9; i++) // প্রতিটি ডিজিটের জন্য গণনা করুন এবং সেটি দিয়ে শুরু হওয়া সংখ্যা খুঁজে বের করুন
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
