ACM UVa 算法题 #202 - Repeating Decimals的解法

题目的Link：ACM UVa #202 - Repeating Decimals

很简单，属于大家都可以做的题目，也就是送分题 ：）

当逐步作除法的时候如果出现了重复的商，那么cycle必然在这个两个重复的商之间，道理我就不多啰嗦了，小学数学嘛

一般的方法是纪录所有商，每算出一个新的便顺序查找看该商是否出现过，复杂度为O(n^2)。为了提高速度，注意到题目中限制除数和被除数<3000，也就是说商必然<3000。那么用一数组便可以纪录某个商是否出现过，可以将速度提高一个数量级，为O(n)。

代码如下：

//
//ACMUVaProblem#202
//http://acm.uva.es/p/v2/202.html
//
//Author:ATField
//Email:[e-mail]
//

#include"stdafx.h"
#include<iostream>
#include<algorithm>

usingnamespacestd;

#defineMAX5000
#defineDISPLAY_LIMIT50
#defineMAX_INT3000

intmain(intargc,char*argv[])
...{
intdigits[MAX+1];
intreminder_exist[MAX_INT];
intreminder_pos[MAX_INT];

while(1)
...{
intnumerator;
intoriginal_numerator;
intdenominator;

cin>>numerator;
if(cin.eof())
return0;

original_numerator=numerator;

cin>>denominator;

intquotient,reminder;

memset(reminder_exist,0,sizeof(reminder_exist));
memset(reminder_pos,0,sizeof(reminder_pos));

quotient=numerator/denominator;
reminder=numerator-quotient*denominator;

intinteger=quotient;

intn=0;
boolfound_cycle=false;
intcycle_pos=MAX;
intcycle_len=0;
while(n<=MAX&&!found_cycle/**//*&&reminder>0*/)
...{
if(reminder_exist[reminder])
...{
cycle_pos=reminder_pos[reminder];
cycle_len=n-cycle_pos;
found_cycle=true;
}
else
...{
reminder_exist[reminder]=1;
reminder_pos[reminder]=n;
}

numerator=reminder*10;

quotient=numerator/denominator;
reminder=numerator%denominator;
digits[n]=quotient;

n++;
}

cout<<original_numerator<<"/"<<denominator<<"="<<integer<<".";
intlimit=min(cycle_pos,DISPLAY_LIMIT);
for(inti=0;i<limit;++i)
cout<<digits[i];

if(cycle_pos<DISPLAY_LIMIT)
...{
cout<<"(";
intlimit=min(n-1,DISPLAY_LIMIT);
for(inti=cycle_pos;i<limit;++i)
cout<<digits[i];
if(n>DISPLAY_LIMIT)
cout<<"...";
cout<<")";
}

cout<<" ";
cout<<""<<cycle_len<<"=numberofdigitsinrepeatingcycle ";
}


return0;
}