- 论坛徽章:
- 0
|
比如mypow(x, ,第一次循环算出x·x=x2,第二次循环算出x2·x2=x4,第三次循环算出4·x4=x8。这样只需要三次循环,时间复杂度是Θ(lgn)。思考一下如果n不是2的整数次幂应该怎么处理。请分别用递归和循环实现这个算法。- #include<iostream>
- using namespace std;
- //递归法
- double myPow(double x,int n){
- int y=0;
- if(n==1)return x;
- y=n/2;
- if((2*y)==n)
- return myPow(x,n/2)*myPow(x,n/2);
- else
- return x*myPow(x,(n-1)/2)*myPow(x,(n-1)/2);
- }
- //循环法
- double myPow2(double x,int n){
- if(n==1)return x;
- int y=1,b=2,a=0;
- while(n>b){
- b*=2;
- y++;
- }
- if(n!=b){
- y--;
- a=n-b/2;
- }
- double product=x*x;
- while(--y){
- product*=product;
- }
- while(a--){
- product*=x;
- }
- return product;
- }
- int main(){
- cout<<myPow2(2,8)<<endl;
- }
复制代码 |
|