问题描述
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。
本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。
本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。
输入格式
一行三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置（0<a,b,n<1000000000）
输出格式
一行3位数字，表示：a除以b，小数后第n位开始的3位数字。
样例输入
1 8 1
样例输出
125
样例输入
1 8 3
样例输出
500
样例输入
282866 999000 6
样例输出
914
感谢大佬的文章
原地址：https://blog.csdn.net/wensishuai/article/details/6415658
求一个分数对应小数的循环节。、
思路：
我们分别用x和y表示分子和分母，先求出整数部分x div y和余数部分x mod y，那么小数部分就是重复将余数部分乘以10再进行整除运算和求余运算，直到出现循环或余数为0时结束。
我们不妨从余数入手，因为小数部分整除的结果是由上一次运算的余数决定的，如果某一次运算产生的余数跟前面产生的余数相同，则说明循环开始。
参考代码：
思路：
我们分别用x和y表示分子和分母，先求出整数部分x div y和余数部分x mod y，那么小数部分就是重复将余数部分乘以10再进行整除运算和求余运算，直到出现循环或余数为0时结束。
我们不妨从余数入手，因为小数部分整除的结果是由上一次运算的余数决定的，如果某一次运算产生的余数跟前面产生的余数相同，则说明循环开始。
参考代码：
#include<stdio.h> #define mn 1000 void main() { int i,m,n,r,t; int p[mn],q[mn]; for(i=0;i<mn;i++) //给数组p初始化值全为-1 { p[i]=-1; q[i]=0; } printf("input :m,n(0<=m<n<=1000)= "); scanf("%d%d",&m,&n); t=0; //初始化值 r=m; //把被除数赋给r while(r!=0&&(p[r]==-1)) //循环条件当r不为0且p[r]=-1时执行循环体 { p[r]=t; //余数r第一次出现的位置 r=10*r; //把被除数扩大10倍，以至于取第一个小数 t++; q[t]=r/n; //计算小数点后t位的值：取整，即为m/n的小数从小数点开始逐个取出放到数组q中 r=r%n; //算完一位就去掉一位，即取余对n } printf("m/n = 0."); //因为m<n,所以m/n整数部分0,所以先输出'0.' if (r!=0) //被除数不为0就执行以下语句 { for(i=1;i<=p[r];i++) //输出循环小数中前面非循环的部分 printf("%d",q[i]); printf("("); //输出循环的小数放在括号中 for(i=p[r]+1;i<=t;i++) printf("%d",q[i]); printf(")"); } else //被除数为0的情况 for(i=1;i<=t;i++) //输出不循环的小数 printf("%d",q[i]); printf("/n"); }
题目AC代码
#include<iostream> using namespace std; const int maxn = (int)2e6+10; int p[maxn]; //标记该余数是否出现，并记录该余数是第几个 int q[maxn]; //存放小数结果 int loop[maxn]; //存放循环部分 int a, b, n; int main() { cin >> a >> b >> n; int rest = a%b; //余数 for (int i = 0; i < maxn; i++){ p[i] = -1; q[i] = 0; } int len = 0; while (rest != 0 && p[rest] == -1){ //余数不为0(未除尽)，并且该余数第一次出现 p[rest] = len++; //标记这个余数是第几个,p[rest]为不循环部分的长度 rest *= 10; q[len] = rest / b; //小数的下一位，q[1]为小数后第1位,len可以看做结果的长度(包括不循环部分和循环部分) rest %= b; //余数更新 } //若是因为rest==0而退出while循环，则被除尽,说明结果不是无限循环小数 //若是因为p[rest]!=-1而推出循环，则说明出现了重复的余数，即会一直执行下去，为无限循环小数 if (rest == 0){ //如果不是无限循环小数，则转化成无限循环小数，循环部分为0 p[rest] = len; q[++len] = 0; } int len_noloop = p[rest]; //不循环的长度 int len_loop = len - len_noloop;//循环长度=总长度-不循环长度 if (n > len_noloop){ //如果输出的位置在循环部分 loop[0] = q[len]; //为方便输出，将循环部分放入loop数组中，并且循环部分最后一位放在loop[0] for (int i = 1; i < len_loop; i++) loop[i] = q[len_noloop + i]; n -= len_noloop; //因为是输出循环部分的数字，所以需要把前面的砍掉 cout << loop[n%len_loop] << loop[(n+1)%len_loop] << loop[(n+2)%len_loop] << endl; } else if (n + 2 <= len_noloop){ cout << q[n] << q[n+1] << q[n+2] << endl; } else if (n+1==len_noloop){ cout << q[n] << q[n+1] << q[(n+2)%len_loop] << endl; } else if (n == len_noloop){ cout << q[n] << q[(n+1)%len_loop] << q[(n+2)%len_loop] << endl; } return 0; }
题解效率
