আমাদের n সংখ্যক সিঁড়ি এবং ২টি রঙ (লাল এবং হলুদ) দেওয়া আছে যেটি দিয়ে এই সিঁড়িগুলো রঙ করা হবে। আমাদের কাজ হল সিঁড়িগুলো রঙ করার পদ্ধতির সংখ্যা গণনা করা যাতে কোনো দুটি συνεχা ধাপ হলুদ রঙে না থাকে।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝি,
ইনপুট
3
আউটপুট
5
ব্যাখ্যা
সিঁড়িগুলো রঙ করার পদ্ধতিগুলো হল YRY, RYR, YRR, RRY, RRR. এখানে R হল লাল রঙ, Y হল হলুদ রঙ।
এই সমস্যাটি সমাধান করতে, চলুন সিঁড়িগুলো রঙ করার পদ্ধতির সংখ্যা দেখি।
N = 1, ways(1) = 2 : R, Y
N = 2, ways(2) = 3 : RY, YR, RR
N = 3, ways(3) = 5 : RYR, YRY, RRY, YRR, RRR
N = 4, ways(4) = 8 : YRYR, RYRY, RYRR, YRRY, YRRR, RRYR, RRRR, RRRY.
এই ক্ষেত্রগুলো থেকে আমরা অনুমান করতে পারি যে এটি একটি ফিবোনাচ্চি সিরিজ যার প্রথম উপাদান ২ এবং দ্বিতীয় উপাদান ৩।
আমাদের লজিকের বাস্তবায়ন চিত্রিত করার প্রোগ্রাম,
উদাহরণ
#include <iostream> using namespace std; int colorSteps(int n) { int first = 2; int next = 3; for (int i = 3; i <= n; i++) { next = first + next; first = next - first; } return next; } int main(){ int n = 6; cout<<"সিঁড়ি রঙ করার পদ্ধতির সংখ্যা "<<n<<" ধাপ হল "<<colorSteps(n); return 0; }
আউটপুট
সিঁড়ি রঙ করার পদ্ধতির সংখ্যা ৬ ধাপ হল 21
