【題目鏈接】

ybt 1069：乘方計算
OpenJudge NOI 1.5 13:乘方計算

【題目考點】

1. 循環求冪

• 設變量r初始值為1：int r = 1;
• 循環n次每次循環中輸入變量a，將r的值設為r*a：r *= a;
• 循環結束后，r即為$a^n$

2. 調用乘方函數pow()（存在于<cmath>中）

double pow(double a, double b); 求$a^b$

3. （擴展）快速冪

一般循環求$a^n$時間復雜度為O(n)，快速冪求$a^n$時間復雜度為O(logn)

• 設結果變量r初始值為1：int r = 1;，
• 此時r需要乘以$a^n$才能得到最終結果
  • 如果此時n為奇數，那么r *= a;，此時r還需要乘以n-1個a，使n = n - 1。如果n是偶數，則跳過這一步。（由于n是奇數，整除運算 n/2 的值與 (n-1)/2的值是相等的，所以這一步中n = n - 1可以省略）
  • 此時r需要乘以$a^n$，已知$a^n=(a^2{)}^{\frac{n}{2}}$，所以使a *= a; n /= 2;后，r需要乘的仍然是$a^n$
• 重復上述步驟，直到n為0為止。r即為最終結果

4.（擴展）遞歸求冪

【題解代碼】

解法1：循環求冪

#include <bits/stdc++.h> using namespace std; int main() {int a, n, r = 1;cin>>a>>n;for(int i = 0; i < n; ++i)r *= a;cout<<r;return 0; }

解法2：調用<cmath>中pow()函數

#include<bits/stdc++.h> using namespace std; int main() {int a, n;cin>>a>>n;cout<<(int)pow(a, n);//cout直接輸出浮點數相當于用printf以%g形式輸出，當有效數字位數很多時會以科學計數法的形式輸出。轉為int型后就會直接輸出數字。return 0; }

解法3：快速冪

#include<bits/stdc++.h> using namespace std; int main() {int a, n, r = 1;//r:結果cin>>a>>n;while(n > 0){if(n % 2 == 1)r *= a;a *= a;n /= 2;}cout<<r;return 0; }

解法4：遞歸求冪

#include <bits/stdc++.h> using namespace std; int mi(int a, int n) {if(n == 0)return 1;elsereturn a * mi(a, n - 1); } int main() {int a, n, r = 1;cin>>a>>n;cout<<mi(a, n);return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1069：乘方计算 | OpenJudge NOI 1.5 13的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。