qingwa.cpp

解0/1背包问题

#include <iostream> 
#include <math.h>
using namespace std; 

int Mul(long int x,long int y,int i);


void main()
{
	int i;
	long int x,y,z;
	long int X;
	cout<<"\n";       
	cout<<"************************************************************"<<"\n";
   	cout<<"*                   十进制的大整数乘法                     *"<<"\n";
	cout<<"************************************************************"<<"\n";
	cout<<"请输入x,y"<<endl;
	cin>>x>>y;
	X=x;
	for(i=0;X;i++)
		X=int(X/10);
	z=Mul(x,y,i);
	cout<<"Result is "<<z<<endl;
	
}


int Mul(long int x,long int y,int i)
{
	if(i==1)
		return x*y;
	long xh,xl,yh,yl,m1,m2,m3;
	xh=x/int(pow(10,(i/2)));
	xl=x%int(pow(10,(i/2)));
	yh=y/int(pow(10,(i/2)));
	yl=y%int(pow(10,(i/2)));
	if(i==2)
	{
		return ((xh*yh)*100+((xh)*(yh)+(xl)*(yl)+(xh-xl)*(yl-yh))*10+(xl)*(yl));
	}
	m1=Mul(xh,yh,i/2);
	m2=Mul(xh-xl,yl-yh,i/2);
	m3=Mul(xl,yl,i/2);
	return m1*int(pow(10,i))+(m1+m2+m3)*int(pow(10,(i/2)))+m3;
	
	
}