题目的Link：ACM UVa #202 - Repeating Decimals
很简单，属于大家都可以做的题目，也就是送分题 ：）
当逐步作除法的时候如果出现了重复的商，那么cycle必然在这个两个重复的商之间，道理我就不多啰嗦了，小学数学嘛
一般的方法是纪录所有商，每算出一个新的便顺序查找看该商是否出现过，复杂度为O(n^2)。为了提高速度，注意到题目中限制除数和被除数<3000，也就是说商必然<3000。那么用一数组便可以纪录某个商是否出现过，可以将速度提高一个数量级，为O(n)。
代码如下：
// // ACM UVa Problem #202 // http://acm.uva.es/p/v2/202.html // // Author: ATField // Email: atfield_zhang@hotmail.com // #include " stdafx.h " #include < iostream > #include < algorithm > using namespace std; #define MAX 5000 #define DISPLAY_LIMIT 50 #define MAX_INT 3000 int main( int argc, char * argv[]) ... { int digits[MAX + 1]; int reminder_exist[MAX_INT]; int reminder_pos[MAX_INT]; while(1) ...{ int numerator; int original_numerator; int denominator; cin >> numerator; if( cin.eof() ) return 0; original_numerator = numerator; cin >> denominator; int quotient, reminder; memset( reminder_exist, 0, sizeof(reminder_exist) ); memset( reminder_pos, 0, sizeof(reminder_pos) ); quotient = numerator / denominator; reminder = numerator - quotient * denominator; int integer = quotient; int n = 0; bool found_cycle = false; int cycle_pos = MAX; int cycle_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 << "."; int limit = min(cycle_pos, DISPLAY_LIMIT); for( int i = 0; i < limit; ++i ) cout << digits[i]; if( cycle_pos < DISPLAY_LIMIT ) ...{ cout << "("; int limit = min(n - 1, DISPLAY_LIMIT); for( int i = cycle_pos; i < limit; ++i ) cout << digits[i]; if( n > DISPLAY_LIMIT ) cout << "..."; cout << ")"; } cout << " "; cout << " " << cycle_len << " = number of digits in repeating cycle "; } return 0;}
