PAT乙级1017. A除以B(20)

89 阅读 0 评论 59 点赞

我是靠谱客的博主超级大侠，最近开发中收集的这篇文章主要介绍PAT乙级1017. A除以B(20)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1017. A除以B(20)

本题要求计算A / B，其中A是不超过1000位的正整数，B是1位正整数。你需要输出商数Q和余数R，使得A = B * Q + R成立。
输入格式：
输入在1行中依次给出A和B，中间以1空格分隔。
输出格式：
在1行中依次输出Q和R，中间以1空格分隔。
输入样例：
123456789050987654321 7
输出样例：

17636684150141093474 3

分析：由于被除数的数据过大，用int或者long int肯定是不行的。因此我们可以用字符串来保存A。

我们可以通过模拟笔算的过程来一位一位的求商。

下图是我拿1234除以7当作栗子。

红色表示当前正在处理哪一位，Q是商数组，A是被除数数组。

每次算出一位商（下图的左边），都要调整当前位的被除数（下图的右边），为下一位的除法作准备。

最后输出商的时候还要注意关于开头0的问题，如果开头是0的话就把0跳过，不过前提是这个商不是1位数，否则开头的0就不必跳过

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string a;//a是被除数的字符串形式
	int A[1000], B, Q[1000], R;//A,B,Q,R分别代表被除数，除数，商，余数
	cin >> a >> B;
	int i;
	for (i = 0; i < a.length(); i++)//把被除数从字符串形式转化为int形式
		A[i] = a[i] - 48;

	Q[0] = A[0] / B;//先求出商的第一位
	A[0] -= B*Q[0];//再更新下一步的被除数

	for (i = 1; i < a.length(); i++)
	{
		Q[i] = (A[i - 1] * 10 + A[i]) / B;//算出商从左往右数第i位
		A[i] = ((A[i - 1] * 10 + A[i]) - B*Q[i]) % 10;//更新被除数的第i位
	}

	R = A[a.length() - 1];//余数就是最后更新完成后的被除数的个位

	if (Q[0]||a.length()==1)//只有商的第一位不是0才输出，但是如果商只有一位的话那么还是要输出0
		cout << Q[0];
	for (i = 1; i < a.length(); i++)//输出商的其余位
		cout << Q[i];

	cout << " " << R;//输出余数
}