ধরুন আমাদের একটি সংখ্যা n আছে। আমরা এই অপারেশনগুলির যেকোন একটিকে নির্বিচারে সংখ্যায় সম্পাদন করি -
-
যখন n 2 দ্বারা বিভাজ্য হয় তখন n/2 দিয়ে n প্রতিস্থাপন করুন
-
যখন n 3 দ্বারা বিভাজ্য হয় তখন n কে 2n/3 দিয়ে প্রতিস্থাপন করুন
-
যখন n 5 দ্বারা বিভাজ্য হয় তখন n কে 4n/5 দিয়ে প্রতিস্থাপন করুন
নম্বর 1 করার জন্য আমাদের ন্যূনতম সংখ্যক চালগুলি গণনা করতে হবে। যদি সম্ভব না হয় তবে -1 ফেরত দিন।
সুতরাং, যদি ইনপুটটি n =10 এর মত হয়, তাহলে আউটপুট হবে 4, কারণ 5 পেতে n/2 ব্যবহার করুন, তারপর 4 পেতে 4n/5, তারপর n/2 আবার 2 এবং n/2 ব্যবহার করুন। 1.
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
m :=0 যখন n 1 এর সমান না হয়, তাহলে করুন:যদি n mod 2 0 এর সমান হয়, তাহলে:n :=n / 2 (m 1 দ্বারা বাড়ান) অন্যথায় যখন n mod 3 0 এর সমান হয়, তখন :n :=n / 3 m :=m + 2 অন্যথায় যখন n mod 5 0 এর মত হয়, তখন:n :=n / 5 m :=m + 3 অন্যথায় m :=-1 লুপ্রেটার্ন m<থেকে বেরিয়ে আসুন /প্রে>উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#includeনেমস্পেস ব্যবহার করে std;int solve(int n) { int m =0; যখন (n !=1) { যদি (n % 2 ==0) { n =n / 2; m++; } অন্যথায় যদি (n % 3 ==0) { n =n / 3; m +=2; } অন্যথায় যদি (n % 5 ==0) { n =n / 5; m +=3; } অন্য { মি =-1; বিরতি } } ফেরত m;} int main() { int n =10; cout < ইনপুট
10আউটপুট
4