UVa264 - Count on Cantor－awesq123的部落格

用了一個很笨的方法，所以參考就好。

把每一term放入array，再將input帶入array的index求出答案。

#include <stdio.h>
#include <stdlib.h>

#define MAX 10000000

typedef struct{
int numerator;
int denominator;
} Node;

Node terms[MAX + 1]; // 0 ~ MAX => MAX + 1 個

int main(){
terms[1].numerator = 1;
terms[1].denominator = 1;

   // 從第二項開始
   int i, numberTermOfARow = 1, k, direction = 0;
   for(i = 2; i <= MAX; i++, direction++){
       // The offset between this term and the term before this term.
       switch(direction % 4){
           case 0: // right move 1/1 -> 1/2
               terms[i] = terms[i - 1]; // 1/1
               terms[i].denominator = terms[i].denominator + 1; // 1/2
               numberTermOfARow++; // Right movement will cause row index++
               break;

           case 1: // lower left move
               // Do (numberTermOfARow - 1) times.
               k = 0;
               for(; i <= MAX && k < (numberTermOfARow - 1); i++, k++){

                   terms[i] = terms[i - 1]; // 1/2
                   terms[i].numerator++; // 2/2
                   terms[i].denominator--; // 2/1
               }
               if(i > MAX){
                   goto out;
               }
               i--; // 統一由大迴圈將i increment
               break;

           case 2: // down move
               terms[i] = terms[i - 1]; // 2/1
               terms[i].numerator++; // 3/1
               numberTermOfARow++; // Down movement will cause row index++
               break;

           case 3: // upper right move
               // Do (numberTermOfARow - 1) times.
               k = 0;
               for(; i <= MAX && k < (numberTermOfARow - 1); i++, k++){
                   terms[i] = terms[i - 1]; // 3/1
                   terms[i].numerator--; // 2/1
                   terms[i].denominator++; // 2/2
               }
               if(i > MAX){
                   goto out;
               }
               i--;
               break;
       }
   }
   out:

   int num;
   while(scanf("%d", &num) == 1){
       printf("TERM %d IS %d/%d\n", num, terms[num].numerator, terms[num].denominator);
   }
return 0;
}