PTA-快速幂

要求实现一个递归函数，高效求ab(1≤a,b≤62,ab<263)。

函数接口定义：

long long int pow(int a, int b);

其中a 、b 是用户传入的参数。

裁判测试程序样例：

#include<iostream> 
using namespace std; 
long long int pow(int a, int b); //求a^b //输入整数a，b，求 a^b，处理到文件尾 
int main() { 
int a,b; 
while(cin>>a>>b) { 
cout<<pow(a,b)<<endl; 
} 
return 0; 
}

输入样例：

2 3
2 10

输出样例：

8
1024

分析：

1. 首先判断指数b是否为0，如果是，则返回1，因为任何数的0次方都是1。
2. 如果指数b为奇数，则递归计算a的b-1次方，然后将结果乘以a。这是因为a的奇数次方可以表示为a乘以a的(b-1)次方。
3. 如果指数b为偶数，则递归计算a的b/2次方，然后将结果乘以自身。这是因为a的偶数次方可以表示为(a的b/2次方)的平方。
4. 最终返回计算得到的结果。

C语言：

#include<iostream>
using namespace std;long long int pow(int a, int b) // 递归方式求a^b
{if (b == 0)return 1;if (b % 2 == 1) // 当b为奇数return a * pow(a, b - 1);else { // 当b为偶数long long int c = pow(a, b / 2);return c * c;}
}

总结：

 

这段代码利用了递归的思想，将一个复杂的问题（a的b次方）分解为更小的子问题（a的(b-1)次方或a的b/2次方）。然后逐步递归求解子问题，最终得到原问题的解。此外，代码中还利用了递归终止条件（当b为0时），确保递归过程能够终止并返回结果。