20111018

ACM 264 Count on Cantor

找規則
分子                       分母
1             第1行          1
2 1           第2行        1 2
3 2 1         第3行      1 2 3
4 3 2 1       第4行    1 2 3 4
5 4 3 2 1     第5行  1 2 3 4 5

第3(1+2)個term的分子是2
第6(1+2+3)個term的分母是3
第10(1+2+3+4)個term的分子是4
第15(1+2+3+4+5)個term的分母是5
第21(1+2+3+4+5+6)個term的分子是6
第28(1+2+3+4+5+6+7)個term的分母是7

i從2往上累加,超過term為止。
判斷i是奇數還是偶數,
p = term - 累加值。p表示在該行相對於尾端(i)的位置。
每行的分母+分子 = 行數(i)+1。
所以求出其中之一,另一個即為i + 1 - 分母(或分子)。
奇數行: [(i + 1) - (i - p)] / (i - p),
偶數行: (i - p) / [(i + 1) - (i - p)]。
/* ACM 264
 * mythnc
 * 2011/10/18 14:18:56   
 * run time: 0.008
 */
#include <stdio.h>

void findterm(int);

int main(void)
{
    int n;

    while (scanf("%d", &n) != EOF)
        if (n == 1)
            printf("TERM %d IS 1/1\n", n);
        else
            findterm(n);
    return 0;
}

/* findterm: find term and print it */
void findterm(int n)
{
    int sum, i, p;

    for (i = 2, sum = 1; sum < n; i++)
        sum += i;
    p = sum - n;
    if (--i % 2 == 0)   /* judge i is even line or odd line */
        printf("TERM %d IS %d/%d\n", n, i - p, 1 + p);
    else
        printf("TERM %d IS %d/%d\n", n, p + 1, i - p);
}

沒有留言: