编程之美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++ ,