最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

C/C++高精度運(yùn)算(大整數(shù)運(yùn)算)詳細(xì)講解

 更新時間:2022年11月08日 14:53:56   作者:小白還在寫代碼  
高精度算法的本質(zhì)是把大數(shù)拆成若干固定長度的塊,然后對每一塊進(jìn)行相應(yīng)的運(yùn)算,下面這篇文章主要給大家介紹了關(guān)于C/C++高精度運(yùn)算(大整數(shù)運(yùn)算)的相關(guān)資料,需要的朋友可以參考下

前言

高精度的運(yùn)算在算法題尤為常見,在處理一些大型數(shù)據(jù)的項(xiàng)目中也需要用到。雖然Boost庫中有處理高精度問題的模板,但是標(biāo)準(zhǔn)庫中并沒有。為了方便學(xué)習(xí),本文提供了高精度運(yùn)算的模板,供大家參考。

什么是大整數(shù) 

眾所周知,最大的整型long long的范圍是【-9223372036854775808~9223372036854775807】,即使是無符號位的unsigned long long最大值也只是擴(kuò)大一倍,那當(dāng)題目需要用到或需要輸出比long long類型的范圍還要大的數(shù)字時,我們是不是就不能用常規(guī)辦法去接收這些數(shù)字了。這個時候使用大整數(shù)就可以解決上述問題——也就是解決接收超出整型范圍數(shù)字的問題。

大整數(shù)的表示

其實(shí)大整數(shù)的表示方法也不難,我們使用數(shù)組就可以了(當(dāng)然C++的vector容器也是可以的,原理都一樣,但為了照顧C(jī)語言的小伙伴,本文用數(shù)組表示)。

假設(shè)現(xiàn)在有一個int類型數(shù)組d[1000],那么我們可以用數(shù)組中的每一位元素表示大整數(shù)中的每一位數(shù)字,比如有整數(shù)123456789,那么我們可以用d[0]表示億位上的【1】,用d[1]表示千萬位上的【2】...以此類推,我們就可以用一個長度為9的數(shù)組表示這個大整數(shù)了。

當(dāng)然為了契合我們后面四則運(yùn)算的思維,我們將數(shù)組元素的順序翻轉(zhuǎn)一次,也就是在數(shù)組靠前的元素表示低位,而靠后的元素表示高位(原因后面會講到),也就是如下圖所示:

而為了方便我們獲取當(dāng)前大整數(shù)的長度,我們可以使用一個結(jié)構(gòu)體(或者一個類,與C語言的結(jié)構(gòu)體不同,在C++中的結(jié)構(gòu)體也可以定義成員函數(shù))來表示。

//struct of bign(big number)
struct bign {
    int d[1000];
    int len;
	bign()//構(gòu)造函數(shù)
	{
		this->len = 0;
		memset(d, 0, sizeof(d));
	}
};

當(dāng)然,一般輸入大整數(shù)時,都是先用字符串讀入,然后再把字符串另存為至bign結(jié)構(gòu)體。

bign change(const string str)//將整數(shù)轉(zhuǎn)換為begin c語言用const char* 
{
	bign a;
	a.len = str.size();//bign的長度就是字符串的長度 c語言用strlen()函數(shù)
	for (int i = 0; i < a.len; i++)
	{
		a.d[i] = str[a.len - i - 1] - '0';
	}
	return a;
}

大整數(shù)的運(yùn)算

對于大整數(shù)的四則運(yùn)算,我們需要模擬在小學(xué)期間學(xué)習(xí)四則運(yùn)算的思路和過程,也就是把我們在草稿紙上運(yùn)算的過程,抽象成代碼的邏輯。

1、高精度加法

加法實(shí)現(xiàn)方式與我們以前學(xué)到的加法一樣。對于某一位的運(yùn)算:我們將該位上的兩個數(shù)字與進(jìn)位相加,得到的結(jié)果取個位數(shù)作為該結(jié)果,十位數(shù)作為新的進(jìn)位。

