一、问题
在计算机中，使用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.3）/ 无限循环小数（例：0.333(3333)，这里循环节在括号内标记）
输入使用的数据结构：X = c[0]c[1]c[2]c[3]c[4]....a[0]a[1][a2][a3][a4]...(b[0]b[1]b[2]b[3]b[4]...)，这里数组abc每个元素只保留输入中的一位，每个元素大小范围为0-9，数组c存储整数部分，数组b存储循环节部分，数组a存储小数部分，这些数组有效长度由输入的数据多少来确定。（例：c[0] = 0 a[1] = 3 len(c) = 1 len(a) = 1 len(b) =
0，表示0.3）
输出：分数（例：3/10 ；1/3）
输出使用的数据结构：Y = [a b] ，a存储分子，b存储分母。（例a = 3, b = 10 表示分数 3/10）
约束：分母最小的分数形式（因分数表达有多种，这里限制了唯一的输出）；输入数据含有多种表达方式来表达同一个浮点数：如0.3（3）和0.3（33）。
二、解法
思考：
1.小数可以分解为一个整数和一个纯小数之和，我们先求解纯小数使之表示为分数，再把分母乘以这个整数与分子相加得到新的数作为分子，就可以求得含有整数部分的小数了。（《编程之美》也提及分解）
2.我们把一个纯小数表示成分数后，要使分母在所有分数表示形式中最小，我们只需要求出该分数分母和分子的最大公约数，并让分数与分母同时除以它求可求得分母最小的分数形式。（《编程之美》也提及约分）
3.我们先考虑有限小数的情况，我们可以将有限小数进行N次乘10运算直到无小数位，再令其与10^N进行约分，即除以它们的最大公约数来得到解；对于无限小数，我们针对小数部分考虑将含循环节的小数部分的数据根据循环解扩大多位，并按照有限小数来求解，但是始终会丢失一定的精度，取决于计算机能够存储的位数，尚有不足之处。（需向《编程之美》学习）
《编程之美》对处理无限循环小数进行了更细致的分解和转换，不同上面思考的第3点部分，它成功的把循环节表示为分数的形式，这一点我并没有认真考虑：
分解及转换过程：
（设无限循环小数写作：X = 0.a1a2a3...an(b1b2b3...bm)）
X = 0.a1a2a3...an(b1b2b3..bm)
=> 10^n * X = a1a2a3...an.(b1b2b3..bm) = a1a2a3...an + Y
=> X = (a1a2a3...an + Y) / (10^n)
其中Y为无限循环部分，由於是无限循环，故有：（这部分推导很关键，能够正确将无限长的循环节转换为有限长度的分母表示）
Y = 0.b1b2b3...bm
=> 10^m * Y = b1b2b3...bm + Y（关键是这个Y值）
=> Y = b1b2b3..bm / (10^m - 1)
结合两个式子得出：
X = (a1a2a3...an * (1o^m -1） + b1b2b3...bm) / ((10^m - 1)* 10^n)
算法C实现：
1.辅助算法：考虑到分母很可能是比较大的数以及又是偶数，采用Stein算法求解分子与分母的最大公约数，这部分算法详见博文：《编程之美》学习笔记——最大公约数问题
2.数据结构：考虑的输入的整数部分，小数部分，循环节部分，在算法处理过程中总是按块（三块）处理，块内部数据（不同的位）并不分离，因此，将它们存储成3个整数，并且通过算法判断这3个整数的位数，而不采用数组形式按位一个个存储（问题分析中提及了这种形式的数据结构）。这里需要注意的是整数部分可正可负，小数和循环节部分均为正值或0
3.辅助算法：实现10的n次幂的求值而不调用<math.h>中的函数。
4.辅助算法：实现十进制N的位数的求值。
3.数据溢出：分析算法时我们可以发现输出的分母未进行约分时可能是很大的整数，为了避免数据溢出，采用long型数据结构存储，但对于一些循环节位数比较多或小数位数比较多的输入仍然可能导致数据溢出并使求解出错。
/**
* @file accurate_float_expression.c
* @brief accurate expression of of floating point number including
* the repeating decimal numbers.
* Ex: 0.3 -> 3 / 10 ; 0.3(3) -> 1 / 3
* @author chenxilinsidney
* @version 1.0
* @date 2015-01-18
*/
#include <stdlib.h>
#include <stdio.h>
// #define NDEBUG
#include <assert.h>
// #define NDBG_PRINT
#include "debug_print.h"
typedef long TYPE;
/**
* @brief get greatest common divisor(gcd) for value m and n.
*
* @param[in] m first value
* @param[in] n second value
*
* @return gcd value
*/
TYPE gcd(TYPE m, TYPE n)
{
/// m and n range limits
assert(m >= 0 && n >= 0);
if (m < n)
return gcd(n, m);
else if (n == 0)
return m;
if (m & 1) {
if (n & 1)
return gcd(n, (m - n) >> 1);
else
return gcd(m, n >> 1);
} else {
if (n & 1)
return gcd(m >> 1, n);
else
return gcd(m >> 1, n >> 1) << 1;
}
}
/**
* @brief get pow(10, num) as in math.h
*
* @param[in] num power value
*
* @return power result
*/
TYPE ten_pow(TYPE num)
{
assert(num >= 0);
TYPE pow = 1;
while (num--) pow *= 10;
return pow;
}
/**
* @brief count the decimal number digit
*
* @param[in] decimal_number input number
*
* @return digit count
*/
TYPE count_decimal_digit(TYPE decimal_number)
{
TYPE digit = 1;
while((decimal_number /= 10) != 0) digit++;
return digit;
}
/**
* @brief accurate expression for floating point numbers.
*
* @param[in] value_integer integer part of floating number
* @param[in] value_decimal decimal part of floating number
* @param[in] value_repeating repeating part of floating number
* @param[out] numerator numerator of the output fractional number
* @param[out] denominator denominator of the output fractional number
*/
void accurate_float_expression(TYPE value_integer, TYPE value_decimal,
TYPE value_repeating, TYPE* numerator, TYPE* denominator)
{
/// reasonable input range
assert(value_repeating >= 0 && value_decimal >= 0 && numerator != NULL &&
denominator != NULL);
/// get the decimal digit
TYPE digit_decimal = count_decimal_digit(value_decimal);
TYPE digit_repeating = count_decimal_digit(value_repeating);
/// detect if integer part is positive
TYPE flag_positive = 1;
/// get absolute integer part
if (value_integer < 0) {
value_integer *= -1;
flag_positive = -1;
}
/// get denominator and numerator
if (value_repeating == 0) {
*denominator = ten_pow(digit_decimal);
*numerator = value_integer * *denominator + value_decimal;
} else {
*denominator = ten_pow(digit_decimal) * (ten_pow(digit_repeating) - 1);
*numerator = value_integer * *denominator + value_repeating +
value_decimal * (ten_pow(digit_repeating) - 1);
}
/// get gcd of denominator and numerator
TYPE value_gcd = gcd(*denominator, *numerator);
/// get final value of numerator and denominator
*numerator = flag_positive * *numerator / value_gcd;
*denominator /= value_gcd;
}
int main(void) {
/// get floating point number
TYPE value_integer;
TYPE value_decimal;
TYPE value_repeating = 0;
TYPE value_count;
printf("input the floating point number integer(Ex:0.3 / 0.3(3)): \n");
if(((value_count = scanf("%ld.%ld(%ld)", &value_integer,
&value_decimal, &value_repeating)) != 2 &&
value_count != 3) || value_decimal < 0 ||
value_repeating < 0) {
DEBUG_PRINT_STATE;
DEBUG_PRINT_STRING("can not get the right value.\n");
DEBUG_PRINT_VALUE("%ld", value_integer);
DEBUG_PRINT_VALUE("%ld", value_decimal);
DEBUG_PRINT_VALUE("%ld", value_repeating);
DEBUG_PRINT_VALUE("%ld", value_count);
fflush(stdout);
assert(0);
exit(EXIT_FAILURE);
}
/// get accurate expression
TYPE numerator;
TYPE denominator;
accurate_float_expression(value_integer, value_decimal, value_repeating,
&numerator, &denominator);
/// output result
printf("accurate expression for floating point number is: \n%ld / %ld\n",
numerator, denominator);
return EXIT_SUCCESS;
}
备注：
1.转载请注明出处：http://blog.csdn.net/chensilly8888/
2.全文源码均开源（在UBUNTU + GCC4.8.2下编译并测试通过），可下载或查看：https://github.com/chenxilinsidney/funnycprogram/tree/master/beauty_of_programming/accurate_float_expression
3.有写错或写漏之处请指正，谢谢！