c语言中尽量不用除法,[C语言]整除光棍—高精度除法 | 祭夜の咖啡馆

拼搏现实的明天。 2023-01-22 12:58 17阅读 0赞

前言

最近经常做PTA的题目，吐槽一下，这老师布置题目真是不分等级。。。

就教了那么点东西，就想让学生做一些恶心的题目。

(PS:我是学过的，所以稍微动脑也不是太大问题

![63c7414bbda0339b7b3d4eb9832c0b36.png][] )

题目

整除光棍这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。 现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。

提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序输入31，那么就输出3584229390681和15，因为31乘以3584229390681的结果是111111111111111，一共15个1。

输入格式：

输入在一行中给出一个不以5结尾的正奇数x(<1000)。

输出格式：

在一行中输出相应的最小的s和n，其间以1个空格分隔。

输入样例：31

输出样例：3584229390681 15

有点恶心

![004488bd471ad6bc9fa98d98233b41b9.png][]

解题

既然题目明确提示s可能是个非常大的数，那就暴力的直接上高精度除法。。

这个题目有个便捷点，就是被除数每一位都是1，这就为计算是增加1的位数提供了方便。

![43c756f255e64c6fe06631f4acb0b00a.png][]

高精度除法是需要用数组的，所以可以定义一个名为res的很大的数组，比如1000个元素，这样就能存1000位数字了。

首先，假设x = 7，那就是这样：

![3959.air][]

图将就看吧

![590d3cd882bc9d23da61faedd735ced4.png][]

模拟计算取商

取余

判断余数是否为0

为0输出结果

不为0乘10加上1，重复1-5

1.取商

定义一个变量divisor用于存储余数，像这样：

![3959.air][]

这里可以默认divisor为1，因为从第二次开始计算商都是这样的：(divisor \* 10 + 1)/7,

这种除法显然是要用循环来实现的，并且是类死循环(只有余数为0时，通过break强制退出循环)那这第一个结果要不要存到数组里面呢？商是零，肯定不存啊

于是，我们有了一个判断是否储存结果的条件：商不为零那要是中途商出现零怎么办？那就根据已存数据不为零来判断

于是，我们可以根据数组长度和商的情况来判断是否存储结果，

定义一个变量pos来记录数组中结果保存的位置，同时可以用来指示商保存的位置。

2.计算余数

这个好办，直接 divisor = divisor % x就完事儿，

3.判断余数是否为0

①：为0输出结果，用循环来输出，输出时按顺序输出就行因为做除法时存储数据的顺序跟产生数据的顺序是一样的。

emm….还要输出111….的个数，

这个可以加个计数器，因为每循环一次意味着1的个数加一，所以，计数器就随着循环的次数增加而增加，

像这样：

![3959.air][]

输出完毕之后，使用break终止循环。

②：不是0，那就模拟余数与1拼凑在一起 divisor = divisor \* 10 +1

像这样：

![3959.air][]

然后重复相同计算过程就行了

贴代码

代码并发最优，只是能用，好理解

![63c7414bbda0339b7b3d4eb9832c0b36.png][]/\*\*

\* 这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。 现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。

\* 提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序输入31，那么就输出3584229390681和15，因为31乘以3584229390681的结果是111111111111111，一共15个1。

\* NOTE:尝试使用高精度除法

\*/

\#include

int main(void)

int res\[1000\] = \{'\\0'\};

int x;

int len = 0;

int pos = 0;

int divisor = 1;

scanf("%d", &x);

while (true)

//pos确保结果长度不为0时，但除法结果为0时，结果能够得到保存

if (pos || divisor / x)

res\[pos++\] = divisor / x;

//结果长度加一

len++;

//获取人工计算除法的余数

divisor = divisor % x;

//如果余数为0，表明计算完毕

if (divisor == 0)

for (int i = 0; i < pos; i++)

//顺序输出结果

printf("%d", res\[i\]);

//输出“光棍”数

printf(" %d", len);

break;

//模拟人工计算得到余数后，从后上方下落一位数字的过程

divisor = divisor \* 10 + 1;

return 0;

总结

除法比乘法简单没有进位什么的，相对好处理一些。

![43c756f255e64c6fe06631f4acb0b00a.png][]

转载请注明原文链接：\[C语言\]整除光棍—高精度除法

[63c7414bbda0339b7b3d4eb9832c0b36.png]: /images/20221020/7d983859be0f484f8d2b394c57328f01.png
[004488bd471ad6bc9fa98d98233b41b9.png]: /images/20221020/dd134d55681148af8df63a57b26155e7.png
[43c756f255e64c6fe06631f4acb0b00a.png]: /images/20221020/35dfcab60c444beebeb8c2180c4b8027.png
[3959.air]: /images/20221020/9d90860fef2f448c856b5b73319ab530.png
[590d3cd882bc9d23da61faedd735ced4.png]: /images/20221020/58009443793942328cf3656f3eadc68d.png