আমাদের একটি সংখ্যা দেওয়া হয়েছে। লক্ষ্য হল নিয়মগুলি অনুসরণ করে সংখ্যাটিকে 1 এ কমাতে প্রয়োজনীয় পদক্ষেপের সংখ্যা গণনা করা -
-
যদি সংখ্যাটি 2 এর শক্তি হয়, তাহলে এটিকে অর্ধেক কমিয়ে দিন।
-
অন্যথায় এটিকে N-তে কমিয়ে দিন (2 এর নিকটতম শক্তি যা N-এর চেয়ে কম)।
ধাপ 1-এর জন্য, আমরা পরীক্ষা করব N এর শক্তি 2 আছে কিনা, ceil(log2(N)), ফ্লোর(log2(N)) একই ফলাফল দেয় কিনা তা পরীক্ষা করে। যদি হ্যাঁ হয় তাহলে N=N/3, অপারেশনের সংখ্যা বৃদ্ধি।
যদি ধাপ 1 এর ফলাফল মিথ্যা হয় তবে আমরা ধাপ 2 সম্পাদন করব এবং N থেকে N থেকে 2 কমের নিকটতম শক্তি বিয়োগ করব। N থেকে 2 কমের নিকটতম শক্তি হিসাবে গণনা করা হবে −
x=floor(log2(N)) → যখন N 2 এর শক্তি না হয়, log2(N) ফ্লোটিং পয়েন্টের মান দেয়, ফ্লোর এটিকে N-এর চেয়ে কম কাছাকাছি পূর্ণসংখ্যাতে কমিয়ে দেয়।
এখন N=N- pow(2,x) → pow(2,x) N থেকে 2 কম পাওয়ার দেবে। N কমিয়ে দিন।
উদাহরণ দিয়ে বোঝা যাক।
ইনপুট − N=20
আউটপুট -:প্রয়োজনীয় ধাপের সংখ্যা − 3
ব্যাখ্যা − N=20
20 is not power of 2. Step 2. Reduce nearest power of 2 less than N from N. N=20- 16=4. Count=1. 4 is power of 2. Step 1. Reduce N to its half. N=4/2=2. Count=2. 2 is power of 2. Step 1. Reduce N to its half. N=2/2=1. Count=3. N is 1 total step count=3.
ইনপুট − N=32
আউটপুট প্রয়োজনীয় ধাপের সংখ্যা − 5
ব্যাখ্যা − N=32
32 is power of 2. Step 1. Reduce N to its half. N=32/2=16. Count=1. 16 is power of 2. Step 1. Reduce N to its half. N=16/2=8. Count=2. 8 is power of 2. Step 1. Reduce N to its half. N=8/2=4. Count=3. 4 is power of 2. Step 1. Reduce N to its half. N=4/2=2. Count=4. 2 is power of 2. Step 1. Reduce N to its half. N=2/2=1. Count=5. N is 1 total step count=5.
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
-
একটি পূর্ণসংখ্যা মান সংরক্ষণের জন্য আমরা একটি পূর্ণসংখ্যা N নিই।
-
ফাংশন stepCount(int n) N নেয় এবং এটিকে 1 এ কমাতে প্রয়োজনীয় ধাপের গণনা ফেরত দেয়।
-
0 হিসাবে পদক্ষেপের প্রাথমিক গণনা নিন।
-
এখন যখন(n!=1) n এর মান অনুযায়ী 1, এবং 2 উভয় ধাপই সম্পাদন করুন।
-
যদি n এর শক্তি 2 হয় ( ceil(log2(n))==floor(log2(n)) সত্য হবে , n কমিয়ে অর্ধেক করুন। সংখ্যা বৃদ্ধি।
-
যদি 2 এর শক্তি না হয় তবে n কে pow(2,x) দ্বারা কমিয়ে দিন যেখানে x ফ্লোর(log2(n))। সংখ্যা বৃদ্ধি।
-
যখন লুপ শেষ হবে তখন গণনায় সঞ্চালিত অপারেশনের সংখ্যা থাকবে।
-
পছন্দসই ফলাফল হিসাবে রিটার্ন গণনা।
উদাহরণ
#include <iostream>
#include <math.h>
using namespace std;
// Function to return number of steps for reduction
int stepCount(int n){
int count=0;
while(n!=1){
if(ceil(log2(n))==floor(log2(n))) //if n is power of 2 then this is true{
n=n/2; //reduce n to half
count++;
} else {
int x=floor(log2(n)); //floor value
n=n-(pow(2,x)); //2^x is nearest power of 2 which is less than n
count++;
}
}
return count;
}
int main(){
int N = 96;
cout <<"Count of steps required to reduce N to 1:"<<stepCount(N);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of steps required to reduce N to 1:6
