n'th সিঁড়ি পৌঁছানোর উপায় গণনা

এখানে n সিঁড়ি আছে৷ ১ম থেকে ১ম সিঁড়িতে একজন যাবেন। তিনি এক ধাপে সর্বোচ্চ কতটি সিঁড়ি পার হতে পারবেন তাও দেওয়া আছে। এই তথ্য দিয়ে, আমাদের n'th সিঁড়িতে যাওয়ার সম্ভাব্য উপায় খুঁজে বের করতে হবে।

আসুন বিবেচনা করা যাক প্রতিটি ধাপে একজন সর্বোচ্চ দুটি সিঁড়ি অতিক্রম করতে পারে। তাই আমরা এই সমস্যা সমাধানের জন্য পুনরাবৃত্তিমূলক সম্পর্ক খুঁজে পেতে পারি। কেউ (n-1)'তম সিঁড়ি থেকে বা (n-2)'তম সিঁড়ি থেকে n'ম সিঁড়িতে যেতে পারে। সুতরাং উপায়(n) =উপায়(n-1) + উপায়(n-2)।

ইনপুট এবং আউটপুট

ইনপুট:সিঁড়ির সংখ্যা, বলুন 10টি সর্বোচ্চ সংখ্যক সিঁড়ি যা এক ধাপে লাফানো যেতে পারে, বলুন 2আউটপুট:সিঁড়ির সংখ্যা লিখুন:10একজন ব্যক্তি উঠতে পারে এমন সর্বাধিক সিঁড়ি প্রবেশ করান:2 পৌঁছানোর উপায়গুলির সংখ্যা:89

অ্যালগরিদম

সিঁড়ি ক্লিম্পওয়েস(সিঁড়ি, সর্বোচ্চ)

ইনপুট - সিঁড়ি সংখ্যা, একক ধাপে সর্বোচ্চ সিঁড়ি লাফ।

আউটপুট - পৌঁছানোর সম্ভাব্য উপায়ের সংখ্যা।

সিঁড়ি সংখ্যা গণনা [0] :=1 গণনা [0] :=1 এর জন্য i :=2 থেকে সিঁড়ি -1, গণনা করুন [i] :=0 এর জন্য j =1 থেকে i এবং j <=সর্বোচ্চ; গণনা করতে হবে 
উদাহরণ
 
#includeনেমস্পেস ব্যবহার করে std;int stairClimbWays(int stair, int max) { int count[সিঁড়ি]; //বটম আপ মেনার কাউন্ট ব্যবহার করে ফলাফলের সিঁড়ি পূরণ করুন[0] =1; //যখন 0 বা 1টি সিঁড়ি থাকে, 1 উপায়ে ওঠার সংখ্যা গণনা[1] =1; জন্য (int i=2; i<সিঁড়ি; i++) { // সিঁড়ি 2 থেকে উচ্চতর গণনার জন্য [i] =0; (int j=1; j<=max &&j<=i; j++) গণনা[i] +=গণনা[i-j]; } রিটার্ন কাউন্ট [সিঁড়ি-১];}int countWays(int stair, int max) { //ব্যক্তি এক সময়ে 1,2,...সর্বোচ্চ সিঁড়ি উঠতে পারে () { int stair, max; cout <<"সিঁড়ির সংখ্যা লিখুন:"; cin>> সিঁড়ি; cout <<"সর্বোচ্চ সিঁড়ি প্রবেশ করুন একজন ব্যক্তি আরোহণ করতে পারেন:"; cin>> সর্বোচ্চ; cout <<"পৌছানোর উপায়ের সংখ্যা:" < 
আউটপুট
 
সিঁড়ির সংখ্যা লিখুন:10 একজন ব্যক্তি আরোহণ করতে পারেন সর্বোচ্চ সিঁড়ি প্রবেশ করুন:2 পৌঁছানোর উপায়ের সংখ্যা:89