Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

昨日の既約分数クイズ*1の続きです。

結城浩さんの日記を拝見すると、既約分数クイズのJavaPerlの解答例*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,