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

数据结构实验之链表八：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: AcceptedTake time: 0msTake Memory: 252KBSubmit time: 2017-01-14 18:26:37****************************************************/