当前位置:首页 - 技术文章 - 【算法基础】高精除以高精(C++描述)

【算法基础】高精除以高精(C++描述)

2021-03-27 00:05:07 作者: 共享资源吧

高精除以低精。输入两个正整数,求他们的商(做整除)。

【算法分析】

做除法时,每一次的商的值都在 0 ~ 9,每次求得的余数连接以后的若干位得到新的被除数,继续做除法。因此,在做高精度除法时,要涉及到乘法运算和减法运算,还有位移处理。当然,为了 程序简洁,可以避免高精度乘法,用 0 ~ 9 次循环减法取代得到商的值。这里,我们讨论一下高精度除以单精度数的结果,采取的方法时按位相除法。

高精除以低精的参考程序:

#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;
}

文章结束

免责声明

本站提供的一切软件、教程和内容信息仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络收集整理,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑或手机中彻底删除上述内容。如果您喜欢该程序和内容,请支持正版,购买注册,得到更好的正版服务。我们非常重视版权问题,如有侵权请邮件与我们联系处理。敬请谅解!

作者信息
广告位 投稿