টাওয়ার অফ হানোই একটি পাজল সমস্যা। যেখানে তিনটি স্ট্যান্ড এবং nটি ডিস্ক আছে। প্রাথমিকভাবে, ডিস্কগুলো প্রথম স্ট্যান্ডে থাকে। আমাদের ডিস্কগুলো তৃতীয় বা গন্তব্য স্ট্যান্ডে রাখতে হবে, দ্বিতীয় বা সহায়ক স্ট্যান্ড সাহায্যকারী স্ট্যান্ড হিসেবে ব্যবহার করা যায়।
- কিন্তু কিছু নিয়ম মানতে হবে।
- প্রতিটি মুভমেন্টে শুধু একটি ডিস্ক সরানো যায়।
- শুধু শীর্ষের ডিস্কটি একটি স্ট্যান্ড থেকে তুলা যায়।
- کوई বড় ডিস্ক ছোট ডিস্কের শীর্ষে রাখা যাবে না।
এই সমস্যাটি রিকার্শন দিয়ে সহজে সমাধান করা যায়। প্রথমে, রিকার্শন ব্যবহার করে শীর্ষের (n-1)টি ডিস্ক সোর্স থেকে অক্সিলিয়ারি স্ট্যান্ডে রাখা হয়, তারপর শেষ ডিস্কটি সোর্স থেকে ডেস্টিনেশনে রাখা হয়, তারপর আবার (n-1)টি ডিস্ক অক্সিলিয়ারি স্ট্যান্ড থেকে ডেস্টিনেশন স্ট্যান্ডে রিকার্শন দিয়ে রাখা হয়।
ইনপুট এবং আউটপুট
ইনপুট: ডিস্কের সংখ্যা: ৩ আউটপুট: 1. Move disk 1 from A to C 2. Move disk 2 from A to B 3. Move disk 1 from C to B 4. Move disk 3 from A to C 5. Move disk 1 from B to A 6. Move disk 2 from B to C 7. Move disk 1 from A to C
অ্যালগরিদম
toh(n, s, a, d)
ইনপুট: ডিস্কের সংখ্যা, সোর্স, অক্সিলিয়ারি, ডেস্টিনেশন।
আউটপুট: সঠিক নিয়ম মেনে ডিস্ক সোর্স থেকে ডেস্টিনেশনে সরানোর ধাপ।
শুরু
যদি n = 1, তবে
s থেকে d-এ ডিস্ক সরানোর কথা প্রদর্শন করুন
toh(n-1, s, d, a)
s থেকে d-এ ডিস্ক সরানোর কথা প্রদর্শন করুন
toh(n-1, a, s, d)
শেষউদাহরণ
#include<iostream> using namespace std; void TOH(int n, char s, char a, char d) { static int count = 0; //কাউন্টের সংখ্যা সংরক্ষণ if(n == 1) { count++; cout << count<< ". Move disk " << n << " from "<<s <<" to "<<d<<endl; return; //বেস কেস, যখন শুধু একটি ডিস্ক } TOH(n-1, s, d, a); //রিকার্শিভ কল ফাংশন count++; cout << count<< ". Move disk " << n << " from "<<s <<" to"<<d<<endl; TOH(n-1, a, s, d); } int main() { int n; cout << "Enter the number of disks: "; cin >> n; TOH(n, 'A','B','C'); }আউটপুট
Enter the number of disks: 3 1. Move disk 1 from A to C 2. Move disk 2 from A to B 3. Move disk 1 from C to B 4. Move disk 3 from A to C 5. Move disk 1 from B to A 6. Move disk 2 from B to C 7. Move disk 1 from A to C
