Cách tìm lũy thừa của số cho trước bằng backtracking C#

Tạo hàm FindPower nhận số x và n, trong đó x là cơ số, n là số mũ. Nếu n chẵn thì tính x*x, nếu lẻ thì nhân kết quả với x*x. Tiếp tục gọi đệ quy cho đến khi n bằng 0.

Ví dụ: 2^8 = 2*2*2*2*2*2*2*2 = 256.

Ví dụ

using System;

namespace ConsoleApplication
{
    public class BackTracking
    {
        public int FindPower(int x, int n)
        {
            int result;
            if (n == 0)
            {
                return 1;
            }
            result = FindPower(x, n / 2);
            if (n % 2 == 0)
            {
                return result * result;
            }
            else
            {
                return x * result * result;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BackTracking b = new BackTracking();
            int res = b.FindPower(2, 8);
            Console.WriteLine(res);
        }
    }
}

Kết quả

256

Giải thích: Thuật toán lũy thừa nhanh (Exponentiation by Squaring) đệ quy. Độ phức tạp O(log n) thay vì O(n). Cơ sở: x^n = (x^(n/2))^2 nếu n chẵn, x * (x^(n/2))^2 nếu n lẻ.