結城浩さんの日記を拝見すると、既約分数クイズのJavaとPerlの解答例*2が載っていました。Javaなら自分でも分かるはずと、じ〜とプログラムを目で追ってみました。しばらくすると、結城さんがどうやって解答を得ようとしているかが分かりました!
では、C言語で作ってみようと思い作ってみました。最初は、連結リストなどを使って作ったほうがいいと思ったのですが、予定変更。ちょっと効率が悪いですが、大きい配列を用意して、その配列に対して解を格納していくことにしました。連結リストを用いる方法よりも簡単に実装できると思ったからです。
やっていることは、配列の一番左側(indexが0番目)に0/1を、配列の一番右側(indexがSIZE-1番目)に1/1を登録し、以下、再帰的に部分配列の中央に、両端の各分子、各分母の和を格納していきます。
- 作った後の感想
#include#define SIZE 1024 typedef struct { int up; int down; } Fraction; void farey(Fraction *,int ,int ,int); main() { int i,n; Fraction fraction_array[SIZE]; printf("Input Number --> "); scanf("%d",&n); for(i = 0 ; i < SIZE ; i++) fraction_array[i].up = -1; fraction_array[0].up = 0; fraction_array[0].down = 1; fraction_array[SIZE - 1].up = 1; fraction_array[SIZE - 1].down = 1; farey(fraction_array,0,SIZE - 1,n); for(i = 0 ; i < SIZE ; i++) if (fraction_array[i].up != -1) printf("%d/%d, ",fraction_array[i].up,fraction_array[i].down); printf("\n"); } void farey(Fraction *fraction,int left,int right,int limit) { int middle; int down; middle = (left + right) / 2; down = fraction[left].down + fraction[right].down; if (fraction[middle].up == -1){ if (down <= limit){ fraction[middle].down = down; fraction[middle].up = fraction[left].up + fraction[right].up; } else return; } else { printf("array is full!\n"); exit(1); } farey(fraction,left,middle,limit); farey(fraction,middle,right,limit); }
実行例は以下です。
[mmasa@localhost c]$ ./farey Input Number --> 9 0/1, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1/1,
