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

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