分治法-大数相乘.cpp

湖南大学ACM-OJ的部分题目代码

#include<iostream>
#include<string>
#include<list>
int a[10];
using namespace std;
//int a[1000],b[1000],sum[10000];
//int *a,*b,n,m;
//b=new int[m];
list<int>Link;
list<int> fun(list<int> t,list<int> v,int w)
{
	int i=0,r;
	list<int> L;
	list<int>::iterator p=t.begin();
	list<int>::iterator k=v.begin();
	r=(*p)*w+(*k)+i;
	L.push_back(r%10);
	Link.push_back(r%10);
	i=r/10;
	p++;
	k++;

	while(p!=t.end())
	{
		r=(*p)*w+(*k)+i;
		L.push_back(r%10);
		i=r/10;
		p++;
		k++;
	}
	if(i!=0)
		L.push_front(i);
	L.pop_front();
	

	return L;
}
int main()
{
	int n,i=0;
	list<int> x,y,w;
	int d;
	for(;i<5;i++)
	{
		cin>>d;
		w.push_back(d);		
	}
	list<int>::iterator q=w.begin();
	for(i=0;i<10;i++)
	{
		cin>>d;
		x.push_back(d);
		y.push_back(0);
	}

	while(q!=w.end())
	{
		y=fun(x,y,(*q));
		q++;
	}
	
	
	q=y.begin();
	while(q!=y.end())
	{
		Link.push_front(*q);
		q++;
	}
	list<int>::iterator p=Link.begin();
	while(p!=Link.end())
	{
		cout<<(*p);	
		p++;
	}
		return 0;
}

	


/*int main()
{
    string s1,s2;
while(1)
{
	cin>>s1;
	cin>>s2;
	int l1=s1.length();
	int l2=s2.length();
	for(int i=l1-1;i>=0;i--)
	{
		a[l1-i-1]=s1[i]-'0';
	}
	for(int j=l2-1;j>=0;j--)
	{
		b[l2-j-1]=s2[j]-'0';
	}
	if((a[0]==0)&&(b[0]==0))
		break;
	int l=l1>l2?l1:l2;
	int set=0;
	for(int x=0;x<=l;x++)
	{
        sum[x]=a[x]+b[x]+set;
		set=sum[x]/10;
		sum[x]=sum[x]%10;
	}
	int t=0;
	for(int y=l;y>=0;y--)
	{
		if(sum[l]==0&&t==0)
		{
			t=1;
			continue;
		}
		cout<<sum[y];
	}
	cout<<endl;
}
	return 0;
}
*/




/*     用数组实现
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
using namespace std;
char result[10000],result1[10000],result2[10000]; 
 
int Add(char *result,char *sa,char *sb,int len1,int len2,int n)
{
	char digit[11]="0123456789";
	int sum;
	int i,g=0;
	int p=len1>(len2+n)?len1:(len2+n);
	for(i=0;i<n;i++)
		result[i]=sa[i];
	for(i=n;i<p;i++)
	{	
	   sum=(sa[i]-'0')+(sb[i-n]-'0')+g;		
	   result[i]=digit[sum%10];
	   g=sum/10;
	}
    if(g==1)
	{
        result[i]='1';
		return (p+1);
	}
	return p;
}

int Mul_signal(char *result,char *elem1,char elem2,int len1)
{
    int i,sum,jin=0;
	char digit[11]="0123456789";
	for(i=0;i<len1;i++)
	{
	    sum=(elem1[i]-'0')*(elem2-'0')+jin;
		result[i]=digit[sum%10];
		jin=sum/10;
	}
	if(jin>0)
	{
		result[i]=digit[jin];
		return (i+1);
	}
	return i;
    
}

int main()
{
    char plus_elem1[100],plus_elem2[100];
	while(cin>>plus_elem1>>plus_elem2)
	{
	for(int j=0;j<10000;j++)
	{
		result[j]=result1[j]=result2[j]='0';
	}
	int len1=strlen(plus_elem1);
	int len2=strlen(plus_elem2);
	int flag=0;
	if(len1>len2)
		flag=1;
	int min=len1<len2?len1:len2;
	int i;
	reverse(plus_elem1,plus_elem1+len1);
	reverse(plus_elem2,plus_elem2+len2);
	int l0,l1,l2;
	if(flag)
	{
	   l1=Mul_signal(result1,plus_elem1,plus_elem2[0],len1);
       for(i=1;i<min;i++)
	   {
            l2=Mul_signal(result2,plus_elem1,plus_elem2[1],len1);
	        l0=Add(result,result1,result2,l1,l2,i);
		    strncpy(result1,result,l0);
	   }
	}
	else
	{
		l1=Mul_signal(result1,plus_elem2,plus_elem1[0],len2);
     	for(i=1;i<min;i++)
		{
          l2=Mul_signal(result2,plus_elem2,plus_elem1[i],len2);
	      l0=Add(result,result1,result2,l1,l2,i);
		  strncpy(result1,result,l0);
		}
	}
	result[l0]='\0';
	reverse(result,result+l0);
	printf("%s\n",result);
	}
	return 0;
}
*/