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

客官°小女子只卖身不卖艺 2022-07-15 10:13 78阅读 0赞

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

Time Limit: 10MS  Memory Limit: 600KB

#### 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个分数，同一行的两个相邻分数间隔一个制表符的距离。

#### Example Input ####

#### Example 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/1

#### Hint ####

#### Author ####

#include<stdio.h>
    #include<stdlib.h>
        struct node
        {
            int data1;
            int data2;
            struct node *next;
        };
        struct node *head,*p,*q,*tail;
        int Chushi()
        {
            p=(struct node *)malloc(sizeof(struct node));
            p->next=NULL;
            p->data1=0;
            p->data2=1;
            tail->next=p;
            tail=p;
            p=(struct node *)malloc(sizeof(struct node));
            p->next=NULL;
            p->data1=1;
            p->data2=1;
            tail->next=p;
            tail=p;
        }
        int Insert(int n)
        {
            p=head->next;
            tail=p->next;
            while(p)
            {
                if(tail==NULL)
                    break;
                if((p->data2+tail->data2)<=n)
                {
                    q=(struct node *)malloc(sizeof(struct node));
                    q->data1=p->data1+tail->data1;
                    q->data2=p->data2+tail->data2;
                    q->next=p->next;
                    p->next=q;
                    tail=q;
                }
                else
                {
                    p=p->next;
                    tail=tail->next;
                }
            }
        }
        int display()
        {
            int kk=1;
            p=head->next;
            int num=0;
            while(p)
            {
                if(kk)
                    kk=0;
                else
                    printf("\t");
                num++;
                printf("%d/%d",p->data1,p->data2);
                p=p->next;
                if(num==10)
                {
                    num=0;
                    printf("\n");
                    kk=1;
                }
            }
            if(num!=10)
                printf("\n");
        }
        int main()
        {
            int n;
            while(scanf("%d",&n)!=EOF)
            {
                head=(struct node *)malloc(sizeof(struct node));
                head->next=NULL;
                tail=head;
                Chushi();
                if(n==1)
                    display();
                else
                {
                    Insert(n);
                    display();
                }
            }
        }