এই সমস্যায়, আমাদের সিঁড়ি তৈরির জন্য দেওয়া ইটের সংখ্যা নির্দেশ করে একটি সংখ্যা দেওয়া হয়েছে। আমাদের কাজ হল f সিঁড়ির ধাপের সংখ্যার মধ্যে .
প্রদত্ত ইট ব্যবহার করে, আমাদের একটি সিঁড়ি ধাপ তৈরি করতে হবে। প্রতিটি ধাপে শেষ ধাপের থেকে আরও একটি ইট লাগে। আর প্রথম ধাপে দুটি ইট উঁচু। আমাদের ইট থেকে তৈরি করা যেতে পারে এমন ধাপের সংখ্যা খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
N = 40
আউটপুট
3
ব্যাখ্যা
ধাপ =1; ইট প্রয়োজন =2; মোট ব্যবহৃত ইট =2; ইট বাকি =38
ধাপ =2; ইট প্রয়োজন =3; মোট ব্যবহৃত ইট =5; অবশিষ্ট ইট =৩৫
ধাপ =3; ইট প্রয়োজন =4; মোট ব্যবহৃত ইট =9; ইট বাকি =31
ধাপ =4; ইট প্রয়োজন =5; মোট ব্যবহৃত ইট =14; ইট বাকি =26
ধাপ =5; ইট প্রয়োজন =6; মোট ব্যবহৃত ইট =20; ইট বাকি =20
ধাপ =6; ইট প্রয়োজন =7; মোট ব্যবহৃত ইট =২৭; ইট বাকি =13
ধাপ =7; ইট প্রয়োজন =8; মোট ব্যবহৃত ইট =৩৫; ইট বাকি =5
আর কোন ধাপ তৈরি করা যাবে না কারণ 8ম ধাপের জন্য 9টি ইটের প্রয়োজন এবং মাত্র 5টি বর্তমান।
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল একটি লুপ ব্যবহার করে, 2 থেকে শুরু করে ব্যবহৃত ইটের সংখ্যা N অতিক্রম না করা পর্যন্ত এবং তারপর শেষ ধাপের গণনা ফেরত দেওয়া।
এই সমাধানটি ভাল তবে সময়ের জটিলতাটি N ক্রম অনুসারে। এবং যোগফল সূত্র এবং বাইনারি অনুসন্ধান ব্যবহার করে সমাধানটি খুঁজে বের করার জন্য আরও ভাল পদ্ধতি তৈরি করা যেতে পারে।
আমাদের কাছে X আছে যা ব্যবহার করা ইটগুলির মোট গণনা যা সর্বদা (n*(n+1)) /2 এর চেয়ে তৈরি করা হয় কারণ আমাদের কাছে প্রয়োজনীয় সমস্ত ইটের যোগফল রয়েছে। এই ক্ষেত্রে, আমাদের কাছে দুটি মান থেকে একটি সমাধান আছে যা মধ্য এবং মধ্য - 1 থেকে পাওয়া যায়।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findStairCount(int T){
int low = 1;
int high = T/2;
while (low <= high) {
int mid = (low + high) / 2;
if ((mid * (mid + 1)) == T)
return mid;
if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T)
return mid - 1;
if ((mid * (mid + 1)) > T)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main(){
int N = 60;
int stepCount = findStairCount(2*N);
if (stepCount != -1)
stepCount--;
cout<<"The number of stair steps that can be made is "<<stepCount;
return 0;
} আউটপুট
The number of stair steps that can be made is 9
