循环小数(Repeating Decimals, ACM/ICPC World Finals 1990,UVa202)题解

我就是我 2022-12-28 04:25 118阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
     *  输出
     *  原题（PDF）
     *  题目分析
     *  案例分析
     *  解题标程（C）
     *  解题标程（CPP）
     *  错题总结
     *   *  模拟竖式运算

--------------------

# 题目描述 #

输入整数 a 和 b （0≤ a ≤3000,1≤ b ≤3000），输出a/b的循环小数表示以及循环节的长度。例如 a = 5， b = 43 小数表示为0.(116279069767441860465)，循环节长度为21。 补充： 如果循环节超过50位，就在第50位后打省略号（三个点，就像“…”）

## 输入 ##

76 25  
    5 43  
    1 397

## 输出 ##

（在输出循环节前要输出三个空格）

76/25 = 3.04(0)  
    1 = number of digits in repeating cycle  
    5/43 = 0.(116279069767441860465)  
    21 = number of digits in repeating cycle  
    1/397 = 0.(00251889168765743073047858942065491183879093198992...)  
    99 = number of digits in repeating cycle

--------------------

## 原题（PDF） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

--------------------

## 题目分析 ##

本题用**模拟竖式除法，求高精度小数**。  
本题 *关键在于当某一余数（即被除数）再次出现时，即表示第二次循环的开始*

## 案例分析 ##

> 1、如果所给 a,b 可整除，则其循环节为 (0) ，循环节长度为 1  
> 2、如果循环节长度超过50，那么先输出前50位小数再输出 “…”  
> 3、输出的格式，在输出循环长度前要加三个空格 ‘ ’

## 解题标程（C） ##

#include<stdio.h>
    #include<string.h>
     
    int r[3005];    //记录所得的商的每一位
    int u[3005];    //记录当前余数（即下一个被除数），此时的循环节长度（即商包含整数在内的位数）
    int s[3005];    //记录在商第i位时的被除数的值
     
    int main()
    {
        
        int n, m, t;
        while (scanf("%d%d", &n, &m)!=EOF)
        {
        
            memset(r, 0, sizeof(r));
            memset(u, 0, sizeof(u));
            int count = 0;
            int t = n;
            
            //高精，模拟竖式除法(开始)
            r[count++] = n/m;
            n = n%m;
            while (!u[n] && n)      //当出现被除数相同的情况时，可认为出现循环节
            {
        
                u[n] = count;//存除数对应的循环小数位置，为了找到循环节长度
                s[count] = n;//存循环小数位置对应的除数，为了找到循环节的开始位置输出"("
                r[count++] = 10 * n / m;//得到余数
                n = 10 * n%m;//得到新除数
            }
            //高精，模拟竖式除法(结束)
            
            //提前输出整数部分
            printf("%d/%d = %d",t,m,r[0]);
            printf(".");
            
            //循环s数组找到被除数等于最后一次发现相等时的位置，输出左括号(准备处理循环节
            for (int i = 1; i < count&&i<=50; i++)  //i从1开始，可以统一避免处理整数
            {
        
                if (s[i] == n)printf("(");
                printf("%d",r[i]);  //输出r数组中存放的小数部分的商的每一位值
            }
            
            //如果循环节的长度大于50，在输出前50个商的值后输出...
            if (count>50)printf("…");
            
            //如果最后可以发现可以整除 即被除数为 0 则循环节为 (0)
            if (!n)printf("(0");
            printf(")\n");
            
            printf("   %d = number of digits in repeating cycle",!n?1:count-u[n]);
     
        }
        
        
        return 0;
    }

## 解题标程（CPP） ##

#include <cassert>      //assert()函数的来源
    #include <cstring>
    #include <cstdio>
    #include <functional>
    #include <algorithm>
    #include <string>       //string ans 来源
    #include <map>          //map容器来源
    using namespace std;
    
    const int MAXN = 3000 + 5;
    //一对一的关系，实际记录了被除数是否出现过的情况
    //并且在判断是否出现过的同时，记录此被除数在第几个次上商时出现
    map<int,int> Pos;
    
    void solve(int n, const int d, string& ans, int& r) {
        
        assert(n%d && n<d);     //assert()当不满足条件时终止程序
        ans = ".";
        Pos.clear();    //删除map中的所有元素
    
        while(true) {
           //恒为真，直到出现循环节或者最后被除数为0才挑出循环
            n *= 10;        //产生新被除数
            int p = Pos[n];
            
            if(p == 0)
                Pos[n] = ans.size(); //为零，即未出现过
            else{
                                   //不为零时，即同一个被除数出现第二次
                r = ans.size() - p; // 找到循环节
                if(r > 50) ans.erase(p + 50), ans += "..."; //大于50时，删除50位后的数字输出...
                ans.insert(p, "("); //在第一次出现此被除数的上商位置插入'('
                ans += ')';     //在字符串末尾插入')'
                break;
            }
            
            if(n < d) {
         ans += '0'; continue; } // 补0
            
            int div = n/d, mod = n%d;   //求新商和余数
            ans += (char)(div + '0');   //上商
            n = mod;        //准备处理新被除数
            if(n == 0) {
         ans += "(0)"; r = 1; break; }  //如果在除了几次后发现被除数为0，则直接在ans后加上(0)即可
        }
    }
    
    int main(){
        
        int a, b;
        while(scanf("%d%d", &a, &b) == 2) {
        
            string ans = ".(0)";
            int r = 1;              // 循环节长度
            if(a%b) //无法整除为整数，否则就会输出.(0)
                solve(a%b, b, ans, r);
            
            printf("%d/%d = %d%s\n", a, b, a/b, ans.c_str());
            printf("   %d = number of digits in repeating cycle\n\n", r);
        }
        
        return 0;
    }

--------------------

## 错题总结 ##

### 模拟竖式运算 ###

int n;    //被除数
    int m;    //除数
    scanf("%d %d",&n,&m);
    
    printf("%d.",n/m);   //整数部分
    
    while(n){
        
      printf("%d",n*10/m);    //生成新的商
      n=n*10%m;   //生成新的被除数
    }

> 2、**只有当被除数出现重复时就表示出现循环节**，这是本题解题的关键。  
> 3、map容器的用法

此用法原文链接：https://blog.csdn.net/love20165104027/article/details/81515466

//头文件
    #include <map>
    
    //基本操作
    begin() 返回指向 map 头部的迭代器
    clear(） 删除所有元素
    count() 返回指定元素出现的次数
    empty() 如果 map 为空则返回 true
    end() 返回指向 map 末尾的迭代器
    erase() 删除一个元素
    find() 查找一个元素
    insert() 插入元素
    key_comp() 返回比较元素 key 的函数
    lower_bound() 返回键值>=给定元素的第一个位置
    max_size() 返回可以容纳的最大元素个数
    rbegin() 返回一个指向 map 尾部的逆向迭代器
    rend() 返回一个指向 map 头部的逆向迭代器
    size() 返回 map 中元素的个数
    swap() 交换两个 map
    upper_bound() 返回键值>给定元素的第一个位置
    value_comp() 返回比较元素 value 的函数

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/76374052f22d4251956df45d0e4fe0f1.png