蜜桃婷婷久久福利视频,日日欧美久久成人

二分求冪法是快速計(jì)算形如 $a^b$ 的求冪運(yùn)算的方法。樸素計(jì)算 $a^b$ 的方式是將 $a$ 連乘 $b$ 次，代碼如下：

int result = 1;
for (int i = 0; i != b; i++)
    result *= a;

這需要計(jì)算 $b$ 次，而實(shí)際真的需要運(yùn)算這么多次嗎？答案是不需要，利用二分求冪法，我們可以使運(yùn)算次數(shù)大大小于 $b$ 次。那么什么是二分求冪法呢？我們先考慮一個(gè)具體的計(jì)算： $a^{32} = \; ?$ 。

首先，我們需要想到： $a^{32} = a^{16} \times a^{16}$ 。這說明當(dāng)我們計(jì)算出 $a^{16}$ 的值后，再去計(jì)算 $a^{32}$ 的值并不需要再連乘 $a$ 十六次，我們只需要自乘一次 $a^{16}$ 即可，這便大大降低了運(yùn)算步驟。

如果我們想到了 $a^{32} = a^{16} \times a^{16}$ ，那么我們也可以很自然的進(jìn)一步想到 $a^{16} = a^{8} \times a^{8}$ ，這同樣大大簡(jiǎn)化了計(jì)算 $a^{16}$ 的步驟：當(dāng)我們得到 $a^8$ 的值時(shí)，只需再自乘一次 $a^8$ 即可得到 $a^{16}$ 的值，而無(wú)需連乘 8 次 $a$ 。繼續(xù)這樣推演下去，我們可以得到以下的式子：
$\begin{align} a^{32} &= a^{16} \times a^{16} \\[1ex] a^{16} &= a^{8} \times a^{8} \\[1ex] a^8 &= a^4 \times a^4 \\[1ex] a^4 &= a^2 \times a^2 \\[1ex] a^2 &= a \times a \\[1ex] a^1 &= a \end{align}$
我們可以發(fā)現(xiàn)，通過二分求冪的方法，僅需 6 次運(yùn)算即可得到結(jié)果，而在樸素求冪的方法中足足需要 32 次！

但我們發(fā)現(xiàn)一個(gè)問題：32 剛好是 2 的 5 次方，所以 32 可以一直被二分到 1 為止，如果失去這種特殊性，我們還可以使用二分求冪嗎？答案也是可以的，以計(jì)算 $a^{31}$ 為例：

$\begin{align*} a^{31} &= a^{16} \times a^{15} \\[1ex] &= a^{16} \times a^8 \times a^7 \\[1ex] &= a^{16} \times a^8 \times a^4 \times a^3 \\[1ex] &= a^{16} \times a^8 \times a^4 \times a^2 \times a^1 \end{align*}$

當(dāng)我們得到上面的拆分結(jié)果后，再計(jì)算 $a^{31}$ 就輕松多了。當(dāng)我們得到 $a$ 的值時(shí)，自乘一次即可得到 $a^2$ ，再自乘一次即可得到 $a^4$ ，再自乘一次得到 $a^8$ ，再自乘一次得到 $a^{16}$ ，我們最后將這些中間結(jié)果乘到一起就計(jì)算出了 $a^{31}$ 的值。利用二分求冪，計(jì)算出 $a^{31}$ 僅需要 5 次運(yùn)算，而樸素求冪足足需要 31 次！

現(xiàn)在我們已經(jīng)充分認(rèn)識(shí)到了二分求冪法的威力，但想要完全掌握這一方法，我們還需要攻克一個(gè)核心問題——如何正確的分解指數(shù)，使其可以滿足二分求冪的運(yùn)算過程（如上述對(duì) $a^{31}$ 的分解）。對(duì)于一般化的 $a^b$ ，我們可以這樣考慮：
$a^b = a^{b_1 + b_2 + b_3 + \cdots} = a^{b_1} \cdot a^{b_2} \cdot a^{b_3} \cdots \\[1ex] b_1 + b_2 + b_3 + \cdots = b \\[1ex] \lbrace b_1, b_2, b_3, \cdots \rbrace \subset \lbrace 1,2,4, 8, \cdots \rbrace = \lbrace 2^0, 2^1, 2^2, \cdots, 2^n \rbrace$

