เขียนโปรแกรมคำนวณ pow(x, n) ใน C++

โจทย์

ได้รับจำนวนเต็ม x และ n ต้องเขียนโปรแกรมคำนวณ xⁿ (x ยกกำลัง n)

ตัวอย่าง

Input: x = 5, n = 3
Output: 125

วิธีแก้ปัญหา: Exponentiation by Squaring (Fast Power)

แทนที่จะคูณซ้ำ n ครั้ง (O(n)) ใช้วิธีแบ่งครึ่งกำลัง (divide and conquer):

• xⁿ = (x^n/2)² หาก n เป็นเลขคู่
• xⁿ = x × (x^n/2)² หาก n เป็นเลขคี่
• Base case: x⁰ = 1

Time complexity: O(log n)

โค้ดตัวอย่าง (Recursive)

#include <iostream>
using namespace std;

float myPow(float x, int y) {
    if (y == 0) return 1;
    
    float temp = myPow(x, y / 2);
    
    if (y % 2 == 0) {
        return temp * temp;
    } else {
        if (y > 0) {
            return x * temp * temp;
        } else {
            return (temp * temp) / x;  // negative exponent
        }
    }
}

int main() {
    float x = 5;
    int n = 7;
    cout << x << " raised to the power " << n << " is " << myPow(x, n);
    return 0;
}

ผลลัพธ์

5 raised to the power 7 is 78125

โค้ดตัวอย่าง (Iterative) - แนะนำให้ใช้

#include <iostream>
using namespace std;

double myPowIterative(double x, long long n) {
    if (n == 0) return 1.0;
    
    bool negative = n < 0;
    if (negative) n = -n;
    
    double result = 1.0;
    while (n > 0) {
        if (n & 1) result *= x;
        x *= x;
        n >>= 1;
    }
    
    return negative ? 1.0 / result : result;
}

int main() {
    double x = 2.0;
    long long n = -3;
    cout << x << "^" << n << " = " << myPowIterative(x, n);
    return 0;
}

ผลลัพธ์

2^-3 = 0.125

การจัดการกรณีพิเศษ

Modular Exponentiation (สำหรับ competitive programming)

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

สรุป

Fast Exponentiation (Exponentiation by Squaring) เป็นอัลกอริทึมมาตรฐานสำหรับคำนวณกำลังอย่างมีประสิทธิภาพ O(log n) ใช้ทั้ง recursive และ iterative ได้ แบบ iterative แนะนำมากกว่าสำหรับ production code เพราะไม่มี stack overflow risk