นับขั้นตอนลด N เป็น 1 ตามกฎกำหนด ใน C++

ได้รับจำนวน N ต้องการนับขั้นตอนลด N ให้เหลือ 1 ตามกฎ:

1. ถ้า N เป็นกำลังสอง: N = N/2
2. มิฉะนั้น: N = N - (กำลังสองที่ใกล้ที่สุดและน้อยกว่า N)

ตัวอย่าง

อินพุต: N = 20

เอาต์พุต: 3

ขั้นตอน: 20→4 (20-16), 4→2 (4/2), 2→1 (2/2)

อินพุต: N = 32

เอาต์พุต: 5

ขั้นตอน: 32→16→8→4→2→1 (หาร 2 ทุกขั้นตอน)

แนวทาง

• ตรวจสอบกำลังสอง: ceil(log2(n)) == floor(log2(n))
• ถ้าใช่: n /= 2
• ถ้าไม่: x = floor(log2(n)), n -= 2ˣ
• นับขั้นตอนจน n == 1

ตัวอย่างโค้ด C++

#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