■

昨日の結城浩さんの既約分数クイズ*1の続きです。

昨日は、配列を用いて、プログラムを作成したが、あまりにもメモリ効率が悪いので、連結リストを用いたものを作成。

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

typedef struct {
  int up;
  int down;
} Fraction;

typedef struct fraction_node {
  Fraction fraction;
  struct fraction_node *next;
} FNode;

FNode *make_node(void);
void print_fnode_link(FNode *);
void farey(FNode *, FNode *, int);
void free_fnode(FNode *, FNode *);

FNode *make_node(void)
{
  FNode *p;
  p = (FNode *)malloc(sizeof(FNode));
  if (p == NULL){
    printf("error: malloc\n");
    exit(1);
  }
  return p;
}

void print_fnode_link(FNode *p)
{
  while(p->next != NULL){
    printf("%d/%d ,", p->fraction.up, p->fraction.down);
    p = p->next;
  } 
  printf("%d/%d\n", p->fraction.up, p->fraction.down);
}

void farey(FNode *left, FNode *right, int limit)
{
  FNode *middle;
  int down;

  down = left->fraction.down + right->fraction.down;
  if (down <= limit){
    middle = make_node();    
    middle->fraction.down = down;
    middle->fraction.up = left->fraction.up + right->fraction.up;
    middle->next = right;
    left->next = middle;
  } else
    return;

  farey(left, middle, limit);
  farey(middle, right, limit);
}

void free_fnode(FNode *head, FNode *tail)
{
  FNode *tmp;

  while (head->next != tail) {
    tmp = head->next;
    head->next = tmp->next;
    free(tmp);
  }
  free(head); free(tail);
}

int main(void)
{
  FNode *head, *tail;
  int n;
  
  printf("Input Number --> "); scanf("%d", &n);

  head = make_node();
  tail = make_node();

  head->fraction.up = 0; head->fraction.down = 1;
  tail->fraction.up = 1; tail->fraction.down = 1;
  
  head->next = tail; tail->next = NULL;
  
  farey(head, tail, n);
  print_fnode_link(head);
  free_fnode(head, tail);  
  return 0;
}

以下は、実行結果です。

[mmasa@localhost c]$ ./link_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

このページは、結城浩さんの日記からリンクされています。光栄なことです(^^)。

*1:http://www.hyuki.com/diary/dia0312.html#i30