একটি পূর্ণসংখ্যা দেওয়া থাকলে, নিচের অপারেশনগুলো ব্যবহার করে সেটিকে ১-এ রূপান্তর করতে ন্যূনতম কত ধাপ লাগে তা বের করতে হবে।
সংখ্যা জোড় হলে ২ দিয়ে ভাগ করুন।
সংখ্যা বিজোড় হলে ১ যোগ বা বিয়োগ করুন।
উদাহরণ
ইনপুট − Number = 28
আউটপুট − 28 কে ১-এ রূপান্তরের ন্যূনতম ধাপ: 6
ব্যাখ্যা − ২৮/২=১৪, ১৪/২=৭, ৭+১=৮, ৮/২=৪, ৪/২=২, ২/২=১।
ইনপুট − Number = 9
আউটপুট − 9 কে ১-এ রূপান্তরের ন্যূনতম ধাপ: 4
ব্যাখ্যা − ৯-১=৮, ৮/২=৪, ৪/২=২, ২/২=১।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
রিকারসিভ পদ্ধতিতে ন্যূনতম অপারেশন বের করা হয়। জোড় হলে ২ দিয়ে ভাগ, বিজোড় হলে num-1 ও num+1-এর মধ্যে ন্যূনতম পথ বেছে নেওয়া হয়।
ইনপুট
Numberনিন।minWays(int num)ফাংশন ন্যূনতম অপারেশন ফেরত দেয়।tmp1, tmp2, minভেরিয়েবল নিন।যদি
num == 1হয়, ফেরত দিন ০।যদি জোড় হয়,
tmp1 = minWays(num/2); return 1+tmp1।যদি বিজোড় হয়,
tmp1 = minWays(num-1); tmp2 = minWays(num+1); min = min(tmp1, tmp2); return 1+min।
উদাহরণ কোড
#include <iostream>
using namespace std;
int minWays(int num){
int tmp1, tmp2, min;
if (num == 1){
return 0;
}
else if (num % 2 == 0){
tmp1 = minWays(num/2);
return (1 + tmp1);
}
else{
tmp1 = minWays(num - 1);
tmp2 = minWays(num + 1);
min = tmp1 < tmp2 ? tmp1 : tmp2;
return (1 + min);
}
}
int main(){
int Number = 21;
cout << "Minimum steps to reduce " << Number << " to 1: " << minWays(Number);
return 0;
}
আউটপুট
উপরের কোড রান করলে নিচের আউটপুট পাওয়া যাবে:
Minimum steps to reduce 21 to 1: 6
