মডিউল ১৭_২ঃ ফ্যাক্টোরিয়াল নাম্বার

আমরা এখন ফ্যাক্টোরিয়াল নাম্বার সম্পর্কে জানবো। এটি কি,কিভাবে কাজ করে,ডিপি ইউজ করা উচিত কি না এইসব এর ধারনা নিব।

তাহলে এখন আগে জেনে নেই ফ্যাক্টোরিয়াল কি?

ফ্যাক্টোরিয়ালকে আমরা ! এইটা দিয়ে প্রকাশ করি। এটির মানে হচ্ছে যেই সংখ্যা দেওয়া থাকবে তা থেকে শুরু করে তার আগের সকল পজিটিভ সংখ্যার গুণফল।

৫! = ৫*৪*৩*২*১ = ১২০

৪! = ৪*৩*২*১ = ২৪

তাহলে আমরা বলতে পারি,

n! = n*(n-1)*..........*3*2*1

এখন একটা মজার জিনিস খেয়াল করে দেখি।

৫! = ৫*৪*৩*২*১

আবার ৪! = ৪*৩*২*১

তাহলে বলা যায় না ৫! = ৫*৪!

সেই সাথে তাহলে বলতে পারি n! = n*(n-1)!

তাহলে খেয়াল করে দেখো এখানে একটা রিকারশিব এপ্রোচ এর সন্ধান আমরা পেয়ে যাচ্ছি। কেননা এক প্রবলেম এর কিছু সাব প্রবলেম বিদ্যমান। আমরা বেইস কেইস সেট করে দিব। অর্থাৎ বলবো যে n এর মান ০ হলে ১ দাও। কেননা ০!=১। আর বাকি কাজটা করবো ফাংশনের মাধ্যমে।

// Some code
  int fn(n) {
  // type your own code
  if(n == 0) return 1;
  return n*fn(n-1);
}

রিকারশানতো দেখলাম এবার দেখি memoization করা যায় কিনা। খেয়াল করে দেখো এখানে কোনো রিপিটেড ফাংশন কল নেই। তাই এখানে আসলে অপ্টিমাইজ করার কোনো জায়গা নাই। তাহলে এই থেকে আমরা বুঝতে পারলাম যে সব রিকারশানে আসলে memoization করা যায় না। যেখানে অপ্টিমাইজ করা পসিবল শুধু সেখানে memoization করা যাবে। এই ক্ষেত্রে এই ফাংশনের টাইম কমপ্লেক্সিটি O(N)| কেননা এখানে N সংখ্যক বার ফাংশন কল হচ্ছে।