快速冪運算（反復平方法）
先來看一道題目：題目鏈接
本題代碼在最后哦~
快速冪運算的優勢：
1.可用來算大數的冪的一種演算法，
2.其時間復雜度為 O(log?N)， 如果我們使用回圈來計算的話，那么時間復雜度就是 O(n) ，與樸素的O(N)相比效率有了極大的提高，
快速冪演算法的核心思想：每一步都把指數分成兩半，而相應的底數做平方運算，
如這張圖片上所寫的計算2的n次方所示，可以進行對底數做平方，冪做除2運算，
演算法如何實作？
首先我們要知道對于冪是偶數時我們可以這樣操作，如果冪是奇數呢？
如計算123的234次方如下圖所示：
哦，原來我們遇到奇數冪時可以將底數提取出來一個，冪就會變為偶數， 然后就可以進行我們的快速冪操作，
下面來看代碼實作：
1.用遞回實作：
int QuickPower(int a, int n)
{
int ans;
if (n == 0)
{
ans = 1;//結束條件
}
else
{
ans = QuickPower(a*a, n / 2);//遞回呼叫
if (n % 2 == 1)//n為奇數
{
ans *= a;
}
}
return ans;
}
2.回圈實作
int QuickPower(int a, int n)
{
int ans = 1;
while (n)
{
if (n % 2)//奇數情況
{
ans = ans*a;
}
a = a*a;//底數平方
n = n / 2;//指數減半
}
return ans;
}
我們回過頭來看看這道人見人愛的A^B
AC代碼如下：
#include <stdio.h>
int QuickPower(int a, int n)
{
int ans = 1;
while (n)
{
if (n % 2)//奇數情況
{
ans = ans*a;
}
a = a*a;//底數平方
n = n / 2;//指數減半
}
return ans;
}
int main()
{
int a, b;
while (~scanf("%d %d", &a, &b))
{
int ret = QuickPower(a, b);
printf("%d\n", ret%1000);//取三位哦~
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/267415.html
標籤：其他
上一篇：AcWing 104. 貨倉選址
下一篇：訓練賽題解