编程之美2.6——精确表达浮点数

问题：
用分数形式来表示小数，以达到精确的计算结果。

解答一：
用于小整数，将无限循环小数0.a1a2...an(b1b2...bm)分为非循环部分和循环部分。
X=((a1a2...an)*(10^m-1)+b1b2...bm)/((10^m-1)*10^n)
[cpp]
#include <iostream>

using namespace std;

long long gcd(long long a, long long b)
{
    if (a < b)
    {
        long long tmp = a;
        a = b;
        b = tmp;
    }
    int i, k=0;
    while (b!=0)
    {
        if ((a&1) == 0)
        {
            if ((b&1) == 0)
            {
                // a,b均是偶数，f(a,b)=2*f(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 < b)
        {
            long long tmp = a;
            a = b;
            b = tmp;
        }
    }
    return a << k;
}

int main()
{
    long long a=0, b=0, c=0;
    // 整数部分c，非循环小数a，循环小数b
    scanf("%d.%d(%d)",&c, &a, &b);
    if (a==0 && b==0)
        cout << c;
    else
    {
        // 分子up，分母down
        long long up = c;
        long long down = 1;
        long long ta = a;
        while (ta)
        {
            down *= 10;
            ta /= 10;
        }
        up = c*down+a;
        if (b!=0)
        {
            long long wb = 1;
            long long tb = b;
            while (tb)
            {
                wb *= 10;
                tb /= 10;
            }
            up = up*(wb-1)+b;
            down = down*(wb-1);
        }
        long long fac = gcd(up, down);
        cout << up/fac << "/" << down/fac << endl;
    }
}

解答二：
用于大整数，定义了大整数类型，以及对应的加减乘除、比较移位运算。

[cpp]
#include <iostream>
#include <cstring>
#include <string>
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 << x.s[i];
}

// 字符串转大整数
void Str2HP(const char *s, HP &x)
{
    x.len = strlen(s);
    for (int i=1; i<=x.len; i++)
        x.s[i] = s[x.len-i] - '0';
    if (x.len == 0)
    {
        x.len = 1;
        x.s[1] = 0;
    }
}

// 大整数的加法
void Plus(const HP a, const HP b, HP &c)
{
    int i; c.s[1] = 0;
    // 大整数a,b的加法操作和结果c的进位操作
    for (i=1; i<=a.len || i<=b.len || c.s[i]; i++)
    {
        if (i <= a.len) c.s[i] += a.s[i];
        if (i <= b.len) c.s[i] += b.s[i];
        c.s[i+1] = c.s[i]/10; c.s[i] %= 10;
    }
    // 退出循环到原因是c.s[i]==0，所以取前一位
    c.len = i

补充：软件开发 , C++ ,