Căn bậc 5 của một số trong C++

Cho số N. Nhiệm vụ: tìm phần nguyên của căn bậc 5 của N.

Căn bậc 5: Số a mà a^5 = N.

Ví dụ:

Đầu vào: N = 325

Đầu ra: 3

Giải thích: Căn bậc 5 của 325 ≈ 3.179, phần nguyên = 3.

Phương pháp giải

Cách 1: Duyệt tuyến tính - Tăng a từ 1 cho đến khi a^5 >= N, trả về a-1.

Cách 2: Tìm kiếm nhị phân - Tìm a trong [1, n] sao cho a^5 <= n < (a+1)^5. O(log n).

Chương trình minh họa (Cách 1)

Ví dụ

#include <iostream>
using namespace std;

int calcFifthRoot(int n) {
    if (n == 0 || n == 1)
        return n;
    int a = 0;
    for (a = 1; a * a * a * a * a < n; a++) {}
    return (a - 1);
}

int main() {
    int n = 325;
    cout << "The Floor of fifth root of " << n << " is " << calcFifthRoot(n);
    return 0;
}

Kết quả

The Floor of fifth root of 325 is 3

Chương trình minh họa (Cách 2 - nhị phân)

Ví dụ

#include <iostream>
using namespace std;

int calcFifthRoot(int n) {
    if (n == 0 || n == 1)
        return n;
    int start = 1, end = n, root = 0;
    while (start <= end) {
        int a = (start + end) / 2;
        long int apowfive = a * a * a * a * a;
        if (apowfive == n)
            return a;
        if (apowfive < n) {
            start = a + 1;
            root = a;
        } else
            end = a - 1;
    }
    return root;
}

int main() {
    int n = 250;
    cout << "The floor of fifth root of " << n << " is " << calcFifthRoot(n);
    return 0;
}

Kết quả

The floor of fifth root of 250 is 3