擂台：分数化小数
题目描述：
将分数转化为小数，相信很多人都会吧．在计算机中并能直接进行分数运算，需要将分数转换化为浮点数或双精度数才能运算，但这样会导致结果的不精确，那么，这里给定一个分数N/D,N为分子，D为分母(N,D均为整数)，请给出分数精确运算的方法并编程求出N/D的精确小数形式，当然如果这个小数为无限循环小数，则把循环的部分用括号括起来，接着循环的部分则省略不写。比如：
1/3 =0.(3)
22/5=4.4
1/7 =0.(142857)
2/2 =1.0
3/8 =0.375
45/56 =0.803(571428)
算法不难，我自己也写了一个，但不满意，设此擂台，希望强人能给出更好的代码。
我的程序运行效率（数据输出到文件中）：
当N/D=1/100003 time : 0ms
当N/D=1/1000003 time : 16ms
当N/D=1/10000019 time : 1515ms
当N/D=1/50000017 time : 7500ms
当N/D=1/100000007 time : 15094ms
当N/D=1/1000000007 time : 201594ms
[解决办法]
用个hash存每次除下来的余数应该可以了。
[解决办法]
很久没用c++, 代码很烂， 见笑了。
#include <iostream>
#include <map>
#include <cstdlib>
using namespace std;
map <int, int> comp;
int N, D, ar, ar1;
char buff[1024];
int main(int argc, char *argv[])
{
N = atoi(argv[1]);
D = atoi(argv[2]);
ar = N % D;
if (ar == 0) {
cout < <ar < <endl;
exit(0);
}
else {
comp[ar] = 1;
}
cout < <N/D < < ".( ";
while (1) {
while (1) {
ar *= 10;
if (ar > = D) {
break;
}
cout < < '0 ';
}
cout < <ar/D;
ar = ar % D;
if (comp[ar] != 0) {
cout < < ') ';
break;
}
else {
comp[ar] = 1;
}
}
cout < <endl;
return 0;
}
测试了一下， 结果基本是秒出。
[解决办法]
楼上的反例.
1/30 = 0.0(3)
楼上的结果是
0.(033)
[解决办法]
分数一定是有理数
[解决办法]
我的方法,代码就不写啦.
1. 求最大公约数,然后约分.
2. 计算偏移位.具体方法:
用约分后的N/D,
首先计算D有多少个0,每个0算一个偏移.
首先计算D能被2^n的整除的最大n,n偏移.
首先计算D能被5^n的整除的最大n,n偏移.
伪代码: nFirstNum是偏移位数
nFirstNum = 0;
while(D%10 == 0)
{
D %= 10;
nFirstNum++;
}
while(D%5 == 0)
{
D %= 5;
N *= 2;
nFirstNum++;
}
while(D%2 == 0)
{
D %= 2;
N *= 5;
nFirstNum++;
}
下一步打印出前面不循环的数字.
只要拿现在的D/N得到的整数,然后将小数点从最右边向左移动nFirstNum次就可以了,不足的补0.
然后
D=D%N
下面每次出现的就是循环部分了.
按照下面的顺序输出
首先用临时变量记录k=D,记录D
1.输出 "( "
2.D*=10;输出D/N
3.D=D%N,如果(D==k)输出 ") "退出循环,否则到2.
原理嘛,其实就是小学的时候教的怎么把分数转换成循环小数的方法.
时间复杂度和循环小数的位数有关,反正每位都要做一次除法和一次判断,估计没有更快的了.除非有人可以不用除法解决.
[解决办法]
循环节长度即为“指数”：先求欧拉函数，而后求出其约数子集，满足 a^r mod m = 1 最小的 r 即为所求。
[解决办法]
我试了一下Divid by constant优化的作用
为了简单起见，我准备变更一下算法，让最后的循环逆序输出，这样，我们就可以设计一个算法让编译器自己做优化了，
首先我们需要一个能够计算任何数关于10的离散倒数，这个很简单：
unsigned inv(unsigned a, unsigned b){
int s,t;
a=a%b;
if(a==1)return 1;
s=inv(b,a);
t=(s*b-1)/a;
return b-t;
}
unsigned inv10(unsigned p){
return inv(p,10);
}
而且这个代码性能不重要，我就不优化了。
然后我们可以将if(N> 0)里面的代码替换为：
int u=inv10(D);
int w;
int index[10];
longlong cur=N;
for(w=1;w <10;w++){
index[w]=((10-w)*u)%10;
}
printf( "( ");
do{
w = index[cur%10];
cur=(cur+w*D)/10;
// printf( "%d ",w);
}while(cur!=N);
printf( ")%d ",w);
这样，所有的除法运算就已经变成除以常数10了。
很遗憾，我发现这个代码计算速度还是同原先代码几乎一样。
稍微分析一下，就可以知道了，主要原因在于cur被声明为long long,是64为整数，跃出了优化的范围了。
将cur声明改成int后（这样，对于D=100000007就不能使用了，乘法要越界了）
结果对于50000017,计算只需要0.7s了（不输出结果）。同原先4.6秒相比，提高了很多倍。
所以这种优化是非常有效的，只是对数字范围有点要求。
[解决办法]
通过将文件数据分块输出，可以显著加速写文件速度：
比如：
#define BUFFER_LEN (4096)
...
char buf[BUFFER_LEN];
int used=0;
FILE *fout=fopen( "out.txt ", "wb ");
...
do{
int curm10=cur%10;
int curd10=cur/10;
w = index[curm10];
cur=curd10+Dd10*w+(curm10+Dm10*w)/10;
buf[used++]=(char)( '0 '+w);
if(used==BUFFER_LEN){
fwrite(buf,BUFFER_LEN,1,fout);
used=0;
}
// printf( "%d ",w);
}while(cur!=N);
if(used> 0){
fwrite(buf,used,1,fout);
}
...
通过这种修改，包含文件输入输出的df3版本对于1000000007的时间从
2m42s降低到39s.
而我发现在我的计算机上，我简单把输出结果用cp命令复制一份也需要花费同样长的时间，这说明已经没有任何优化机会了。