bign add(bign a, bign b)
{
	bign c;
	int carry = 0;	//carry是進(jìn)位標(biāo)志
	for (int i = 0; i < a.len || i < b.len; i++) //以較長的為界限 
	{
		int temp = a.d[i] + b.d[i] + carry;		//兩個對應(yīng)位與進(jìn)位相加 
		c.d[c.len++] = temp % 10;		//取個位數(shù)為該位的結(jié)果 
		carry = temp / 10;	//取十位數(shù)為新的進(jìn)位 
	}
	if (carry) //如果最后的進(jìn)位不為0,則直接賦給結(jié)果的最高位  
	{
		c.d[c.len++] = carry;
	}
	return c;
}

這里要注意,這樣寫法的條件是兩個對象都是非負(fù)整數(shù)。如果有雙方異號,可以在轉(zhuǎn)換到數(shù)組這一步時去掉符號,再使用高精度減法;如果雙方都為負(fù)數(shù),那么去掉負(fù)號后采用高精度加法,最后負(fù)號加回去即可。 

2、高精度減法

通過對減法步驟的拆分可以得到一個簡練的步驟:對某一位,比較被減位和減位,如果不夠減,則令被減位的高位減1,被減位加10再進(jìn)行減法(借一位);如果夠減,那就直接減。最后需要注意減法后高位可能有多余的0,要去除它們,但要保證結(jié)果至少有一位數(shù)。

bign sub(bign a, bign b) //a - b
{
	bign c;
	for (int i = 0; i < a.len || i < b.len; i++) //以較長的為界限
	{
		if (a.d[i] < b.d[i]) //不夠減 
		{
			a.d[i + 1]--;	//向高位借位 
			a.d[i] += 10; 	//向前位借10  
		}
		c.d[c.len++] = a.d[i] - b.d[i];		//減法結(jié)果為當(dāng)前位 
	}
	while (c.len >= 2 && c.d[c.len - 1] == 0)    //剩余的位數(shù)不小于十位,并且最高位是0
	{
		c.len--;	//去除高位的0,同時至少保留一位最低位 
	}
	return c;
}

3、高精度乘以低精度

所謂高精度乘以低精度,就是bign*int的運(yùn)算。

對某一位來說是這樣的步驟:取bign的某位與int型整體相乘,再與進(jìn)位相加,所得結(jié)果的個位數(shù)作為該結(jié)果,高位部分作為新的進(jìn)位。對于a、b異號的情況只需要一個標(biāo)志位變量記錄,在輸出的時候加上負(fù)號就行了。

bign multi(bign a, int b)
{
	bign c;
	int carry = 0;	//進(jìn)位
	for (int i = 0; i < a.len; i++)
	{
		int temp = a.d[i] * b + carry;
		c.d[c.len++] = temp % 10;		//個位作為該結(jié)果
		carry = temp / 10;	//高位部分作為新的進(jìn)位 
	}
 
	while (carry != 0) //和加法不一樣,乘法的進(jìn)位可能不止一位,因此用while 
	{
		c.d[c.len++] = carry % 10;
		carry /= 10;
	}
	return c;
}

4、高精度除以低精度

高精度除以低精度,就是bign/int的運(yùn)算??紤]到有時還需要知道計(jì)算之后的余數(shù),于是就把余數(shù)寫成引用的形式傳入,當(dāng)然也可以把余數(shù)設(shè)成全局變量。 

對于某一位來說:上一步的余數(shù)乘以10加上該步的位,得到該步當(dāng)前的被除數(shù),將其與除數(shù)比較;如果不夠除,則該位的商為0;如果夠除,則商即為對應(yīng)的商,余數(shù)即為對應(yīng)的余數(shù)。和其他運(yùn)算一樣,要注意結(jié)果可能有多余的0,要去掉它們,但也要保證結(jié)果至少有一位數(shù)。

