USACO 2.4 Fractions to Decimals


模拟题,将分数转换成带循环节小数形式。
模拟小学算术方法即可。
用一个char数组存储结果。用一个int数组来存储当余数为i时,i除以被除数得到的余数在char数组的索引值。
如果某余数重复出现,说明出现了循环。从该余数第一次出现开始表示循环节即可。只是输出比较麻烦,要小心处理。

#include <iostream>
#include 
<fstream>

using namespace std;

ifstream fin(
"fracdec.in");
ofstream fout(
"fracdec.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int pos[100001];
char result[100010];

void solve()
{
    memset(pos,
-1,sizeof(pos));

    
int n,d;
    
in>>n>>d;

    
int integer = n/d;

    
int start;
    
int cnt = 1;

    
out<<integer<<'.';

    
do{
        cnt
++;
        integer
/=10;
    }
while(integer);

    cnt
++;
    start 
= cnt;

    n
%=d;

    
while(pos[n]==-1){
        pos[n]
=cnt++;
        result[pos[n]] 
= n*10/d+'0';
        n 
= n*10%d;
        
if(n==0break;
    }


    
if(n==0){
        
for(int i=start;i<cnt;++i){
            
out<<result[i];
            
if((i)%76==0)
                
out<<endl;
        }
        
if((cnt-1)%76!=0)
            
out<<endl;
    }
else{
        
int i;
        
for(i=start;i<pos[n];++i){
            
out<<result[i];
            
if(i%76==0)
                
out<<endl;
        }
        
out<<'(';
        i
++;
        
if(i%76==0)
            
out<<endl;
        cnt
++;
        
for(;i<cnt;++i){
            
out<<result[i-1];
            
if(i%76==0)
                
out<<endl;
        }
        
out<<')';
        
out<<endl;
    }
}

int main(int argc,char *argv[])
{
    solve(); 
    
return 0;
}


posted on 2009-06-28 18:49 YZY 阅读(1317) 评论(0)  编辑 收藏 引用 所属分类: AlgorithmUSACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