#include <stdio.h>

#define PRECISION 12

typedef struct {
   int num;
   int denom;
} rational;

typedef struct _node {
   int data;
   struct _node *next;
} node;

node *cfracApprox ( double x , int k )
{
   node *head, *p;
   int i;
   int a;

   if (x < 0) x = -x;
   i = 0;
   p = head = (node *)malloc(sizeof(node));
   while ((i < k) && (x != 0)) {
      p -> next = (node *)malloc(sizeof(node));
      p = p -> next;
      a = (int)x;
      p -> data = a;
      x -= a;
      x = 1.0/x;
      if (x > 2147483647.) x = 0;
      ++i;
   }
   p -> next = NULL;
   return head;
}

void printCFrac ( node *head )
{
   node *p;

   if ((head == NULL) || (head->next == NULL)) {
      fprintf(stderr, "Cannot print NULL list...\n");
      return;
   }
   p = head -> next;
   printf("Continued fraction expansion is <");
   while (1) {
      printf("%d",p->data);
      p = p->next;
      if (p == NULL) break;
      printf(",");
   }
   printf(">\n");
}

void ratApprox ( node *p , rational R[] , int k , int j )
{
   int i, a, b, c;

   if (j<k) ratApprox((p == NULL) ? NULL : p->next, R, k, j+1);
   R[j-1].num = (p == NULL) ? 1 : p -> data;
   R[j-1].denom = (p == NULL) ? 0 : 1;
   for (i=j; i<k; ++i) if (p != NULL) {
      a = R[i].num;
      b = R[i].denom;
      c = p -> data;
      R[i].num = c*a + b;
      R[i].denom = a;
   }
}

void printApprox ( rational R[] , int k )
{
   int i;

   for (i=0; i<k; ++i)
      printf("Convergent %2d = %9d / %-9d = %20.18lf.\n",
              i+1, R[i].num, R[i].denom,
              (double)R[i].num / (double)R[i].denom);
}

int main ()
{
   double x;
   node *head;
   rational R[PRECISION];
   int i;

   printf("x = "); scanf("%lf",&x);
   head = cfracApprox(x,PRECISION);
   printCFrac(head);
   ratApprox(head->next,R,PRECISION,1);
   printApprox(R,PRECISION);
}