bign divide(bign a, int b, int& r) //r為余數(shù) 
{
	bign c;
	c.len = a.len;//被除數(shù)的每一位和商的每一位是一一對應(yīng)的,因此先令長度相等 
	for (int i = a.len - 1; i >= 0; i--)  //從高位開始 
	{
		r = r * 10 + a.d[i];		//和上一位遺留的余數(shù)組合
		if (r < b) c.d[i] = 0;		//不夠除,該位為0 
		else //夠除 
		{
			c.d[i] = r / b;	//商
			r = r % b;		//獲得新的余數(shù) 
		}
	}
	while (c.len >= 2 && c.d[c.len - 1] == 0)
	{
		c.len--; //去除高位的0,同時至少保留一位最低位 
	}
	return c;
}

如果大家對于上述的邏輯還不清楚的話,可以自己在稿紙上舉例幾個簡單的數(shù)算算,實(shí)際思路和我們運(yùn)算時的思路是一樣的哈。

大整數(shù)的表示

最后,當(dāng)我們要打印出大整數(shù)時則要注意了,在上文中,我們?yōu)榱朔奖氵\(yùn)算,將數(shù)組中的位序翻轉(zhuǎn)了一次,所以打印時就是需要從后往前輸出。

而如果我們輸入的數(shù)據(jù)是【04】,那么輸出的結(jié)果就不是單純的【4】了,一般來說這不是我們想要的結(jié)果是吧。那么為了解決這個問題,我們可以在打印的時候加上一個標(biāo)志位來判斷。

void print(bign ans)
{
	int flag = 0;
	for (int i = ans.len - 1; i >= 0; i--)
	{
		if (ans.d[i] != 0)    //標(biāo)志位如果首位是0 則不輸出
		{
			flag = 1;
		}
		if (flag)
		{
			cout << ans.d[i];
		}
	}
	if (!flag)
		cout << 0;    //包含輸出0的情況
}

補(bǔ)充:使用示例

例題1(貪心+大整數(shù))

題目:洛谷P1080 國王游戲

分析

此題需要先貪心找到排序規(guī)律為按照每個人的左右手乘積非降序排列,在計(jì)算最小值時累乘的過程中可能數(shù)字溢出,所以要使用大整數(shù),但是根據(jù)題目描述大整數(shù)開100001位是不夠的需要開的更大,但是實(shí)際測試數(shù)據(jù)并沒有這么大。

AC代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 10001;
pair<int,int> nums[maxn];	//first 右手,second左手

struct bign{	//存123時: d={3,2,1}llen =3; 
	int d[maxn];
	int len;
	bign(){
		memset(d,0,sizeof(d));
		len = 0;}
}res,sum,ans;	//res最終結(jié)果,sum累乘結(jié)果,ans比較變量

bign multi(bign a,int b){	//高精度大整數(shù)與低精度的乘法
	bign c;
	int carry = 0; //進(jìn)位
	for(int i=0;i<a.len;i++){
		int temp = a.d[i]*b + carry;
		//printf("%d*%d+%d\n",a.d[i],b,carry);
		c.d[c.len++] = temp%10;
		carry = temp / 10;
	} 
	while(carry!=0){
		c.d[c.len++] = carry%10;
		carry/=10;
	}
	return c;
}

bign divide(bign a,int b,int& r){	//高精度除以低精度,r為余數(shù) 
	bign c;
	c.len = a.len;
	r=0;
	for(int i=a.len-1;i>=0;i--){
		r = r*10 + a.d[i];
		if(r<b) c.d[i] = 0;
		else{
			c.d[i] = r/b;
			r %= b;
		}
	}
	while(c.len-1>=1&&c.d[c.len-1]==0){
		c.len--;
	}
	return c;
}

int compare(bign a,bign b){	//比較a和b的大小,a>b返回1,相等返回0,a<b返回-1 
	if(a.len>b.len) return 1;
	if(a.len<b.len) return -1;
	for(int i=a.len-1;i>=0;i--){
		if(a.d[i]>b.d[i]) return 1;
		if(a.d[i]<b.d[i]) return -1;
	}
	return 0;
}

void print(bign a){	//輸出大整數(shù) 
	for(int i=a.len-1;i>=0;i--)
		printf("%d",a.d[i]);
	return;
}

int cmp(pair<int,int> a,pair<int,int> b){
	return a.first*a.second<b.first*b.second;
}