顯然，這樣分解出來(lái)的指數(shù) $b_1, b_2, b_3, \cdots$ 滿足二分求冪的運(yùn)算過程。因?yàn)?，在二分求冪過程中，從 $a$ 開始不斷自乘，我們可以得到： $a^1, a^2, a^4, a^8， \cdots$ ，所以，我們分解出來(lái)的 $a^{b_1}, a^{b_2}, a^{b_3}, \cdots$ 必須屬于自乘得到的序列，即指數(shù) $\lbrace b_1, b_2, b_3, \cdots \rbrace \subset \lbrace 1, 2, 4, 8, \cdots \rbrace$ ，而 $\lbrace 1, 2, 4, 8, \cdots \rbrace$ 又等于 $\lbrace 2^0, 2^1, 2^3, 2^4, \cdots \rbrace$ ，看到這里，我們只需要再邁出最后一步——聯(lián)想到二進(jìn)制，就可以完全掌握二分求冪法了。

對(duì)于任何一個(gè)指數(shù) $b$ ，我們可以將其轉(zhuǎn)化為二進(jìn)制形式，這個(gè)二進(jìn)制串中所有值為 1 的位置所代表的值，就是二分求冪法所需要的分解結(jié)果。現(xiàn)在用這樣的視角再次回顧之前的 $a^{31}$ ，指數(shù) $31$ 的二進(jìn)制形式為 $11111$ ，這個(gè)二進(jìn)制串從低位到高位每一個(gè) 1 的值如下：

$\begin{aligned} 2^0 &= 1 \\[1ex] 2^1 &= 2 \\[1ex] 2^2 &= 4 \\[1ex] 2^3 &= 8 \\[1ex] 2^4 &= 16 \\[1ex] \end{aligned}$

我們可以發(fā)現(xiàn)，這些值正好是分解后的結(jié)果，即 $a^{31} = a^{16} \times a^8 \times a^4 \times a^2 \times a^1$ ，然后就可以輕松的利用二分求冪法快速計(jì)算出結(jié)果了。

再分析一個(gè)具體的例子：計(jì)算 $a^{177}$ 的值。指數(shù) $177$ 的二進(jìn)制形式是 $10110001$ ，所有值為 1 的位置代表的值分別是：

$\begin{aligned} 2^0 &= 1 \\[1ex] 2^4 &= 16 \\[1ex] 2^5 &= 32 \\[1ex] 2^7 &= 128 \end{aligned}$

從而可以將 $a^{177}$ 分解為 $a^{128} \cdot a^{32} \cdot a^{16} \cdot a^1$ ，然后利用二分求冪，從 $a$ 開始，自乘一次得到 $a^2$ ，再自乘一次得到 $a^4$ ，以此類推，直到得到 $a^{128}$ 。這些中間結(jié)果中，對(duì)我們有用的是 $a, a^{16}, a^{32}, a^{128}$ ，我們把它們乘到一起，就計(jì)算出了 $a^{177}$ 的值。從程序運(yùn)行的角度來(lái)看，利用二分求冪，得到這個(gè)結(jié)果需要循環(huán) 8 次，而如果要在樸素求冪算法中得到這一結(jié)果，則需要運(yùn)行 177 次！顯然，要計(jì)算的冪指數(shù)越大，二分求冪的優(yōu)勢(shì)也就愈加明顯。

最后簡(jiǎn)單地用程序語(yǔ)言表達(dá)如何計(jì)算 $a^b$ ：

int fun(int a, int b) {
    int result = 1;
    while (b) {
        if (b % 2 == 1)
            result *= a;
        a *= a;
        b /= 2;
    }
    return result;
}

參考資料：

王道論壇編組.王道論壇計(jì)算機(jī)考研機(jī)試指南[M]. :, 2013. 101-105.

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

二分求冪算法：快速完成求冪計(jì)算

二分求冪算法：快速完成求冪計(jì)算

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

二分求冪算法：快速完成求冪計(jì)算

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av