ACM 202 - Repeating Decimals

#include <stdio.h>
#include <memory.h>

#define MAX 5000
#define DISPLAY_LIMIT 50
#define MAX_INT 3000

int min (int a , int b){
    return a > b ? b : a;
}


int main()
{
    int digits[MAX + 1], remainderExist[MAX_INT], remainderPos[MAX_INT];
    while (1)
    {
        int numerator, denominator, oNumerator, quotient, remainder, recode, i;
        
        if (scanf("%d", &numerator) < 1) break;
        oNumerator = numerator;
        scanf("%d", &denominator);
        
        memset (remainderExist, 0, sizeof(remainderExist));
        memset (remainderPos, 0, sizeof(remainderPos));
        
        quotient = numerator / denominator;
        remainder = numerator % denominator;
        
        recode = quotient;
        int n = 0, isCycle = 0, cyclePos = MAX, cycleLen = 0;
        
        while ( n <= MAX && !isCycle)
        {
            if (remainderExist[remainder] )
            {
                cyclePos = remainderPos[remainder];
                cycleLen = n - cyclePos;
                isCycle = 1;
            }
            else
            {
                remainderExist[remainder] = 1;
                remainderPos[remainder] = n;
            }
            numerator = remainder * 10;
            
            quotient = numerator / denominator;
            remainder = numerator % denominator;
            digits[n] = quotient;
            n ++;
        }
        printf("%d/%d = %d.", oNumerator, denominator, recode);
        int limit = min(cyclePos, DISPLAY_LIMIT);
        
        for (i = 0; i < limit; ++i )
            printf("%d", digits[i]);
        
        if (cyclePos < DISPLAY_LIMIT)
        {
            printf("(");
            limit = min(n - 1, DISPLAY_LIMIT);
            for (i = cyclePos; i < limit; ++i ) 
                printf("%d", digits[i]);
            if (n > DISPLAY_LIMIT)
                printf("...");
            printf(")");         
        }    
        printf("\n");
        printf("   %d = number of digits in repeating cycle\n\n",cycleLen );

    }
    return 0;
}

回目錄
回首頁