Posted inc++ zerojudge

zerojudge a021. 大數運算

2023 年 4 月 8 日

題目在 https://zerojudge.tw/ShowProblem?problemid=a021

這題是在算答案至多500位的加減乘除, 已經很大了嗎? 魔王題其實是在”i212. 三則運算“.

那題是要很快算出一百萬位的乘法才困難. 雖然我是先做出i212, 我用解那題的FFT來解這題的乘法,但是沒過. 怎麼會可以計算一百萬位的程式卻沒過500位的乘法呢? 因為這題的記憶體限制比較嚴格.只有64MB. 所以說做這題不要想太多, 我全部用簡單的直式來做加減乘除, 也都可以快速(2ms)完成.

直式加法

做加法時, 我要統一由長的a字串來加短的b字串,這樣才不用處理字串越加越長的問題.所以如果a字串比較短,就由b來加a.

我先不考慮進位, 字元範圍最高到255,所以不會溢位. 全部加完後再一次從右到左處理進位.只有最左邊的進位要注意, 因為字串會變長一位, 就加個’1’就好了. 這流程簡單明瞭吧.

string Add(string a, string b){
	int a_size=a.size();
	int b_size=b.size();
      //長的a字串來加短的b字串
	if(a_size<b_size){
		return Add(b,a);
	}

	int a_index=a_size-1;
	int b_index=b_size-1;

	//answer先加a
	string answer=a;

	//answer加b, 先不管進位
	while(b_index>=0){
		answer[a_index--]+=(b[b_index--]-'0');
	}

	//處理answer進位, answer[0]進位不處理
	a_index=a_size-1;
	while(a_index>0){
		if(answer[a_index]>'9'){
			answer[a_index]-=10;
			answer[a_index-1]++;
		}
		a_index--;
	}

	//處理answer[0]進位
	if(answer[0]>'9'){
		answer[0]-=10;
		answer='1'+answer;
	}

	return answer;
}
C++

直式減法

做減法時, 我要統一由大的a減小的b, 如果a<b那就算b-a後,再加個負號就好了. 其它跟加法差不多, 不夠減時先不管借位, 因為也不會變負號. 等全部減完後,再像直式算法的由右到左去處理借位. 輸出時,記得把字串開頭的0拿掉.

string Sub(string a, string b){

	int a_size=a.size();
	int b_size=b.size();

	//處理a<b
	if(a_size<b_size){
		string answer="-"+Sub(b,a);
		return answer;
	}else if(a_size==b_size && a<b){
		string answer="-"+Sub(b,a);
		return answer;
	}

	int a_index=a_size-1;
	int b_index=b_size-1;

	string answer=a;

	//answer減b, 先不管借位
	while(b_index>=0){
		answer[a_index--]-=(b[b_index--]-'0');
	}

	a_index=a_size-1;
	//處理answer借位
	while(a_index>0){
		if(answer[a_index]<'0'){
			answer[a_index]+=10;
			answer[a_index-1]--;
		}
		a_index--;
	}
	//由左向右去找第一個不是0的數字
	a_index=0;
	while(answer[a_index]=='0' && a_index<answer.size()-1){
		a_index++;
	}
	return answer.substr(a_index);

}
C++

直式乘法

乘法跟加減法的直式流程也一樣,但是要先把字元轉成整數, 因為怕加法太多時會溢位. 進位也是等到所有位數的乘法和加法都做完後再處理.

