日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后,達者為師

網站首頁 編程語言 正文

c++入門必學算法之快速冪思想及實現_C 語言

作者:舊林墨煙 ? 更新時間: 2022-12-06 編程語言

一、什么是快速冪

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

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

二、快速冪思想及實現

快速冪思想其實很簡單,就是公式的轉換

1、當指數是偶數時,我們可以讓指數除以2,底數乘以底數

2、當指數是奇數時,我們可以將指數變為奇數

例如 210

  • 指數是偶數,210 = 45
  • 指數是奇數,45 = 4 * 44
  • 指數是偶數, 4 * 44 = 4 * 162
  • 指數是偶數,4 * 162 = 4 * 2561
  • 指數是奇數, 4 * 2561=4 * 256 * 2560
  • 指數為0時停止,那么答案就是計算 4 * 256 = 1024

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

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

總結

原文鏈接:https://blog.csdn.net/weixin_52115456/article/details/127608433

欄目分類
最近更新