目錄

創(chuàng)新互聯(lián)是專業(yè)的薛城網站建設公司，薛城接單;提供成都網站建設、網站制作,網頁設計,網站設計,建網站,PHP網站建設等專業(yè)做網站服務;采用PHP框架,可快速的進行薛城網站開發(fā)網頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網站,專業(yè)的做網站團隊,希望更多企業(yè)前來合作!

1.?數(shù)值的整數(shù)次方

1.1?運行超時的思路

1.2?思路一:? 快速冪 (遞歸實現(xiàn))

1.3?思路二:? 快速冪 (迭代實現(xiàn))

---

1.?數(shù)值的整數(shù)次方

原題鏈接:

劍指 Offer 16. 數(shù)值的整數(shù)次方 - 力扣（LeetCode）https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

我們都知道,? 在C語言的一根庫中有一個pow函數(shù)可以用來求一個數(shù)的乘方,? 本題就是要求實現(xiàn)類似于pow的功能.? 要求實現(xiàn)特定庫函數(shù)(特別是處理數(shù)值和字符串的函數(shù))的功能是一類常見的面試題。這就要求我們在平時編程的時候除了能熟練使用庫函數(shù),更重要的是要理解庫函數(shù)的實現(xiàn)原理。

1.1?運行超時的思路

想必大家第一個想到的思路就是循環(huán).??我們對輸入的冪指數(shù)進行特殊處理:? 使得冪指數(shù)大于0.? 然后利用for循環(huán)將底數(shù)乘到最終結果上就可以了!? 很遺憾Leetcode?并不想讓你這么做,? 面試官也不希望看到這種解法.

double myPow(double x, int n){
    //保存結果的變量
    double result = 1.0;
    //為啥用long int 后面講
    long int a = n;
    //如果冪指數(shù)小于0, 取絕對值, 2的-1次方就等于二分之一的一次方嘛
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    //循環(huán)將底數(shù)乘到結果上
    int i = 0;
    for(i = 0;i< a;i++)
    {
        result *= x;
    }
    return result;
}

1.2?思路一:? 快速冪 (遞歸實現(xiàn))

快速冪的本質就是分治,? 大家細細品味哈.?

?以上方法不可行,? 我們可以換一種思路考慮:? 例如,? 我們的目標是求出一個數(shù)字的32次方，如果我們已經知道了它的16次方，那么只要在16次方的基礎上再平方一次就可以了。而16次方是8次方的平方。這樣以此類推，我們求32次方只需要做5次乘法:? 先求平方，在平方的基礎上求4次方，在4次方的基礎上求8次方，在8次方的基礎上求16次方，最后在16次方的基礎上求32次方。對于奇數(shù)次方,?我們只需要拿出一個底數(shù)出來即可.?
也就是說，我們可以用如下公式求a?的n次方:

同上面一樣我們需要對輸入的冪指數(shù)進行處理:??

將冪指數(shù)保存在一個變量,? 例如 a?中,? 當冪指數(shù)小于 0?時,? 我們就令?a = -a,? 底數(shù)x = 1 /?x,? 就相當于對冪指數(shù)取絕對值,? 然后把冪指數(shù)的負號作用到底數(shù)上,? 2 的 -1 次方就等于 1/2?的 1?次方嘛.??

注意:? 保存冪指數(shù)的變量必須選用存儲范圍更大的 long?int,? 我們都知道 int 的范圍是?

當我們輸入的冪指數(shù)為 - (2的31次方時),? 取絕對值后?int?類型是存不下這個數(shù)的.?

解題的時間復雜度:? O(logN),? 因為是遞歸,? 函數(shù)調用需要函數(shù)棧幀,? 故空間復雜度:? O(logN).

double recurison(double x, long int n)
{
    //遞歸的結束條件, 任何數(shù)的0次冪都等于1(0除外)
    if(n==0)
    {
        return 1;
    }
    // 將冪指數(shù)整除2, 但是我們選用位運算提高效率
    double result = recurison(x, n>>1);
    result *= result;
    //判斷奇偶, 奇數(shù)就乘以一個底數(shù), 同樣使用位運算提高效率
    if((n&1)==1)
    {
        result*=x;
    }
    return result;
}

double myPow(double x, int n){
    double result;
    //對指數(shù)進行處理
    long int a = n;
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    return recurison(x, a);
}

1.3?思路二:? 快速冪 (迭代實現(xiàn))

還是以具體的例子來看:? 我們一開始還是對冪指數(shù)進行處理使它為整數(shù)哈,? 當冪指數(shù)n為偶數(shù),? 例如x ^ 8? 我們先算?x *?x =?x ^ 2,? 再算x ^ 2?*?x ^ 2 =?x ^ 4,? 最后算x ^ 4 *?x ^ 4 = x ^ 8.?對于奇數(shù)呢,? 我們將指數(shù)進行拆分,? 例如?x ^ 10,? 指數(shù)10 = 1 + 4 + 8? =?2 ^ 0 + 2 ^ 2?+ 2 ^ 3,? 即?

x ^ 10 =?x ^ 1 *?x ^ 4 *?x ^ 8

依次類推,?直到將冪指數(shù)的二進制遍歷完畢,? 顯然result?乘上的值在每一遍歷一個二進制位時都要逐步遞增:??

偶數(shù)自然不用說,? 也是滿足此規(guī)律的.

double myPow(double x, int n){
    //保存結果的變量
    double result = 1.0;
    //對指數(shù)進行處理
    long int a = n;
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    //遍歷指數(shù)的二進制位, 對指數(shù)逐步右移即可
    while(a)
    {
        //如果二進制位為1, 乘上當時的x的二進制位值的次冪
        if((a&1)==1)
        {
            result *= x;
        }
        //下一個二進制位的, x的二進制位值的次冪
        x = x * x;
        //將a右移
        a >>= 1;
    }
    return result;
}

由于作者表達能力有限,? 思路可能不是很清晰,? 望大佬們海涵.

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站名稱：劍指offer----C語言版----第十一天-創(chuàng)新互聯(lián)
文章分享：http://weahome.cn/article/hhhse.html