เลข Woodall (Woodall Number) ใน C++

ในโจทย์นี้ เราได้รับจำนวนหนึ่ง และงานของเราคือตรวจสอบว่าจำนวนนั้นเป็นเลข Woodall หรือไม่

เลข Woodall (Woodall number) เป็นประเภทของจำนวนพิเศษที่มีรูปแบบ:

Wₙ = n·2ⁿ - 1

เลข Woodall 5 ตัวแรกคือ 1, 7, 23, 63, 159

ตัวอย่าง

อินพุต

X = 159

เอาต์พุต

Yes

เพื่อแก้ปัญหานี้ เราจะสังเกตจำนวน ถ้าจำนวนเป็นเลขคู่ แล้วไม่สามารถเป็น Woodall ได้ และตรวจสอบจำนวนนั้น วิธีตรวจสอบ: บวกจำนวนนั้นด้วย 1 แล้วหารด้วย 2 ซ้ำๆ (recursively) หลังการหารแต่ละครั้ง นับจำนวนครั้งที่หารได้ และที่แต่ละจุดตรวจสอบว่าจำนวนครั้งเท่ากับจำนวนที่เหลืออยู่หรือไม่

โปรแกรมแสดงการนำโซลูชันของเราไปใช้

#include <iostream>
using namespace std;

bool isWoodallNumber(int x) {
    if (x % 2 == 0)
        return false;
    if (x == 1)
        return true;
    x += 1;
    int p = 0;
    while (x % 2 == 0) {
        x = x / 2;
        p++;
        if (p == x)
            return true;
    }
    return false;
}

int main() {
    int x = 1424;
    cout << x;
    (isWoodallNumber(x)) ? cout << " is a Woodall Number" : cout << " is not a Woodall Number";
    return 0;
}

ผลลัพธ์

1424 is not a Woodall Number