历届试题小数第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，降低时间复杂度。

代码

 #include<bits/stdc++.h>

 using namespace std;

 int main()

 {

     int a,b,n;

     int sa;

     cin >> a >> b >> n;

     sa=a%b;//初始化sa,sa是求每次相除的余数

     for(int i=;i<=n;i++){

         sa=sa%b*;//在本轮循环相除后余数发生改变

         //cout << sa <<" "<<sa%b <<" "<<a%b << endl;

         if(sa%b==a%b){//如果下一次循环（注意sa%b是下一次循环的余数）的余数 等于初始的余数，说明接下来的循环或重复之前的计算

             n%=i;//n缩小（这是降低时间复杂度的关键） ，

             i=;//重新开始遍历

         }

     }

     for(int i=;i<=;i++){

         cout << sa/b;//输出该位置计算结果 ，注意如果是有限小数切sa=0时，接下来都是输出0

         sa=sa%b*;//下一次计算的余数

     }

     return ;

 }

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

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

在上个代码上修改如下

 #include<bits/stdc++.h>

 using namespace std;

 int t=;

 int array[];

 int compare(int m)//得到循环节开始的下标

 {

     for(int i=;i<t;i++){

         if(array[i]==m) return i;//此时第二个循环节的第一个数字遇到第一个循环节的第一个数字，返回第一个循环节开始的下标

     }

     return ;

 }

 int main()

 {

     int a,b,n;

     int sa;

     cin >> a >> b >> n;

     int m=;//表示还没遇到循环节

     int num=;

      memset(array,,sizeof(array));

     sa=a%b;//初始化sa,sa是求每次相除的余数

     for(int i=;i<=n;i++){

         if(m== && i!=) array[t++]=sa%b;

         if(m== && i==) array[t++]=sa;

         sa=sa%b*;//在本轮循环相除后余数发生改变

         if(m==)

         {

             int aa=sa%b;

             num=compare(aa);

         //    cout << num << endl;

         }

         if(num!=&&m!=){

             n%=(i-num+);

             n+=(num-);

             i=;

             m=;

         }

         //if(nu)

     }

     for(int i=;i<=;i++){

         cout << sa/b;//输出该位置计算结果 ，注意如果是有限小数切sa=0时，接下来都是输出0

         sa=sa%b*;//下一次计算的余数

     }

     return ;

 }

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

 #include<bits/stdc++.h>

 using namespace std;

 int t=;

 int array[];

 int compare(int m)//得到循环节开始的下标

 {

     for(int i=;i<t;i++){

         if(array[i]==m) return i;//此时第二个循环节的第一个数字遇到第一个循环节的第一个数字，返回第一个循环节开始的下标

     }

     return ;

 }

 int main()

 {

     //freopen("D:/Data.txt","r",stdin);

     int a,b;

     int sa;

     cin >> a >> b;

     int num=;

     memset(array,,sizeof(array));

     sa=a%b;

     for(int i=;i<;i++){

         if(sa%b==) {t=; break;}

         if(i!=) array[t++]=sa%b;

         if(i==) array[t++]=sa;

         sa=sa%b*;

         int aa=sa%b;

         num=compare(aa);

         if(num!=) break;

     }

     if(t==) cout << "不存在循环节" << endl;

      else{

            sa=a%b;

       for(int i=;i<=t;i++){

         if(i>num) cout << sa/b;//输出该位置计算结果 ，注意如果是有限小数切sa=0时，接下来都是输出0

         sa=sa%b*;//下一次计算的余数

     }

   }

     return ;

 }

巴特西

历届试题小数第n位

最新文章

热门文章

巴特西

历届试题 小数第n位

最新文章

热门文章

历届试题小数第n位