int main(){
	int n;
	scanf("%d",&n);
	scanf("%d %d",&nums[0].first,&nums[0].second);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&nums[i].first,&nums[i].second);
	sort(nums+1,nums+1+n,cmp);
	sum.d[0] = 1; sum.len = 1;
	for(int i=1;i<=n;i++){
		int r = 0;	//存余數(shù) 
		sum = multi(sum,nums[i-1].first);
		ans = divide(sum,nums[i].second,r);
		if(compare(ans,res)==1)
			res = ans;
	}
	print(res);
	return 0;
}

總結(jié)

到此這篇關(guān)于C/C++高精度運(yùn)算(大整數(shù)運(yùn)算)的文章就介紹到這了,更多相關(guān)C/C++高精度運(yùn)算內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 簡述C++的復(fù)雜性

    簡述C++的復(fù)雜性

    這篇文章主要介紹了簡述C++的復(fù)雜性,幫助大家更好的理解和認(rèn)識c++編程語言,感興趣的朋友可以了解下
    2020-08-08
  • C++中的delete不會將操作數(shù)置0

    C++中的delete不會將操作數(shù)置0

    這篇文章主要介紹了C++中的delete不會將操作數(shù)置0的相關(guān)資料,需要的朋友可以參考下
    2016-05-05
  • C++實(shí)現(xiàn)動態(tài)線性表

    C++實(shí)現(xiàn)動態(tài)線性表

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)動態(tài)線性表,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-05-05
  • c++ 判斷奇數(shù)偶數(shù)實(shí)例介紹

    c++ 判斷奇數(shù)偶數(shù)實(shí)例介紹

    下面通過判斷一個數(shù)是偶數(shù)還是奇數(shù)來展示交互遞歸的應(yīng)用,并且此題突出了遞歸跳躍的信任的重要性,需要的朋友可以參考下
    2012-11-11
  • 帶你搞懂C++ LeeCode 二叉樹的中序遍歷

    帶你搞懂C++ LeeCode 二叉樹的中序遍歷

    中序遍歷(LDR)是二叉樹遍歷的一種,也叫做中根遍歷、中序周游。在二叉樹中,中序遍歷首先遍歷左子樹,然后訪問根結(jié)點(diǎn),最后遍歷右子樹
    2021-07-07
  • C語言零基礎(chǔ)精通變量與常量

    C語言零基礎(chǔ)精通變量與常量

    這篇文章主要為大家詳細(xì)介紹了C語言的變量和常量,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-04-04
  • C語言實(shí)現(xiàn)學(xué)籍信息管理系統(tǒng)

    C語言實(shí)現(xiàn)學(xué)籍信息管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)學(xué)籍信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-07-07
  • 詳解C語言和Python中的線程混用

    詳解C語言和Python中的線程混用

    這篇文章主要介紹了C和Python中的線程混用的相關(guān)資料,文中講解非常細(xì)致,幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下
    2020-07-07
  • C語言實(shí)現(xiàn)通訊管理系統(tǒng)設(shè)計(jì)

    C語言實(shí)現(xiàn)通訊管理系統(tǒng)設(shè)計(jì)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)通訊管理系統(tǒng)設(shè)計(jì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • C語言GetStdHandle函數(shù)使用方法

    C語言GetStdHandle函數(shù)使用方法

    這篇文章介紹了C語言GetStdHandle函數(shù)的使用方法,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-12-12

最新評論

杂多县| 宜黄县| 江山市| 福贡县| 灯塔市| 施秉县| 贺兰县| 精河县| 贺兰县| 正蓝旗| 南雄市| 若羌县| 松原市| 马山县| 囊谦县| 天津市| 盐山县| 老河口市| 武乡县| 宣城市| 剑阁县| 颍上县| 十堰市| 聂拉木县| 满城县| 饶阳县| 雅江县| 年辖:市辖区| 清新县| 金坛市| 临夏市| 宁强县| 武隆县| 博客| 砀山县| 巴马| 莱芜市| 德清县| 博野县| 太白县| 洱源县|