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

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

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

一、什么是快速冪

快速冪算法是用來快速計算指數(shù)表達式的值的，例如 210000000,普通的計算方法 2*2*2*2…乘10000000次，如果一個數(shù)字的計算都要計算那么多次的話，那么這個程序一定是失敗的。

學(xué)完快速冪之后就可以用幾十次計算求出答案了

二、快速冪思想及實現(xiàn)

快速冪思想其實很簡單，就是公式的轉(zhuǎn)換

1、當(dāng)指數(shù)是偶數(shù)時，我們可以讓指數(shù)除以2，底數(shù)乘以底數(shù)

2、當(dāng)指數(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時停止，那么答案就是計算 4 * 256 = 1024

下面代碼就是模擬這個過程：

 #include<iostream>//c++標準頭文件，可以使用cout,cin等標準庫函數(shù) 
using namespace std;//命名空間，防止重名給程序帶來各種隱患，使用cin,cout,stack,map,set,vector,queue時都要使用
long long fpow(long long a,long long b){//a是底數(shù)，b是指數(shù) 
	long long ans=1;//初始化答案為1
	while(b){//當(dāng)指數(shù)不為0時執(zhí)行
		if(b%2==0){//指數(shù)為偶數(shù)時，指數(shù)除以2，底數(shù)乘以2
			b/=2;
			a*=a; 
		}else{//指數(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、快速冪精簡模板

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

您可能感興趣的文章:

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

相關(guān)文章

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