题目的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;
}
// 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;
}