int MA[500];
int MB[500];
int MAB[500];
void MUL(string a, string b)
{
	memset(MAB, 0, sizeof(int)*500);
	int a_size=a.size();
	int b_size=b.size();

	//字串a轉數字
	int index=0;
	for(int i=a_size-1;i>=0;i--){
		MA[index++]=a[i]-'0';
	}

	//字串b轉數字
	index=0;
	for(int i=b_size-1;i>=0;i--){
		MB[index++]=b[i]-'0';
	}

	//直式相乘
	for(int i=0;i<b_size;i++){
		int B=MB[i];
		for(int j=0;j<a_size;j++){
			MAB[i+j]+=B*MA[j];
		}
	}

	//處理進位
	for(int i=0;i<a_size+b_size;i++){
		if(MAB[i]>=10){
			MAB[i+1]+=MAB[i]/10;
			MAB[i]%=10;
		}
	}

	//從左到右印出
	bool first=true;
	for(int i=a_size+b_size;i>=0;i--){
		if(first){
			if(MAB[i]){
				printf("%d",MAB[i]);
				first=false;
			}
			continue;
		}
		printf("%d",MAB[i]);
	}
	//當從未印出即為0
	if(first){
		printf("0");
	}
}
C++

直式除法

除法我看別人是用減法做, 為什麼不用直式除法呢? 可能是計算商的每個位數都要猜數字吧. 我用個簡單的方法.因為商的每一位都是0~9, 所以我就先把除數乘以1~9得到九個字串, 每次用字串比大小,就可以得到商了. 也很快呀.

//先算好的九種除數乘商1~9
string b_str10[10];

void DIV(string a, string b){
	int a_size=a.size();
	int b_size=b.size();

	//先得到九種 除數乘以1~9
	b_str10[1]=b;
	for(int i=1;i<9;i++){
		b_str10[i+1]=Add(b_str10[i],b);
	}

	//取得用來比大小的被除數dividend
	string dividend = a.substr(0,b_size);
	bool first=true;
	int a_index=b_size;

	while(a_index<=a_size){
		int i;
		//用九個字串來比對出商
		for(i=1;i<10;i++){
			if(dividend.size()>b_str10[i].size())
				continue;

			if(b_str10[i]>dividend || dividend.size()<b_str10[i].size())
				break;
		}

		//印出商, 但是商的第一個數字必須大於0
		if(first==false){
			printf("%d",i-1);
		}
		else if(i>1){
			printf("%d",i-1);
			first=false;
		}

                //求餘數(就是下一個被除數)
		if(i>1){
			//被除數減去(除數X商)
			dividend = Sub(dividend, b_str10[i-1]);
		}
		//如果餘數為0, 這個0不需要放入被除數
		if(a_index<a_size){
			if(dividend != "0"){
				dividend += a[a_index];
			}else{
				dividend = a[a_index];
			}
		}
		a_index++;
	}

	//Fixed #8
	if(first){
		printf("0");
	}
}
C++

順便一題, 經過測試, 測資#2,#6是在測試乘法, #3,#7,#8是在測除法.

除了乘法這樣做比較慢以外, 只要記憶體夠大, 其它三種應該都可以處理無限位數的計算.

完整程式如下.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>


using namespace std;

char a_str[1024];
char b_str[1024];
int a_length;
int b_length;


string Add(string a, string b){
	int a_size=a.size();
	int b_size=b.size();

	if(a_size<b_size){
		return Add(b,a);
	}

	int a_index=a_size-1;
	int b_index=b_size-1;

	//answer先加a
	string answer=a;

	//answer加b, 先不管進位
	while(b_index>=0){
		answer[a_index--]+=(b[b_index--]-'0');
	}

	//處理answer進位, answer[0]進位不處理
	a_index=a_size-1;
	while(a_index>0){
		if(answer[a_index]>'9'){
			answer[a_index]-=10;
			answer[a_index-1]++;
		}
		a_index--;
	}

	//處理answer[0]進位
	if(answer[0]>'9'){
		answer[0]-=10;
		answer='1'+answer;
	}

	return answer;
}

