Time Limit: 10 ms Memory Limit: 600 KiB
Submit Statistic
Problem Description
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个分数，同一行的两个相邻分数间隔一个制表符的距离。
Sample Input
6Sample Output
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/1Hint
Source
本题是链表的进阶版，读完这个题目第一个感觉就是比较绕，看不懂说的什么意思，但是仔细考虑下来的话，我们会明白题目中要求的什么意思，我们在建立链表的时候需要一个结点存放两个数据，所以在建立链表的时候要注意下，在判断题目要求的时候，不是同一个结点的两个数据进行比较，而是比较新结点和上一个结点分别对应的数据是否满足要求。在这里，建立链表的方式也有所不同，这里采用尾插法建立链表比较方便。具体见代码。
AC代码：
#include<stdio.h> #include<stdlib.h> struct node { int data1;//一个链表的结点需要两个空间来储存数据，所以直接建立两个不同的数据存放点 int data2; struct node *next; }; void creat(node *head,int n) { struct node *p,*q,*tail; tail=head->next;//尾插法建立链表 while(tail->next) { p=tail->next; if(tail->data2+p->data2<=n)//if中的判断条件就是题目中要求的所应该满足的条件 { q=(struct node *)malloc(2*sizeof(int));//为新结点开辟内存 q->data1=tail->data1+p->data1;//新结点数据的生成 q->data2=tail->data2+p->data2;//同上 q->next=p;//将新建立的结点存入链表 tail->next=q; } tail=tail->next; } } void printf(node *head) { struct node *p; p=head->next; int i=1; while(p) { if(i!=0) { printf("%d/%d\t",p->data1,p->data2);//间隔一个制表符距离，下面简单解释一下制表符 i++; } else { printf("%d/%d\n",p->data1,p->data2); i++; } p=p->next; } } int main() { int n; int i; struct node *head,*p,*q; scanf("%d",&n); head=(struct node *)malloc(2*sizeof(int)); p=(struct node *)malloc(2*sizeof(int)); p->data1=0; p->data2=1; q=(struct node *)malloc(2*sizeof(int)); q->data1=1; q->data2=1; q->next=NULL; head->next=p; p->next=q; for(i=2;i<=n;i++) { creat(head,i); } printf(head); return 0; }C++制表符 \t 主要用于格式化的输出，和\n换行是一样的， \n相当于按enter键 \t相当于按tab键，一般占8个字符。 例如，你想让输出像表格一样，输出name和age cout<<"name"<<"\tage"<<"\n"; cout<<"name"<<"\tage"<<"\n"; cout<<"name"<<"\tage"<<"\n"; 其输出效果为： name空格空格空格空格age name空格空格空格空格age name空格空格空格空格age
