高精度运算练习题（蓝桥杯）

问题一

实现高精度的加法、减法、快速除法。

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

class Bign{
public:
	Bign(){};
	Bign(string a);
	void add(const Bign& a);	//加法 
	void minus(const Bign& a);	//减法 
	Bign devide(const Bign& a);	//除法，返回商，自己变成余数 
	friend ostream& operator<<(ostream &out,const Bign &obj);
	int compare(const Bign& a);
private:
	string data;//低位在前，高位在后 
	
}; 

int main(){
	
	string a,b;cin>>a>>b;
	Bign A(a),B(b);
	cout<<A.devide(B)<<endl;
	cout<<A;

	return 0;
}

Bign Bign::devide(const Bign& a){
	Bign ans("0");
	Bign copy_a=a;
	
	int Len=a.data.size();
	int t=data.size()-Len-1;
	//每次减一个大的数 
	while(t>0){
		copy_a.data.insert(0,string(t,'0'));
		Bign W("1"); 
		W.data.insert(0,string(t,'0'));
		while(compare(copy_a)==1){
			minus(copy_a);
			ans.add(W);
		}
		copy_a=a;
		t=data.size()-Len-1; 
	}
	//减法 (直接做减法会超时） 
	while(compare(copy_a)>=0){
		minus(copy_a);
		ans.add(Bign("1"));
	}
	return ans;
}


void Bign::minus(const Bign& a){
	int newLen=data.size();
	string ans(newLen,'0');
	int temp=0;
	for(int i=0;i<newLen;i++){		
		temp+=(data[i]-'0');
		if(i<a.data.size())temp-=(a.data[i]-'0');		
		if(temp<0){
			ans[i]+=temp+10;
			temp=-1;
		}else{
			ans[i]+=temp;
			temp=0;
		}		
	}
	for(temp=newLen-1;ans[temp]=='0';temp--);
	ans.erase(temp+1);
	this->data=ans;
}

int Bign::compare(const Bign& a){
	if(this->data.size()>a.data.size())return 1;
	if(this->data.size()<a.data.size())return -1;
	for(int i=data.size()-1;i>=0;i--){
		if(data[i]>a.data[i])return 1;
		if(data[i]<a.data[i])return -1;
	}
	return 0;
}
void Bign::add(const Bign& a){
	int newLen=max(data.size(),a.data.size())+1;
	string rel(newLen,'0');
	int temp=0;
	for(int i=0;i<newLen ;i++){		
		if(i<data.size())temp+=data[i]-'0';
		if(i<a.data.size())temp+=a.data[i]-'0';
		rel[i]+=temp%10;
		temp/=10;	
	}	
	if(rel[newLen-1]=='0')rel.erase(newLen-1);
	this->data=rel;
}
ostream& operator<<(ostream &out,const Bign &obj){
	if(obj.data.empty()){
		cout<<'0';
	}else{
		for(int i=obj.data.size()-1;i>=0;i--)
		out<<obj.data[i];
	}	
	return out;
}
Bign::Bign(string a){
	reverse(a.begin(),a.end()) ;
	data=a;
}

问题二

1. 问题描述

给出一个整数 n（n< 10^30) 和 k 个变换规则（k< =15）。

规则：

一位数可变换成另一个一位数：

规则的右部不能为零。

例如：n=234。有规则（k＝2）：

2－> 5

3－> 6

上面的整数 234 经过变换后可能产生出的整数为（包括原数）:

234、534、264、564

共 4 种不同的产生数

问题：

给出一个整数 n 和 k 个规则。

求出：经过任意次的变换（0次或多次），能产生出多少个不同整数。

仅要求输出个数。

2. 样例输入

234 2

2 5

3 6

3.样例输出

4

4.方法

(a) 先用Floyd算法，求出某一个数字可以到达的目的地（即经过0次或若干次变换的结果）
(b) 高精度运算
但是int（4字节）的范围是[-2^31^,2^31^-1]，即[-2147483648,2147483647]，
用一个int来表示1个数字太浪费了，可以用1个int来存储8位数（为了使得乘法不越界），

5.代码实现

#include<iostream>
#include<vector>
#include<string>
#define INF 99999
using namespace std;

class bign{
public:
	bign(int k=0){data.push_back(k);}
	vector<int> data;
	void mult(int k); 
	friend ostream& operator<<(ostream &out, bign& obj);
	static int N;	
};
int bign::N=10000000;



void bign::mult(int k){
	if (k==1)return;
	int L=data.size();
	int t=0;
	for(int i=0;i<L;i++){
		data[i]=data[i]*k+t;
		t=data[i]/N;
		data[i]%=N;
	}
	if(t)
		data.push_back(t);	
}
ostream& operator<<(ostream &out,bign& obj){
	int t=obj.data.size()-1;
	out<<obj.data[t--];
	for(int i=t;i>=0;i--){
		//out<<'-';
		for(int k=0;k<7-NumOfDig(obj.data[i]);k++)
			out<<'0';
		out<<obj.data[i];		
	}
	return out;
}

int NumOfDig(int k){//判断数字位数 
	if(k==0)return 1;
	int rel=0;
	while(k>0){
		k/=10;
		rel++;
	}
	return rel;
}
int main(){
	string n;cin>>n;
	int k;cin>>k;
	int d[10][10];//Floyd算法距离
	//初始化 
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			d[i][j]=INF;
		
	
	int x,y; 
	for(int i=0;i<k;i++){
		cin>>x>>y;d[x][y]=1;
	}
	//Flody算法的三重循环
	for(int k=0;k<10;k++)
		for(int i=0;i<10;i++)
			for(int j=0;j<10;j++)
				if(d[i][j]>d[i][k]+d[k][j])
					d[i][j]=d[i][k]+d[k][j];
	int flag[10]={0};//用于记录该数字会变成几种其他数字
	for(int i=0;i<10;i++){
		d[i][i]=1;//确保可以到达自己（即可以通过0次变换） 
		for(int j=0;j<10;j++)
			if(d[i][j]<INF)
				flag[i]++;
	}
	
	if(0){//测试代码
		for(int i=0;i<10;i++){
			for(int j=0;j<10;j++){
				cout<<d[i][j]<<' ';
			}cout<<endl;
		}
		cout<<"*******************"<<endl;
		for(int i=0;i<10;i++)
			cout<<flag[i]<<' ';cout<<endl; 
		cout<<"*******************"<<endl;			
	}	
	bign rel(1); 
	for(int i=0;i<n.length();i++)
		rel.mult(flag[n[i]-'0']);
	
	cout<<rel;	
	return 0;
}