string Sub(string a, string b){

	int a_size=a.size();
	int b_size=b.size();

	//處理a<b
	if(a_size<b_size){
		string answer="-"+Sub(b,a);
		return answer;
	}else if(a_size==b_size && a<b){
		string answer="-"+Sub(b,a);
		return answer;
	}

	int a_index=a_size-1;
	int b_index=b_size-1;

	string answer=a;

	//answer減b, 先不管借位
	while(b_index>=0){
		answer[a_index--]-=(b[b_index--]-'0');
	}

	a_index=a_size-1;
	//處理answer借位
	while(a_index>0){
		if(answer[a_index]<'0'){
			answer[a_index]+=10;
			answer[a_index-1]--;
		}
		a_index--;
	}
	//由左向右去找第一個不是0的數字
	a_index=0;
	while(answer[a_index]=='0' && a_index<answer.size()-1){
		a_index++;
	}
	return answer.substr(a_index);

}

//先算好的九種除數乘商1~9
string b_str10[10];

void DIV(string a, string b){
	int a_size=a.size();
	int b_size=b.size();

	//先得到九種 除數乘以1~9
	b_str10[1]=b;
	for(int i=1;i<9;i++){
		b_str10[i+1]=Add(b_str10[i],b);
	}

	//取得用來比大小的被除數dividend
	string dividend = a.substr(0,b_size);
	bool first=true;
	int a_index=b_size;

	while(a_index<=a_size){
		int i;
		//用九個字串來比對出商
		for(i=1;i<10;i++){
			if(dividend.size()>b_str10[i].size())
				continue;

			if(b_str10[i]>dividend || dividend.size()<b_str10[i].size())
				break;
		}

		//印出商, 但是商的第一個數字必須大於0
		if(first==false){
			printf("%d",i-1);
		}
		else if(i>1){
			printf("%d",i-1);
			first=false;
		}

                //求餘數(就是下一個被除數)
		if(i>1){
			//被除數減去(除數X商)
			dividend = Sub(dividend, b_str10[i-1]);
		}
		//如果餘數為0, 這個0不需要放入被除數
		if(a_index<a_size){
			if(dividend != "0"){
				dividend += a[a_index];
			}else{
				dividend = a[a_index];
			}
		}
		a_index++;
	}

	//Fixed #8
	if(first){
		printf("0");
	}
}

int MA[500];
int MB[500];
int MAB[500];
void MUL(string a, string b)
{
	memset(MAB, 0, sizeof(int)*500);
	int a_size=a.size();
	int b_size=b.size();

	//字串a轉數字
	int index=0;
	for(int i=a_size-1;i>=0;i--){
		MA[index++]=a[i]-'0';
	}

	//字串b轉數字
	index=0;
	for(int i=b_size-1;i>=0;i--){
		MB[index++]=b[i]-'0';
	}

	//直式相乘
	for(int i=0;i<b_size;i++){
		int B=MB[i];
		for(int j=0;j<a_size;j++){
			MAB[i+j]+=B*MA[j];
		}
	}

	//處理進位
	for(int i=0;i<a_size+b_size;i++){
		if(MAB[i]>=10){
			MAB[i+1]+=MAB[i]/10;
			MAB[i]%=10;
		}
	}

	//從左到右印出
	bool first=true;
	for(int i=a_size+b_size;i>=0;i--){
		if(first){
			if(MAB[i]){
				printf("%d",MAB[i]);
				first=false;
			}
			continue;
		}
		printf("%d",MAB[i]);
	}
	//當從未印出即為0
	if(first){
		printf("0");
	}
}


int main(){

	char op;
	scanf("%s %c %s",a_str,&op,b_str);

	string answer;
	switch(op){
		case '+':answer=Add(string(a_str),string(b_str));
				break;
		case '-':answer=Sub(string(a_str),string(b_str));
				break;
		case '*':MUL(string(a_str),string(b_str));    //#2,#6
				return 0;
		case '/':DIV(string(a_str),string(b_str));   //#3,#7,#8
				return 0;
	}

	printf("%s\n",answer.c_str());
}
C++
Last updated on 2023 年 4 月 9 日