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

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

文章目录

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

题目描述

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

输入

  1. 76 25
  2. 5 43
  3. 1 397

输出

(在输出循环节前要输出三个空格)

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

原题(PDF)

在这里插入图片描述


题目分析

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

案例分析

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

解题标程(C)

  1. #include<stdio.h>
  2. #include<string.h>
  3. int r[3005]; //记录所得的商的每一位
  4. int u[3005]; //记录当前余数(即下一个被除数),此时的循环节长度(即商包含整数在内的位数)
  5. int s[3005]; //记录在商第i位时的被除数的值
  6. int main()
  7. {
  8. int n, m, t;
  9. while (scanf("%d%d", &n, &m)!=EOF)
  10. {
  11. memset(r, 0, sizeof(r));
  12. memset(u, 0, sizeof(u));
  13. int count = 0;
  14. int t = n;
  15. //高精,模拟竖式除法(开始)
  16. r[count++] = n/m;
  17. n = n%m;
  18. while (!u[n] && n) //当出现被除数相同的情况时,可认为出现循环节
  19. {
  20. u[n] = count;//存除数对应的循环小数位置,为了找到循环节长度
  21. s[count] = n;//存循环小数位置对应的除数,为了找到循环节的开始位置输出"("
  22. r[count++] = 10 * n / m;//得到余数
  23. n = 10 * n%m;//得到新除数
  24. }
  25. //高精,模拟竖式除法(结束)
  26. //提前输出整数部分
  27. printf("%d/%d = %d",t,m,r[0]);
  28. printf(".");
  29. //循环s数组找到被除数等于最后一次发现相等时的位置,输出左括号(准备处理循环节
  30. for (int i = 1; i < count&&i<=50; i++) //i从1开始,可以统一避免处理整数
  31. {
  32. if (s[i] == n)printf("(");
  33. printf("%d",r[i]); //输出r数组中存放的小数部分的商的每一位值
  34. }
  35. //如果循环节的长度大于50,在输出前50个商的值后输出...
  36. if (count>50)printf("…");
  37. //如果最后可以发现可以整除 即被除数为 0 则循环节为 (0)
  38. if (!n)printf("(0");
  39. printf(")\n");
  40. printf(" %d = number of digits in repeating cycle",!n?1:count-u[n]);
  41. }
  42. return 0;
  43. }

解题标程(CPP)

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

错题总结

模拟竖式运算

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

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

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

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

发表评论

表情:
评论列表 (有 0 条评论,204人围观)

还没有评论,来说两句吧...

相关阅读

    相关 【EOJ】2895循环小数

    这题主要是难在边界处理,有的情况想不到,我自己这个代码,改到后来,我自己都蒙圈了,看来还是加强代码风格。不过我很喜欢用数组模拟hashmap,也是以前用pascal留下的毛病,

    相关 3. 求循环小数

    对于任意的真分数 N/M ( 0 < N < M ),均可以求出对应的小数。如果采用链表表示各个小数,对于循环节采用循环链表表示,则所有分数均可以表示为如下链表形式。 ![循