【算法基础】高精除以高精（C++描述）

高精除以高精，求他们的**商**和**余数**。

【算法分析】

高精除以低精是对被除数的每一位（这里的"一位"包含前面的余数，以下都是如此）都除以除数，而高精除以高精则是用减法模拟除法，对被除数的每一位都减去除数，一直减到当前位置的数字（包含前面的余数）小于除数（由于每一位的数字小于10，所以对于每一位最多进行10次计算），具体实现程序如下：

```C
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int a[101], b[101], c[101], d, i;

void init(int a[])
{
	string s;
	cin >> s;						//读入字符串

a[0] = s.length();				//用a[0]计算字符串 s 的位数

for (i = 1; i <= a[0]; i++)
	{
		a[i] = s[a[0] - i] - '0';	//将数串 s 转换位数组 a，并倒序存储
	}
}

void print(int a[])
{
	int i;
	if (a[0] == 0)
	{
		cout << 0 << endl;
		return;
	}

for (i = a[0]; i > 0; i--)
	{
		cout << a[i];
	}

cout << endl;
	return;
}

int compare(int a[], int b[])
		//比较 a 和 b 的大小关系，若 a>b 则为1，若 a<b 则为 -1 ，若 a=b 则为0
{
	int i;
	if (a[0] > b[0]) return 1;			//a的位数大于b则a比b大
	if (a[0] < b[0]) return -1;			//a的位数小于b则a比b小
	for (i = a[0]; i > 0; i--)			//从高位到低位比较
	{
		if (a[i] > b[i]) return 1;
		if (a[i] < b[i]) return -1;
	}
	return 0;							//各位都相等则两位数相等
}

void jian(int a[], int b[])				//计算 a = a - b
{
	int flag, i;
	flag = compare(a, b);				//调用比较函数判断大小

if (flag == 0)						//相等
	{
		a[0] = 0;
		return;
	}

if (flag == 1)						//大小
	{
		for (i = 1; i <= a[0]; i++)
		{
			if (a[i] < b[i])			//若不够减则向上借一位
			{
				a[i + 1]--;
				a[i] += 10;
			}
			a[i] -= b[i];
		}

while (a[0] > 0 && a[a[0]] == 0)	//修正a的位数
		{
			a[0]--;
		}

return;
	}
}

void numcpy(int p[], int q[], int det)		//复制 p 数组到 q 数组 ,从 det 开始的地方
{
	for (int i = 1; i <= p[0]; i++) q[i + det - 1] = p[i];
	q[0] = p[0] + det - 1;
}

void chugao(int a[], int b[], int c[])
{
	int i, tmp[101];
	c[0] = a[0] - b[0] + 1;
	for (i = c[0]; i > 0; i--)
	{
		memset(tmp, 0, sizeof(tmp));		//数组清零
		numcpy(b, tmp, i);
		while (compare(a, tmp) >= 0)
		{
			c[i]++;
			jian(a, tmp);					//用减法来模拟
		}
	}
	while (a[0] > 0 && c[c[0]] == 0) c[0]--;
	return;
}

int main()
{
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	init(a);
	init(b);
	chugao(a, b, c);
	print(c);
	print(a);
	return 0;
}
```

最后修改：2021 年 09 月 12 日