无限循环小数转化分数

我会带着你远行 2022-05-17 08:49 145阅读 0赞

### 问题 ###

给出一个无限循环小数以及循环节，求原最简分数，例如输入 5.3 1 表示从小数点后一位开始循环，也就是循环小数是5.33333….. 输出结果是 16/3

### 分析 ###

其实一个简单的数学结论就可以解决这个问题，  
循环节有几位，就用循环节比上几个9，例如 3.141414….就用 14/99，3.145145145….就是145/999（当然，还要加上整数部分），如果用代码来实现的话：

#include<stdio.h>
    #include<stdlib.h>
    #include<iomanip> // 字符串与数字进行转化要引用的库
    #include<iostream>
    using namespace std;
    
    int e[10];
    
    int gcd(int a, int b){
        return b==0?a:gcd(b, a%b);
    }
    int main(){
        e[0] = 1;
        for(int i=1; i<10; i++)
            e[i] = e[i-1]*10;
        string str;
        cin>>str;
        int k = str.find('.');      // 小数点的位置
        int cou = str.length()- 1 - k;   //得到小数的位数
        int inte = atoi(str.substr(0, k).c_str());
        // str.substr(a, b) 从原字符串中得到下标a a+b之间长度为b的一段字符串
        // atoi(str.c_str()) 将str转化为整型数
        // 同样的函数还有 atof(), atoll() 分别是转化为float以及long long int
        int deci = atoi(str.substr(k+1, str.length()).c_str());
    
        int g = gcd(deci, e[cou]-1);
        int su = deci / g;
        int sd = (e[cou]-1) / g;
    
        cout<<inte*sd+su<<"/"<<sd<<endl;
    }

上面的代码中有几个地方需要说明，输入的数据我输入的是字符串，这样比较容易进行分离，当然也可以直接输入float，只是个人觉得有些麻烦而已。  
还有几个注意点：

*  字符串的拆分，如果取得字符串中间的一部分，可以使用substr()方法，这个函数可以带一个或者两个参数：

string str = "123456";
        string temp1 = str.substr(3);   //一个参数 即从参数位置一直截取到最后
        cout<<temp1<<endl;  // 456
        string temp2 = str.substr(2,2);  //两个参数 第一个参数是开始截取的位置 第二个参数是长度
                                         // substr(a, b) 也就是截取 a~a+b之间的字符串
                                         //注意第二个参数不是结束位置
        cout<<temp2<<endl;   //34

*  C++中如何将字符串转化为数字类型，当然可以一位一位的累加，只是C++的库函数中已经提供了方法，首先引用`iomanip` 库，对于一个可以转化的字符串，有几个方法，对应不同的数据类型：

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    int main(){
         string a = "1234";
         string b = "123.1233";
         int a1 = atoi(a.c_str());
         float b1 = atof(b.c_str());
         cout<<a1<<endl;
         cout<<b1<<endl;
    
         return 0;
    }

其余的还有atol() 转化的是long int，atoll()转化对应long long int类型，调用的格式是一样的。

*  上面代码中使用了e来保存10,100,1000，这样获得小数的位数之后，减1就可以得到对应的若干个9了，然后求出分子分母的最大公约数然后进行最后的通分即可。

不过这只是对应最基本的一种情况，也就是非常中规中矩的纯循环小数（从小数点后第一位就开始循环的小数），还有一种复杂一点的情况是混循环小数，这也就是题目中指定循环节位置的原因了。  
对于混循环小数，我们计算的时候很容易想到一种方法，就是乘以对应的位，把混循环小数转化为纯循环小数，例如：1.23444…如果我们乘以100，就是123.44…这样转化为纯循环小数来计算就可以了，在编写程序的时候还有另一种方法：  
，有点难解释，数学原理字啊这里就不做解释了。。

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    int e[20];
    int gcd(int a, int b){
        return b==0?a:gcd(b, a%b);
    }
    
    int main(){
        e[0]=1;
        for(int i=1; i<10; i++)
            e[i] = 10 * e[i-1];
        string str;
        int p;
        cin>>str>>p;
        int k = str.find('.');
        int inte = atoi(str.substr(0, k).c_str());  //整数部分
        int deci = atoi(str.substr(k+1).c_str());   //全部的小数部分
        int mid = atoi(str.substr(k+1, p-1).c_str());    //非循环部分的小数
    
        //用个例子 5.123...从3开始循环
        int tmp1 = deci - mid;    // 用小数部分减去非循环的小数 比如使用123 - 12
        int tmp2 = e[str.length()-1-k] - e[p-1];
        //用小数位数 个 10相乘 - 非循环小数部分位数 个 10相乘 比如 123（3位） 12（2位） 所以是 1000 - 100
        int tmp3 = gcd(tmp1, tmp2);        // 分子分母的最大公因数（未计算整数部分）
    
        int fdown = tmp2 / tmp3;     //未加入整数部分 约分之后的分母
        int fup = tmp1 / tmp3;       //未加入整数部分 约分之后的分子
    
        cout<<inte * fdown + fup<<"/"<<fdown<<endl;    //最后结果
    }

把混循环小数转化位纯循环小数的方式会好理解一些吧。。

以上~