【蓝桥杯】有理数的循环节

有理数的循环节

1 / 7 = 0.142857142 ⋯ ⋯ 1/7 = 0.142857142 \cdots\cdots 1/7=0.142857142⋯⋯ 是个无限循环小数。

任何有理数都可以表示为无限循环小数的形式。

题目要求即是:给出一个数字的循环小数表示法。

输入描述
输入一行,两个整数。
每个整数范围均为:1 ~ 1000。

输出描述
输出两个整数做除法产生的小数或无限循环小数(循环节用方括号括起)。

输入输出样例
示例
输入

1,7

输出

0.[142857]

思路

  • 先模拟手算,找规律,这里不妨用题目所给的例子: 1 ÷ 7 1 \div 7 1÷7
    • 1除以7,商0余1,点上小数点,余数不为0,则把余数1乘以10之后继续除以7(即“添0继续除”)
    • 10除以7,商1余3,余数不为0,添0继续除
    • 30除以7,商4余2,余数不为0,添0继续除
    • 20除以7,商2余6,余数不为0,添0继续除
    • 60除以7,商8余4,余数不为0,添0继续除
    • 40除以7,商5余5,余数不为0,添0继续除
    • 50除以7,商7余1,余数不为0,添0继续除
    • ⋯ ⋯ \cdots\cdots ⋯⋯

到这里,可能已经看出规律了,再继续除下去的话就循环起来了,则已经找出了循环节

  • 然后发现,循环节的最后一个数出现的时候,其对应的余数恰好是出现过的,而这个余数上一次出现时乘10除以除数得到的商恰好是循环节的第一个数
  • 这样问题就差不多解决了,因为已经确定了循环节的首尾位置
  • 由于题目还要求输出中括号,所以商用一个数组来存放比较方便
  • 怎么知道余数已经出现过了?怎么确定循环节的第一个数字?
  • 综合考虑,选用哈希表记录出现过的余数,并且将余数和小数点后的位号(数组下标)建立联系,方便确定循环节
  • 通过模拟,应该还能得出一个显然的规律:当相除的结果是无限循环小数时,最后一个数字一定是循环节的最后一个数字,且最终答案的最后一个字符一定是 ] ] ];而除得尽的话,就直接输出结果就行,但是依然要用数组来存放,因为好判断是否能除尽
  • 将商的整数部分和小数部分分开比较好

代码如下

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<int, int> mp;  //余数<->下标
vector<int> data;            //存放小数部分的数组
int n, m;                    //分子,分母

void solve() {
    int res = 0;  //整数部分商
    int t = 0;    //下标
    scanf("%d,%d", &n, &m);//坑点,要把逗号加进去
    //处理整数部分
    res = n / m;
    n %= m;
    mp[n] = t++;
    //处理小数部分
    while (true) {
        if (n == 0) {
        //这是除得尽的情况
            printf("%d.", res);//整数部分
            //小数部分全部输出
            for (int i = 0; i < int(data.size()); i++) {
                printf("%d", data.at(i));
            }
            printf("\n");
            break;
        }
        n *= 10;//添0继续除
        data.push_back(n / m);//商
        n %= m;//余数更新被除数
        //余数不为0且余数出现过
        if (n && mp.find(n) != mp.end()) {
            printf("%d.", res);//输出整数部分
            //输出循环节之前的小数部分,有些循环小数要等几个数之后才开始循环
            for (int i = 0; i < mp[n]; i++) {
                printf("%d", data.at(i));
            }
            //输出循环节
            printf("[");
            for (int i = mp[n]; i < (int)data.size(); i++) {
                printf("%d", data.at(i));
            }
            printf("]\n");
            break;
        } else {
        //否则加入
            mp[n] = t++;
        }
    }
}

int main(void) {
    solve();
    return 0;
}
上一篇:PHP+mysql开发的图书管理系统 带数据库


下一篇:谈谈PHP反序列基础和简单利用