【分治】快速幂运算-递归与非递归方法
<center>
提交: 14 解决: 9
[提交][状态][讨论版] </center>
问题 Q: 【分治】快速幂运算
时间限制: 1 Sec 内存限制: 128 MB提交: 14 解决: 9
[提交][状态][讨论版] </center>
题目描述
邪狼：“老大，好像还是不够油钱啊？”
修罗王：“看来只好用我的独门绝技----能力增持术了。”
邪狼：“听说能量增持数很霸道的？”
修罗王：“没错，假设初始燃油能提供的能量为X，当我对它进行能量增持n秒后，该然后的能量将达到X n”
邪狼：“这么强大的技能啊，简直逆天了，不过怎么之前不见老大用过？”
修罗王：“偶尔偷偷用几次没关系，经常用，燃油公司会找我麻烦的。”
现已知X和n，试计算X n的值。
修罗王：“看来只好用我的独门绝技----能力增持术了。”
邪狼：“听说能量增持数很霸道的？”
修罗王：“没错，假设初始燃油能提供的能量为X，当我对它进行能量增持n秒后，该然后的能量将达到X n”
邪狼：“这么强大的技能啊，简直逆天了，不过怎么之前不见老大用过？”
修罗王：“偶尔偷偷用几次没关系，经常用，燃油公司会找我麻烦的。”
现已知X和n，试计算X n的值。
输入
两个正整数，即X和n，其中X≥0，n≥0
输出
一个整数，即结果，保证结果不超过整型范围。
样例输入
3 2
样例输出
9
直接上代码：
非递归：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int main() { int x; int mi; int n; while(scanf("%d %d",&x,&n)!=EOF){ mi=x; if(n==0){ printf("1\n"); continue; } for(int i=1;i<n;){ if(i<n/2){ mi*=mi; i*=2; }else{ mi*=x; i+=1; } } printf("%d\n",mi); mi=0; } return 0; }
递归：
//if判断里面，n==2,n==3,可以不写。
#include <iostream> #include <cstdio> using namespace std; int mi(int x,int n){ if(n==0){ return 1; } if(n==1){ return x; } if(n==2){ return x*x; } if(n==3){ return x*x*x; } if(n%2==0){ return mi(x,n/2)*mi(x,n/2); } if(n%2!=0){ return mi(x,(n-1)/2)*mi(x,(n-1)/2)*x; } } int main() { int x; int n; int jieguo; while(scanf("%d %d",&x,&n)!=EOF){ jieguo=mi(x,n); printf("%d\n",jieguo); } return 0; }
