Bài 50 Leetcode: Pow(x, n)

Đề bài:

Viết hàm pow(x, n) để tính giá trị của x mũ n (tức là x^n).

Ví dụ 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Ví dụ 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Ví dụ 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

Ràng buộc:

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• n là một số nguyên.
• Hoặc x khác không hoặc n > 0.
• -10^4 <= x^n <= 10^4

Giải thích thuật toán bằng C ++

class Solution {
 public:
  double myPow(double x, long n) {
    if (n == 0)
      return 1;
    if (n < 0)
      return 1 / myPow(x, -n);
    if (n & 1)
      return x * myPow(x, n - 1);
    return myPow(x * x, n / 2);
  }
};

Đây là một giải thuật để tính giá trị của x mũ n (x^n) trong hàm `myPow`. Dưới đây là giải thích chi tiết về giải thuật:

1. Kiểm tra nếu n bằng 0, trả về 1. Điều này là do bất kỳ số nào mũ 0 đều bằng 1.

2. Kiểm tra nếu n âm, trả về kết quả của phép tính 1 chia cho myPow(x, -n). Điều này là do x mũ -n tương đương với 1 chia cho x^n.

3. Kiểm tra nếu n là số lẻ (n & 1 trả về true), trả về kết quả của phép tính x nhân với myPow(x, n – 1). Điều này tương đương với việc tính x^n bằng cách nhân x^(n-1) với x.

4. Trong trường hợp n là số chẵn, trả về kết quả của phép tính myPow(x * x, n / 2). Điều này tương đương với việc tính x^n bằng cách tính bình phương của x và nhân với x^(n/2).

Giải thuật sử dụng đệ quy để tính toán giá trị của x mũ n, tận dụng tính chất của luỹ thừa chẵn/lẻ để giảm số lần tính toán. Kết quả được trả về là giá trị của x^n.

Giải thích thuật toán bằng Java

class Solution {
  public double myPow(double x, long n) {
    if (n == 0)
      return 1;
    if (n < 0)
      return 1 / myPow(x, -n);
    if (n % 2 == 1)
      return x * myPow(x, n - 1);
    return myPow(x * x, n / 2);
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def myPow(self, x: float, n: int) -> float:
    if n == 0:
      return 1
    if n < 0:
      return 1 / self.myPow(x, -n)
    if n & 1:
      return x * self.myPow(x, n - 1)
    return self.myPow(x * x, n // 2)