計算2的n次方程序設計思路?通常，計算一個數的整數次方的簡單粗暴的方法是用一個循環，其時間複雜度為long(n);，下面我們就來聊聊關于計算2的n次方程序設計思路?接下來我們就一起去了解一下吧!

計算2的n次方程序設計思路

通常，計算一個數的整數次方的簡單粗暴的方法是用一個循環，其時間複雜度為long(n);

double pow(double x, int n) // 這裡沒有考慮n為負數的情況 { double ret = 1.0; for(int i=1;i<=n;i ) ret *= x; return ret; }

簡單直接粗暴的思路往往不是最佳解法，如我們計算，不會機械地計算= 2*2*2*2*2*2*2*2*2*2 = 1024

化簡為=4*8*=32*32=1024

來計算就要簡單些。

對于,其中的n可以可以表示為序列：的某個組合之和，也就是：

… (b==0 || b==1)

(b==0 || b==1)

關于指數n的叠代關系，有點像10進制求二進制，如将一個十進制數打印出二進制位：

void intPrintBinary(int n) { if(n<=0) return; if(n!=0) { intPrintBinary(n/2); printf("%d",n%2); } }

計算一個數的整數次方，，有如下僞代碼：

double ret = 1; while(n>0{ if(n%2 == 1) // 相當于上述表達式中 (b==0 || b==1) ret *= x; // 連乘 n /=2； // 指數連續二分叠代 x *=2; // 相當于上述表達式中 x^2^i }

僞代碼轉換為代碼：

#include <stdio.h> double pow(double x,int n) { double ret = 1.0; while(n>0) { if(n%2==1) // 相當于上述分析中的 (b==0 || b==1) ret *= x; // 當b==1時，項的值叠代到結果中 x *= x; // 相當于上述分析中 x^2^i n /= 2; // 對應x^2^i，x以自身倍數叠代增長，n以二分自己減小 } return ret; } int main() { for(int i=1;i<100;i ) printf(".2f\n",pow(i i*.1,3)); getchar(); }

能以二分方法解決的問題的時間複雜度為O(long2n)，如上例，問題的邊界為(0,n)，以n /= 2來叠代n，直到n==0，叠代的次數為log2n。

-End-

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!