数据结构实验之链表八：Farey序列

TimeLimit: 10MS Memory Limit: 600KB

SubmitStatistic

ProblemDescription

Farey序列是一个这样的序列：其第一级序列定义为（0/1，1/1），这一序列扩展到第二级形成序列（0/1，1/2，1/1），扩展到第三极形成序列（0/1，1/3，1/2，2/3，1/1），扩展到第四级则形成序列（0/1，1/4，1/3，1/2，2/3，3/4，1/1）。以后在每一级n，如果上一级的任何两个相邻分数a/c与b/d满足（c+d）<=n，就将一个新的分数(a+b)/(c+d)插入在两个分数之间。对于给定的n值，依次输出其第n级序列所包含的每一个分数。

Input

输入一个整数n(0<n<=100)

Output

依次输出第n级序列所包含的每一个分数，每行输出10个分数，同一行的两个相邻分数间隔一个制表符的距离。

ExampleInput

6

ExampleOutput

0/1   1/6  1/5   1/4   1/3  2/5   1/2   3/5  2/3   3/4

4/5   5/6  1/1

Hint

 

Author

 

H
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
//#include<dqeue>
using namespace std;

struct node
{

  int data1,data2;
  struct node*next;

};
int main()
{
   struct node*head,*last;
   head = (struct node*)malloc(sizeof(struct node));
   last = (struct node*)malloc(sizeof(struct node));
   head->next =last;
   head->data1 = 0;
   head ->data2 = 1;
   last->data1=1;
   last->data2=1;
   int n;
   cin>>n;
   int i = n;
   struct node*tail = head;
   n--;
   while(n--)
   {

      tail = head;
      while(tail->next)
      {

         if(tail->data2+tail->next->data2<=i)
         {
             struct node*p;
             p = (struct node*)malloc(sizeof(struct node));
             p->data1 = tail->data1+tail->next->data1;
             p->data2 = tail->data2+tail->next->data2;
             p->next = tail->next;
             tail->next = p;
         }
         tail = tail->next;

      }

   }
   tail = head;
   int top = 1;
   int kk= 0;
   while(tail)
   {
     if(kk%10==0&&kk)printf("\n");
     else if(top==1)top = 0;
     else printf("\t");
     printf("%d/%d",tail->data1,tail->data2);
     kk++;

  tail=tail->next;
   }



return 0;


}





/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 0ms
Take Memory: 252KB
Submit time: 2017-01-14 18:26:37
****************************************************/