একটি ধনাত্মক পূর্ণসংখ্যা n-র ফ্যাক্টোরিয়াল হলো 1 × 2 × 3 × ... × n। ঋণাত্মক সংখ্যার ফ্যাক্টোরিয়াল অস্তিত্বে নেই। নিচে ডাইনামিক প্রোগ্রামিং পদ্ধতিতে দিয়ে ফ্যাক্টোরিয়াল হিসাব করার একটি C++ প্রোগ্রাম দেওয়া হলো।
অ্যালগরিদম
শুরু fact(int n):
সংখ্যা n পড়ুন
आरম্ভ করুন
i = 1, result[1000] = {0}
result[0] = 1
i = 1 থেকে n পর্যন্ত
result[i] = i * result[i-1]
result প্রিন্ট করুন
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
int result[1000] = {0};
int fact(int n) {
if (n >= 0) {
result[0] = 1;
for (int i = 1; i <= n; ++i) {
result[i] = i * result[i - 1];
}
return result[n];
}
}
int main() {
int n;
while (true) {
cout << "ফ্যাক্টোরিয়াল বের করতে পূর্ণসংখ্যা দিন (বের হওয়ার জন্য 0 দিন): ";
cin >> n;
if (n == 0)
break;
cout << fact(n) << endl;
}
return 0;
}আউটপুট
ফ্যাক্টোরিয়াল বের করতে পূর্ণসংখ্যা দিন (বের হওয়ার জন্য 0 দিন): 2 2 ফ্যাক্টোরিয়াল বের করতে পূর্ণসংখ্যা দিন (বের হওয়ার জন্য 0 দিন): 6 720 ফ্যাক্টোরিয়াল বের করতে পূর্ণসংখ্যা দিন (বের হওয়ার জন্য 0 দিন): 7 5040 ফ্যাক্টোরিয়াল বের করতে পূর্ণসংখ্যা দিন (বের হওয়ার জন্য 0 দিন): 10 3628800 ফ্যাক্টোরিয়াল বের করতে পূর্ণসংখ্যা দিন (বের হওয়ার জন্য 0 দিন): 0
ব্যাখ্যা
এই প্রোগ্রামে result নামক একটি গ্লোবাল অ্যারে ব্যবহার করা হয়েছে যাতে পূর্বে গণনা করা ফ্যাক্টোরিয়াল মানগুলো সংরক্ষণ থাকে। এটি ডাইনামিক প্রোগ্রামিং-এর মেমোইজেশন (memoization) কৌশল। fact() ফাংশনটি প্রথমে result[0] = 1 সেট করে (কারণ 0! = 1)। তারপর একটি লুপ চালিয়ে 1 থেকে n পর্যন্ত প্রতিটি ইনডেক্সের জন্য ফ্যাক্টোরিয়াল মান গণনা করে সংরক্ষণ করে। যেহেতু প্রতিটি মান পূর্বের মানের ওপর নির্ভরশীল, এটি O(n) সময় কমপ্লেক্সিটিতে সমস্যা সমাধান করে।
দ্রষ্টব্য: বড় সংখ্যার ফ্যাক্টোরিয়াল (যেমন 20-এর বেশি) int টাইপে ফিট না করলে long long বা বড় সংখ্যা হ্যান্ডল করার লাইব্রেরি ব্যবহার করা উচিত।
