快捷導(dǎo)航

c++入門必學(xué)算法之快速冪思想及實(shí)現(xiàn)

更新時(shí)間：2022年11月04日 10:43:27 作者：舊林墨煙

快速冪相較于普通的冪,具有占用空間少,效率更高等優(yōu)點(diǎn),全面碾壓普通的冪,下面這篇文章主要給大家介紹了關(guān)于c++入門必學(xué)算法之快速冪思想及實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下

一、什么是快速冪

快速冪算法是用來(lái)快速計(jì)算指數(shù)表達(dá)式的值的，例如 210000000,普通的計(jì)算方法 2*2*2*2…乘10000000次，如果一個(gè)數(shù)字的計(jì)算都要計(jì)算那么多次的話，那么這個(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ù)

例如 2¹⁰

指數(shù)是偶數(shù)，2¹⁰ = 4⁵
指數(shù)是奇數(shù)，4⁵ = 4 * 4⁴
指數(shù)是偶數(shù)， 4 * 4⁴ = 4 * 16²
指數(shù)是偶數(shù)，4 * 16²= 4 * 256¹
指數(shù)是奇數(shù)， 4 * 256¹=4 * 256 * 256⁰
指數(shù)為0時(shí)停止，那么答案就是計(jì)算 4 * 256 = 1024

下面代碼就是模擬這個(gè)過程：

 #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++入門必學(xué)算法之快速冪思想及實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)c++快速冪算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

C++快速冪與大數(shù)取模算法示例

相關(guān)文章

利用C語(yǔ)言解決八皇后問題以及解析
這篇文章主要給大家介紹了關(guān)于利用C語(yǔ)言解決八皇后問題以及解析，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2018-12-12
C語(yǔ)言實(shí)現(xiàn)通訊錄程序
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)通訊錄程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-10-10
華為云CodeArts?IDE?Online快速入門和使用
華為云CodeArts?IDE?Online服務(wù),提供了可隨時(shí)隨地編碼的云上開發(fā)環(huán)境,同時(shí)具備開放的生態(tài)和獨(dú)立插件市場(chǎng),本文主要介紹了華為云CodeArts?IDE?Online快速入門和使用,具有一定的參考價(jià)值,感興趣的可以了解一下
2023-08-08
基于C++的攝像頭圖像采集及拼接程序的簡(jiǎn)單實(shí)現(xiàn)
本程序是在?ubuntu14.04?平臺(tái)下實(shí)現(xiàn)的，在本項(xiàng)目目錄下，已經(jīng)有編譯生成的可執(zhí)行程序，其中Camera_to_Frmae.cpp是我們從雙攝像頭實(shí)時(shí)抓取單幀圖像的源碼，對(duì)基于C++的攝像頭圖像采集及拼接程序的實(shí)現(xiàn)感興趣的朋友一起看看吧
2022-01-01
C++中前綴和數(shù)組(算法)基本介紹
前綴和（Prefix Sum）是指數(shù)組中某個(gè)位置之前的所有元素的和,本文將介紹C++中前綴和數(shù)組(算法)基本概念,感興趣的朋友一起看看吧
2024-12-12
用C語(yǔ)言實(shí)現(xiàn)猜數(shù)字游戲
這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)猜數(shù)字游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-10-10
C語(yǔ)言中文件常見操作的示例詳解
FILE為C語(yǔ)言提供的文件類型，它是一個(gè)結(jié)構(gòu)體類型，用于存放文件的相關(guān)信息。本文主要為大家介紹下C語(yǔ)言中幾個(gè)常見的文件操作的實(shí)現(xiàn)，需要的可以參考一下
2022-12-12
C++臨時(shí)性對(duì)象的生命周期詳細(xì)解析
臨時(shí)性對(duì)象的被摧毀，應(yīng)該是對(duì)完整表達(dá)式（full-expression）求值過程中的最后一個(gè)步驟。該完整表達(dá)式造成臨時(shí)對(duì)象的產(chǎn)生
2013-09-09
C語(yǔ)言算法練習(xí)之折半查找的實(shí)現(xiàn)
二分查找法（也叫折半查找）其本質(zhì)是分治算法的一種。這篇文章主要介紹了如何利用C語(yǔ)言實(shí)現(xiàn)折半查找，感興趣的小伙伴可以學(xué)習(xí)一下
2022-05-05
C++?QT實(shí)現(xiàn)文件壓縮和解壓縮操作
這篇文章主要為大家詳細(xì)介紹了C++?QT如何實(shí)現(xiàn)壓縮文件、文件夾和解壓縮的操作，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下
2022-11-11