uva 1543 - Telescope(dp+几何)

大数除法说的比较少或许不像加法减法那样简单，或许是用的不太多。到底怎么我也不知道。

反正你会了加法减法，乘法而不会除法，就像是，打开电脑而不玩游戏，心里难受。

我是从看到了大神博客后学习了一下。

http://blog.csdn.net/hitwhylz/article/details/9700935

博客中讲的很详细

让人一看就懂，我很佩服这位同学。果断的关注了。

毕竟别人写的是别人的。

自己写的才是自己的 。于是我就捋了捋，模仿这写了一遍；

思想就是：用减法来代替除法，但是一次一次的减太慢，我们就先见10的n次方次，n可不是乱来的 因为除数不能大于被除数 就以此来决定n的大小。

照着我下面的步骤先自己写一下试一试。

1我们来输入两个数，确定位数。判断大小关系；

2然后进行把输入的被除数除数进行倒置。因为做减法嘛，比如123-23 我们要先用3来减3 所以将数倒置把3放到0的位置我们就能从0开始逐个往后处理了。

3要处理的就是我们首先减多少。比如12345 - 2 因为我们先减10的n次方 我们在这决定先减20 还是200 还是2000 

决定权在两个数位数相差多少。

4 下面我们要来做减法了 比如先减20000 下一次不能减20000了 ，我们就来减2000 这一次来处理。

并且来记录相减的次数 注意减20000 的时候减一次，和2000的时候减一次，这是相差10次的。

5 最后就是尾部的处理前导0 的问题了。

下满贴上代码：

#include<iostream>
using namespace std;
//基础操作大数除法
int substract(char *a,char*b,int alen,int blen)
{
	if(alen<blen)
		return -1;
	if(alen==blen)
	{
		for(int i=alen-1;i>=0;i--)
		{
			if(a[i]<b[i]) return -1;
			if(a[i]>b[i] )break;
		}
	}
	for(int i=0;i<alen;i++)
	{
		a[i]=a[i]-b[i];
		if(a[i]<0)
		{
			a[i]+=10;
			a[i+1]--;
		}
	}
	for(int i = alen-1;i>=0;i--)
	{
		if(a[i])
			return i+1;
	}
	return 0;
}

int main()
{
	int cases;
	cin>>cases;
	while(cases--)
	{
		char _a[100];
		char _b[100];
		int _c[100];
		memset(_c,0,sizeof(_c));
		cin>>_a>>_b;
		int alen = strlen(_a);
		int blen =strlen(_b);
		if(blen>alen)
		{
			cout<<0<<endl;
			continue;
		}
		if(alen%2)
		{
			for(int i=0;i<=alen/2;i++)
			{
				int t = _a[i]-‘0‘;
				_a[i]=_a[alen-1-i]-‘0‘;
				_a[alen-1-i]=t;
			}
		}
		else
		{
			for(int i=0;i<alen/2;i++)
			{
				int t = _a[i]-‘0‘;
				_a[i]=_a[alen-1-i]-‘0‘;
				_a[alen-1-i]=t;
			}
		}
		if(blen%2)
		{
			for(int i=0;i<=blen/2;i++)
			{
				int t=_b[i]-‘0‘;
				_b[i]=_b[blen-1-i]-‘0‘;
				_b[blen-1-i]=t;
			}
		}
		else
		{
			for(int i=0;i<blen/2;i++)
			{
				int t=_b[i]-‘0‘;
				_b[i]=_b[blen-1-i]-‘0‘;
				_b[blen-1-i]=t;
			}
		}
		int a_b = alen-blen;
		for(int i=alen-1;i>=0;i--)
		{
			if(i>=a_b)
				_b[i]=_b[i-a_b];
			else
				_b[i]=0;
		}
		blen=alen;
		int temp;
		for(int i = 0 ; i<=a_b;i++)
		{
			while((temp = substract(_a,_b+i,alen,blen-i))>=0)
			{
				alen = temp;
				_c[a_b-i]++;
			}
		}
		int i=a_b;
		while(!_c[i]&&i>=0)
			i--;
		if(i>=0)
			for(i;i>=0;i--)
				cout<<_c[i];
		else
			cout<<0<<endl;
		cout<<endl;
	}
	return 0;
}

好了！

感谢自己坚持。

uva 1543 - Telescope(dp+几何),布布扣,bubuko.com

uva 1543 - Telescope(dp+几何)

原文：http://blog.csdn.net/keshuai19940722/article/details/25098145