ফাইন্ড ফ্যাক্টরিয়াল - Using Stack

 

আমরা জানি, Stack ডাটা-স্ট্রাকচার LIFO(Last In First Out) প্যারাডাইম মেনে চলে অর্থাৎ এখানে কোনো ভ্যালু শেষে এড করা হলে তা প্রথমে ডিলিট হয়ে যাবে । আপনি যদি Stack ও Queue ডাটা-স্ট্রাকচার সম্পর্কে না জেনে থাকেন তাহলে নিচের দেওয়া লিঙ্কগুলো থেকে পরে নিতে পারেন -

• Stack ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Queue ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Stack ডাটা-স্ট্রাকচার ইন পাইথন
• Queue ডাটা-স্ট্রাকচার ইন পাইথন

এখন, আসল কাজে ফিরে আসা যাক - আপনাকে একটি ফাংশন লিখতে হবে যা প্যারামিটার হিসেবে একটি নাম্বার নিবে এবং সেই নাম্বারের Factorial বের করে তা রিটার্ন  করতে হবে ।

Factorial Number:-

কোন সংখ্যার factorial number বলতে সেই সংখ্যা থেকে ১ পর্যন্ত সবগুলো সংখ্যার গুণফল কে বোঝায় যেমন :- 

= 5 

= 5 *4 * 3 * 2 *1

 = 120

এখন এই প্রব্লেমটি আমরা অনেক ভাবেই সমাধান করতে পারি । কিন্তু আমরা অন্যভাবে প্রব্লেমটি সমাধান না করে Stack দিয়ে কিভাবে সমাধান করতে হয় তা দেখবো এবং বোঝার চেষ্টা করবো ।

ধরি, আমাদের কাছে একটি নাম্বার আছে 5 । আমরা চাইলে সরাসরি Stack ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট করে তা দিয়ে সমাধান করতে পারি । কিন্তু, Stack ডাটা-স্ট্রাকচার সরাসরি ইমপ্লিমেন্ট না করেও জাভাস্ক্রিপ্টের অ্যারে অথবা পাইথনের লিস্ট দিয়ে খুব সহজেই Stack এর কাজ করে ফেলতে পারি তো চলুন শুরু করা যাক -

স্টেপ(০১) :- প্রথমে, 5 থেকে 1 পর্যন্ত প্রত্যেকতা সংখ্যাকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, 5 থেকে 1 এর মাঝে প্রথম সংখ্যা অর্থাৎ 5 কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু 5 কে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = [5]

স্টেপ(০২) :- এখন, 5 থেকে 1 এর মাঝে দ্বিতীয় সংখ্যা অর্থাৎ 4 কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = [5, 4]

স্টেপ(০৩) :- এবার , 5 থেকে 1 এর মাঝে তৃতীয় সংখ্যা অর্থাৎ 3 কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = [5, 4, 3]

স্টেপ(০৪) :- এবারে, 5 থেকে 1 এর মাঝে চতুর্থ সংখ্যা অর্থাৎ ২ কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = [5, 4, 3, 2]

স্টেপ(০৫) :- এবারে , 5 থেকে 1 এর মাঝে সবশেষ সংখ্যা অর্থাৎ 1 কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = [5, 4, 3, 2, 1]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য একটি নাম্বারের সাথে গুণ করে দিবো ।

একটা নাম্বার নিলাম fact নামে এবং তার ভেতর 1 এসাইন করলাম - 

fact = 1

এখন, contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে fact নাম্বারের এর সাথে গুণ করে দিলাম । এখন contains অ্যারে হবে ৪ উপাদান বিশিষ্ট এবং fact এর মান হবে 1*1 = 1 :-

fact = 1 

fact = 1* 1 

fact = 1

contains = [5, 4, 3, 2]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে fact এর সাথে গুণ করে দিলাম-

fact = 2 

fact = 1 * 2 

fact = 2

contains = [5, 4, 3]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে fact এর সাথে গুণ করে দিলাম-

fact = 3 

fact = 2 * 3 

fact = 6

contains = [5, 4]

একইভাবে contains অ্যারে থেকে শেষের ভ্যালু pop() করে fact এর সাথে গুণ করে দিলাম-

fact = 4 

fact = 6 * 4 

fact = 24

contains = [5]

এখন, contains অ্যারে তে একটি মাত্র সংখ্যা আছে সেইটাকেও pop() করে fact এর সাথে গুণ করে দিলাম -

fact = 5

fact = 2 *4 * 5 

fact = 120

contains = []

এখন এই (fact = 120) ই হলো আমাদের কাঙ্খিত ফলাফল । এতো দূর পর্যন্ত আপনি যদি বুঝে থাকেন তাহলে আপনাকে Congrats আর যদি বুঝে নাহ থাকেন তাহলে আরেকবার পড়ুন এবং অন্য আরেকটি নাম্বারের Factorial বের করার চেষ্টা করুন ।

তো চলুন এখন কোড লিখা যাক -

পাইথনে ইমপ্লিমেন্টেশন :-

def fact(n):
    contains = []
    while n > 0:
        contains.append(n)
        n -= 1

    fact = 1
    while len(contains) > 0:
        fact *= contains.pop()

    return fact

Output :

print(fact(5))  # 120
print(fact(7))  # 5040

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন -

const fact = (n) => {
  let contains = [];
  while (n > 0) {
    contains.push(n);
    console.log(n);
    n--;
  }
  let fact = 1;
  while (contains.length > 0) {
    fact *= contains.pop();
  }
  return fact;
};

Output :

fact(5);  // 120
fact(7); // 5040

কোড বিশ্লেষণ :-

উপরোক্ত কোডে, প্রথমে contains নামে একটি অ্যারে বা লিস্ট নিয়েছি । তারপর, একটি লুপ থ্রু করেছি যতক্ষণ 0 থেকে n বড় হতে থাকবে ততক্ষণ লুপটি চলবে এবং প্রত্যেকতা সংখ্যাকে contains নামের অ্যারে বা লিস্টে পুশ করে দিয়েছি । n এর মান প্রত্যেক ইটারেশনে 1 করে কমে দিয়েছি ।

fact নামে একটি নাম্বার নিয়েছি তাতে 1 এসাইন করেছি এবং contains অ্যারেতে একটি লুপ থ্রু করেছি । লুপটি ততক্ষণ চলবে যতক্ষণ পর্যন্ত contains এর সাইজ 0 থেকে বড় থাকবে । এবং প্রত্যেক ইটারেশনে fact এর সাথে contains এর শেষ উপাদানটি রিমুভ হয়ে গুণ হতে থাকবে । এক পর্যায়ে আমাদের লুপটি শেষ হয়েছে । এখন, fact ভেরিয়েবলে আমাদের কাঙ্খিত factorial ভ্যালু রয়েছে তাই সেইটা রিটার্ন করেছি ।

কোডের টাইম ও স্পেস উভয় কমপ্লেক্সিটি হবে ওর্ডার অব এন অর্থাৎ O(n) ।