折半法求x的n次方

blackfur

比如mypow(x, ，第一次循環(huán)算出x·x=x2，第二次循環(huán)算出x2·x2=x4，第三次循環(huán)算出4·x4=x8。這樣只需要三次循環(huán)，時(shí)間復(fù)雜度是Θ(lgn)。思考一下如果n不是2的整數(shù)次冪應(yīng)該怎么處理。請分別用遞歸和循環(huán)實(shí)現(xiàn)這個(gè)算法。

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. //遞歸法
   
5. double myPow(double x,int n){
   
6.     int y=0;
   
7.     if(n==1)return x;
   
8.     y=n/2;
   
9.     if((2*y)==n)
   
10.         return myPow(x,n/2)*myPow(x,n/2);
    
11.     else
    
12.         return x*myPow(x,(n-1)/2)*myPow(x,(n-1)/2);
    
13. }
    
14. 
    
15. //循環(huán)法
    
16. double myPow2(double x,int n){
    
17.     if(n==1)return x;
    
18. 
    
19.     int y=1,b=2,a=0;
    
20.     while(n>b){
    
21.         b*=2;
    
22.         y++;
    
23.     }
    
24.     if(n!=b){
    
25.         y--;
    
26.         a=n-b/2;
    
27.     }   
    
28. 
    
29.     double product=x*x;
    
30.     while(--y){
    
31.         product*=product;
    
32.     }
    
33.     while(a--){
    
34.         product*=x;
    
35.     }
    
36.     return product;
    
37. }
    
38. int main(){
    
39.     cout<<myPow2(2,8)<<endl;
    
40. }

復(fù)制代碼

re1ncu

遞歸法

1. double myPow(double x, int n)
   
2. {
   
3.         if (n <= 0) return 1.0;
   
4.         if (n == 1) return x;
   
5.         double halfX;
   
6.         halfX = myPow(x, n/2);
   
7.         return halfX * halfX * (n%2 ? x : 1.0);
   
8. }

復(fù)制代碼

re1ncu

非遞歸方法

1. double myPow2(double x, int n)
   
2. {
   
3.         if (n <= 0) return 1.0;
   
4.         if (n == 1) return x;
   
5.         int flag = 0; //用來記錄什么時(shí)候要多乘以一個(gè)x
   
6.         double half = 0.0; //用來記錄結(jié)果
   
7.         int tmpN = n;
   
8.         while (tmpN > 1)
   
9.         {
   
10.                 flag = 2 * flag + tmpN % 2;
    
11.                 tmpN /= 2;
    
12.         }
    
13.         half = x;
    
14.         while (tmpN < n)
    
15.         {
    
16.                 half *= half;
    
17.                 half *= (flag % 2) ? x : 1.0; //當(dāng)此時(shí)flag不是2的倍數(shù)時(shí)，表示要多乘一個(gè)x
    
18.                 tmpN *= 2;
    
19.                 tmpN += flag % 2;
    
20.                 flag /= 2;
    
21.         }
    
22.         return half;
    
23. }

復(fù)制代碼

bruceteen

依次查看 n 的二進(jìn)制形式上的各位
舉個(gè)例子，假設(shè) n 為 5（二進(jìn)制為101）
那么 x^5 == (1*x^4) * (0*x^2) * (1*x^1)

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. double foo( double x, unsigned n )
   
5. {
   
6.     double r = 1.0;
   
7.     for( double m=x; n; m*=m, n>>=1u )
   
8.     {
   
9.         if( n & 1u )
   
10.             r *= m;
    
11.     }
    
12.     return r;
    
13. }
    
14. 
    
15. int main()
    
16. {
    
17.     cout << foo(2.1,13) << endl;
    
18. 
    
19.     return 0;
    
20. }

復(fù)制代碼

blackfur

大哥，想問下怎樣寫簽名？我也想找工作^_^回復(fù) 4# bruceteen


   

bruceteen

blackfur 發(fā)表于 2013-10-26 18:24
大哥，想問下怎樣寫簽名？我也想找工作^_^回復(fù) 4# bruceteen

頁面最上端有個(gè)“設(shè)置”，然后是 個(gè)人資料\個(gè)人信息\個(gè)人簽名
不過，我貼了這么久，屁用沒有^_^