【问题描述】： 在计算机中，使用float或者double来存储小数是不能得到精确的。如果你希望得到精确计算结果，最好是用分数形式来表示小数。有限小数或者无限循环小数都可以转化为分数。比如： 0.9 = 9/10 0.333（3）= 1/3（括号中的数字表示是循环节） 当然
【问题描述】：
在计算机中，使用float或者double来存储小数是不能得到精确值的。如果你希望得到精确计算结果，最好是用分数形式来表示小数。有限小数或者无限循环小数都可以转化为分数。比如：
0.9 = 9/10
0.333（3）= 1/3（括号中的数字表示是循环节）
当然一个小数可以用好几种分数形式来表示。如：
0.333（3）= 1/3 = 3/9
给定一个有限小数或者无限循环小数，你能否以分母最小的分数形式来返回这个小数呢？如果输入为循环小数，循环节用括号标记出来。下面是一些可能的输入数据，如0.3、0.30、0.3（000）、0.3333（3333）、……
解法：
拿到这样一个问题，我们往往会从最简单的情况入手，因为所有的小数都可以分解成一个整数和一个纯小数之和，不妨只考虑大于 0 ，小于 1 的纯小数，且暂时不考虑分子和分母的约分，先设法将其表示为分数形式，然后再进行约分。题目中输入的小数，要么为有限小数 X =0. a 1 a 2 … an ，要么为无限循环小数 X =0. a 1 a 2 … an （ b 1 b 2 … bm ）， X 表示式中的字母 a 1 a 2 … an ， b 1 b 2 … bm 都是 0~9 的数字，括号部分（ b 1 b 2 … bm ）表示循环节，我们需要处理的就是以上两种情况。
对于有限小数 X =0. a 1 a 2 … an 来说，这个问题比较简单， X 就等于（ a 1 a 2 … an ） /10 n 。
对于无限循环小数 X =0. a 1 a 2 … an （ b 1 b 2 … bm ）来说， 其复杂部分在于小数点后同时有非循环部分和循环部分，我们可以做如下的转换：
X = 0. a 1 a 2 … an （ b 1 b 2 … bm ）
10 n * X = a 1 a 2 … an . （ b 1 b 2 … bm ）
10 n * X = a 1 a 2 … an +0. （ b 1 b 2 … bm ）
X = （ a 1 a 2 … an +0. （ b 1 b 2 … bm ）） /10 n
对于整数部分 a 1 a 2 … an ，不需要做额外处理，只需要把小数部分转化为分数形式再加上这个整数即可。对于后面的无限循环部分，可以采用如下方式进行处理：
令 Y =0. b 1 b 2 … bm ，那么
10 m * Y = b 1 b 2 … bm . （ b 1 b 2 … bm ）
10 m * Y = b 1 b 2 … bm +0. （ b 1 b 2 … bm ）
10 m * Y - Y = b 1 b 2 … bm
Y = b 1 b 2 … bm / （ 10 m - 1 ）
将 Y 代入前面的 X 的等式可得：
X = （ a 1 a 2 … an + Y ） /10 n
= （ a 1 a 2 … an + b 1 b 2 … bm / （ 10 m - 1 ）） /10 n
= （（ a 1 a 2 … an ） * （ 10 m - 1 ） + （ b 1 b 2 … bm ）） / （（ 10 m - 1 ） *10 n ）
至此，便可以得到任意一个有限小数或无限循环小数的分数表示，但是此时分母未必是最简的，接下来的任务就是让分母最 小，即对分子和分母进行约分，这个相对比较简单。对于任意一个分数 A / B ，可以简化为（ A /Gcd （ A , B ）） / （ B /Gcd （ A , B ）），其中 Gcd 函数为求 A 和 B 的最大公约数，这就涉及本书中的算法（ 2.7 节“最大公约数问题”），其中有很巧妙的解法，请读者阅读具体的章节，这里就不再赘述。
综上所述，先求得小数的分数表示方式，再对其分子分母进行约分，便能够得到分母最小的分数表现形式。
例如，对于小数 0.3 （ 33 ），根据上述方法，可以转化为分数：
0.3 （ 33 ）
= （ 3 * （ 102 - 1 ） + 33 ） / （（ 102 - 1 ） *10 ）
= （ 3*99+33 ） /990
= 1 / 3
对于小数 0. 285714 （ 285714 ），我们也可以算出：
0. 285714 （ 285714 ）
= （ 285714 * （ 106 - 1 ） + 285714 ） / （（ 106 - 1 ） *106 ）
= （ 285714*999999 +285714 ） / 999999000000
= 285714 / 999999
= 2/7
以下给出代码，简单实现：
void Cal(char* str)
{
char *p=str;
char *q=str,*q1=str;//q和q1分别存储(和)的指针
while(*p!='\0')
{
if(*p=='(')
{
q=p;
}
if(*p==')')
{
q1=p;
}
p++;
}
if(q==q1)
{
cout
为了更完善，分两种情况：
1、对于小数的情况，不用定义数组形式：
#include
using namespace std;
long long gcd(long long a, long long b)
{
if (a >1,b>>1)
a >>= 1;
b >>= 1;
k++;
}
else
// a为偶数，b为奇数，f(a,b)=f(a>>1,b)
a >>= 1;
}
else
{
if ((b&1) == 0)
// a为奇数，b为偶数，f(a,b)=f(a,b>>1)
b >>= 1;
else
// a,b均是奇数，f(a,b)=f(a-b,b)
a = a-b;
}
if (a
2、 用于大整数，定义了大整数类型，以及对应的加减乘除、比较移位运算
#include
#include
#include
using namespace std;
// 大整数类型
#define MAXLEN 1000
struct HP {int len, s[MAXLEN];};
void PrintHP(HP x)
{
for (int i=x.len; i>=1; i--)
cout 1 && !c.s[c.len]) c.len--;
}
// 大整数的比较
int HPCompare(const HP &x, const HP &y)
{
if (x.len > y.len) return 1;
if (x.len 1 && (x.s[i]==y.s[i])) i--;
return x.s[i] - y.s[i];
}
// 大整数的乘法
void Multi(const HP a, const HP b, HP &c)
{
int i, j;
// 对乘法结果赋初值，以方便之后的+=运算
c.len = a.len + b.len;
for (i=1; i 1 && !c.s[i]) i--;
c.len = i;
}
// 大整数的除法
void Divide(const HP a, const HP b, HP &c, HP &d)
{
int i, j;
// 用余数d存被除数a的前i位数据，用来多次减去除数b，以得到商c
d.len = 1; d.s[1] = 0;
for (i=a.len; i>0; i--)
{
if (!(d.len == 1 && d.s[1] == 0))
{
// i没移一位，余数d也移位
for (j=d.len; j>0; j--)
d.s[j+1] = d.s[j];
d.len++;
}
d.s[1] = a.s[i];
c.s[i] = 0;
// 余数d大于除数b时，才可以进行减操作
while ((j=HPCompare(d,b)) >= 0)
{
Subtract(d, b, d);
c.s[i]++;
if (j == 0) break;
}
}
c.len = a.len;
while (c.len > 1 && c.s[c.len] == 0)
c.len--;
}
// 十进位右移
void RightShift(HP &x, int k)
{
for (int i=1; i =1; i--)
x.s[i+k] = x.s[i];
for (i=k; i>=1; i--)
x.s[i] = 0;
x.len += k;
}
// 求大整数的最大公约数
void GCD(HP a, HP b, HP &c)
{
if (b.len == 1 && b.s[1] == 0)
{
c.len = a.len;
memcpy(c.s, a.s, (a.len+1)*sizeof(int));
}
else
{
HP m, n;
Divide(a, b, m, n);
GCD(b, n, c);
}
}
int main()
{
string str;
string strc, stra, strb;
cin >> str;
int posc = str.find('.');
int posa = str.find('(');
int posb = str.find(')');
strc = str.substr(0, posc);
if (posc = 0)
{
strb = str.substr(posa+1, posb-posa-1);
// 循环部分
Str2HP(strb.c_str(), b);
HP m = tmp;
LeftShift(m, strb.size());
Subtract(m, tmp, m);
// 乘以10^(|b|-1)
Multi(up, m, up);
Plus(up, b, up);
Multi(down, m, down);
}
// 求分子分母的最大公约数
GCD(down, up, tmp);
HP h;
Divide(down, tmp, down, h);
Divide(up, tmp, up, h);
PrintHP(up); cout
查看更多关于【编程之美】2.6精确表达浮点数的详细内容...
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did157989