c++入門(mén)必學(xué)算法之快速冪思想及實(shí)現(xiàn)
一、什么是快速冪
快速冪算法是用來(lái)快速計(jì)算指數(shù)表達(dá)式的值的，例如 210000000,普通的計(jì)算方法 2*2*2*2…乘10000000次，如果一個(gè)數(shù)字的計(jì)算都要計(jì)算那么多次的話(huà)，那么這個(gè)程序一定是失敗的。
學(xué)完快速冪之后就可以用幾十次計(jì)算求出答案了
二、快速冪思想及實(shí)現(xiàn)
快速冪思想其實(shí)很簡(jiǎn)單，就是公式的轉(zhuǎn)換
1、當(dāng)指數(shù)是偶數(shù)時(shí)，我們可以讓指數(shù)除以2，底數(shù)乘以底數(shù)
2、當(dāng)指數(shù)是奇數(shù)時(shí)，我們可以將指數(shù)變?yōu)槠鏀?shù)
例如 210
- 指數(shù)是偶數(shù)，210 = 45
- 指數(shù)是奇數(shù)，45 = 4 * 44
- 指數(shù)是偶數(shù)， 4 * 44 = 4 * 162
- 指數(shù)是偶數(shù)，4 * 162 = 4 * 2561
- 指數(shù)是奇數(shù)， 4 * 2561=4 * 256 * 2560
- 指數(shù)為0時(shí)停止，那么答案就是計(jì)算 4 * 256 = 1024
下面代碼就是模擬這個(gè)過(guò)程：
#include<iostream>//c++標(biāo)準(zhǔn)頭文件，可以使用cout,cin等標(biāo)準(zhǔn)庫(kù)函數(shù)
using namespace std;//命名空間，防止重名給程序帶來(lái)各種隱患，使用cin,cout,stack,map,set,vector,queue時(shí)都要使用
long long fpow(long long a,long long b){//a是底數(shù)，b是指數(shù)
long long ans=1;//初始化答案為1
while(b){//當(dāng)指數(shù)不為0時(shí)執(zhí)行
if(b%2==0){//指數(shù)為偶數(shù)時(shí)，指數(shù)除以2，底數(shù)乘以2
b/=2;
a*=a;
}else{//指數(shù)為奇數(shù)時(shí)，分離指數(shù)，ans乘以底數(shù)
ans*=a;
b--;
}
}
return ans;//ans就是答案
}
int main(){
long long n,m;
cin>>n>>m;
cout<<fpow(n,m)<<endl;
}
3、快速冪精簡(jiǎn)模板
#include<iostream>
using namespace std;
long long fpow(long long a,long long b){
long long ans=1;
while(b){
if(b&1)ans*=a;
b>>=1;
a*=a;
}
return ans;
}
int main(){
long long n,m;
cin>>n>>m;
cout<<fpow(n,m)<<endl;
}
總結(jié)
到此這篇關(guān)于c++入門(mén)必學(xué)算法之快速冪思想及實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)c++快速冪算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
華為機(jī)試題之統(tǒng)計(jì)單詞個(gè)數(shù)實(shí)例代碼
這篇文章主要介紹了華為機(jī)試題之統(tǒng)計(jì)單詞個(gè)數(shù)實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05
opencv實(shí)現(xiàn)機(jī)器視覺(jué)檢測(cè)和計(jì)數(shù)的方法
在機(jī)器視覺(jué)中，有時(shí)需要對(duì)產(chǎn)品進(jìn)行檢測(cè)和計(jì)數(shù)。其難點(diǎn)無(wú)非是對(duì)于產(chǎn)品的圖像分割。本文就來(lái)介紹一下機(jī)器視覺(jué)檢測(cè)和計(jì)數(shù)的實(shí)現(xiàn)，感興趣的可以參考一下2021-05-05
在C++編程中,dynamic_cast 是處理多態(tài)類(lèi)型轉(zhuǎn)換的關(guān)鍵工具,允許在復(fù)雜繼承結(jié)構(gòu)中安全地將基類(lèi)指針或引用轉(zhuǎn)換為派生類(lèi)指針或引用,這篇文章主要介紹了C++的dynamic,需要的朋友可以參考下2024-08-08
用C# 控制Windows系統(tǒng)音量的實(shí)現(xiàn)方法
本篇文章是對(duì)使用C#控制Windows系統(tǒng)音量的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C語(yǔ)言實(shí)現(xiàn)最長(zhǎng)遞增子序列問(wèn)題的解決方法
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)最長(zhǎng)遞增子序列問(wèn)題的解決方法,采用遞歸的方法解決該問(wèn)題,是非常經(jīng)典的一類(lèi)算法,需要的朋友可以參考下2014-09-09
C++實(shí)現(xiàn)LeetCode(133.克隆無(wú)向圖)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(133.克隆無(wú)向圖),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語(yǔ)言實(shí)現(xiàn)的一個(gè)萬(wàn)年歷小程序
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)的一個(gè)萬(wàn)年歷小程序，具有一定的參考價(jià)值，做C語(yǔ)言日期計(jì)算的朋友可以參考下2014-07-07
VS中scanf為何會(huì)報(bào)錯(cuò)詳解
在我們剛使用vs時(shí),在使用scanf函數(shù)時(shí)常會(huì)遇到報(bào)錯(cuò)提醒,下面這篇文章主要給大家介紹了關(guān)于VS中scanf為何會(huì)報(bào)錯(cuò)的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-02-02
C語(yǔ)言通訊錄管理系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言通訊錄管理系統(tǒng)課程設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
今天和同事說(shuō)到C++模板會(huì)使代碼膨脹, 可同事覺(jué)得不會(huì)。 同事的依據(jù)是: 如果模板會(huì)使代碼膨脹, 那么ATL和WTL里為什么還要大量使用模板? 同樣功能 ，ATL和WTL編譯出的可執(zhí)行文件可比MFC編譯的要小的多2013-04-04