历届试题小数第n位

问题描述

　　我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
　　如果我们把有限小数的末尾加上无限多个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

思路：我们以3/7举例，下面是手写的常规除法的计算过程。

比如n=4时，我们计算的是小数第四位，那么很明显就是40除于7的值，所以我们只需要知道第四位小数对应的哪个被除数是谁就行，用变量sa表示被除数，则第一位小数就是sa/7,余数就是下一个小数对应的被除数，那么用余数更新sa，一次类推可以计算出所有的小数，注意上图第一个被除数30如果在下面再次出现则容易知道接下来会重复计算，意味着产生循环节，所以我们可以通过循环节长度更新n，降低时间复杂度。

代码

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int a,b,n;
 8     int sa;
 9     cin >> a >> b >> n;
10     sa=a%b;//初始化sa,sa是求每次相除的余数 
11     for(int i=1;i<=n;i++){
12         sa=sa%b*10;//在本轮循环相除后余数发生改变 
13         //cout << sa <<" "<<sa%b <<" "<<a%b << endl;
14         if(sa%b==a%b){//如果下一次循环（注意sa%b是下一次循环的余数）的余数 等于初始的余数，说明接下来的循环或重复之前的计算 
15             n%=i;//n缩小（这是降低时间复杂度的关键） ， 
16             i=0;//重新开始遍历 
17         }
18     }
19     for(int i=1;i<=3;i++){
20         cout << sa/b;//输出该位置计算结果 ，注意如果是有限小数切sa=0时，接下来都是输出0 
21         sa=sa%b*10;//下一次计算的余数 
22     }
23     return 0;
24 }

但是仔细一想上个代码其实是不完全正确的，或不完美的，虽然可以通过测试系统，因为上个代码默认循环节的第一个数字就是小数点后的第一个数字，但是很许多循环小数并非如此

这是第三个测试用例相除的结果，发现循环节是149，从第四个数字开始，如果我们要查询结果数亿之后的某个数的后三位，上个代码明显超时，所以需考虑循环节不在第一位的情况，

在上个代码上修改如下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t=1;
 4 int array[10];
 5 int compare(int m)//得到循环节开始的下标
 6 {
 7     for(int i=1;i<t;i++){
 8         if(array[i]==m) return i;//此时第二个循环节的第一个数字遇到第一个循环节的第一个数字，返回第一个循环节开始的下标
 9 
10     }
11     return 0;
12 }
13 int main()
14 {
15     int a,b,n;
16     int sa;
17     cin >> a >> b >> n;
18     int m=0;//表示还没遇到循环节
19     int num=0;
20 
21      memset(array,0,sizeof(array));
22     sa=a%b;//初始化sa,sa是求每次相除的余数
23     for(int i=1;i<=n;i++){
24         if(m==0 && i!=1) array[t++]=sa%b;
25         if(m==0 && i==1) array[t++]=sa;
26         sa=sa%b*10;//在本轮循环相除后余数发生改变
27         if(m==0)
28         {
29             int aa=sa%b;
30             num=compare(aa);
31         //    cout << num << endl;
32         }
33         if(num!=0&&m!=1){
34             n%=(i-num+1);
35             n+=(num-1);
36             i=0;
37             m=1;
38         }
39         //if(nu)
40     }
41     for(int i=1;i<=3;i++){
42         cout << sa/b;//输出该位置计算结果 ，注意如果是有限小数切sa=0时，接下来都是输出0
43         sa=sa%b*10;//下一次计算的余数
44     }
45     return 0;
46 }

下面的小demo是计算循环节的，根据上个代码衍生出来的

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t=1;
 4 int array[100];
 5 int compare(int m)//得到循环节开始的下标
 6 {
 7     for(int i=1;i<t;i++){
 8         if(array[i]==m) return i;//此时第二个循环节的第一个数字遇到第一个循环节的第一个数字，返回第一个循环节开始的下标
 9 
10     }
11     return 0;
12 }
13 int main()
14 {
15     //freopen("D:/Data.txt","r",stdin);
16     int a,b;
17     int sa;
18     cin >> a >> b;
19     int num=0;
20     memset(array,0,sizeof(array));
21     sa=a%b;
22     for(int i=1;i<1000;i++){
23         if(sa%b==0) {t=1000; break;}
24         if(i!=1) array[t++]=sa%b;
25         if(i==1) array[t++]=sa;
26         sa=sa%b*10;
27         int aa=sa%b;
28         num=compare(aa);
29         if(num!=0) break;
30 
31     }
32     if(t==1000) cout << "不存在循环节" << endl;
33      else{
34            sa=a%b;
35       for(int i=1;i<=t;i++){
36         if(i>num) cout << sa/b;//输出该位置计算结果 ，注意如果是有限小数切sa=0时，接下来都是输出0
37         sa=sa%b*10;//下一次计算的余数
38     }
39   }
40     return 0;
41 }

历届试题 小数第n位

推荐阅读

历届试题小数第n位