সি++-এ নির্দিষ্ট নিয়মে N কে ১ এ কমাতে প্রয়োজনীয় ধাপ গণনা

একটি সংখ্যা N দেওয়া আছে। লক্ষ্য হল নিচের নিয়ম মেনে N কে ১ এ কমাতে কত ধাপ লাগে তা গণনা করা:

যদি সংখ্যা ২-এর ঘাত হয়, তা তার অর্ধেক করে দেওয়া হয়।
অন্যথায় N থেকে N-এ চেয়ে ছোট সবচেয়ে নিকটবর্তী ২-এর ঘাত বিয়োগ করা হয়।

ধাপ ১: N ২-এর ঘাত কিনা চেক করা হয় ceil(log2(N)) == floor(log2(N)) দিয়ে। সত্য হলে N=N/2, অপারেশন কাউন্ট বাড়ানো হয়।

মিথ্যা হলে ধাপ ২: x = floor(log2(N)) (যখন N ২-এর ঘাত নয়, log2(N) ফ্লোটিং পয়েন্ট দেয়, floor নিকটবর্তী ইন্টিজার দেয়)। N = N - pow(2,x)। pow(2,x) হল N-এ চেয়ে ছোট নিকটবর্তী ২-এর ঘাত। অপারেশন কাউন্ট বাড়ানো হয়।

উদাহরণ

ইনপুট: N=20

আউটপুট: প্রয়োজনীয় ধাপ: ৩

ব্যাখ্যা: 20 ২-এর ঘাত নয় → 20-16=4 (count=1). 4 ২-এর ঘাত → 4/2=2 (count=2). 2 ২-এর ঘাত → 2/2=1 (count=3).

ইনপুট: N=32

আউটপুট: প্রয়োজনীয় ধাপ: ৫

ব্যাখ্যা: 32→16→8→4→2→1, প্রতিটি ধাপে অর্ধেক। মোট ৫ ধাপ।

অ্যাপ্রোচ

N ইন্টিজার ভেরিয়েবলে।
stepCount(int n) ফাংশন N গ্রহণ করে ১ এ কমাতে প্রয়োজনীয় ধাপ রিটার্ন করে।
প্রাথমিক count=0।
while(n!=1) লুপে দুটি ধাপ অনুসরণ করা হয়।
২-এর ঘাত হলে n/=2, count++। নয় হলে n -= pow(2, floor(log2(n))), count++।

উদাহরণ কোড

#include <iostream>
#include <math.h>
using namespace std;

int stepCount(int n) {
    int count = 0;
    while (n != 1) {
        if (ceil(log2(n)) == floor(log2(n))) {
            n = n / 2;
            count++;
        } else {
            int x = floor(log2(n));
            n = n - pow(2, x);
            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