データ構造実験のチェーンテーブル8:Fareyシーケンス

2252 ワード

Problem Description
Fareyシーケンスは、第1段目のシーケンスを(0/1,1/1)と定義し、このシーケンスを第2段目の形成シーケンス(0/1,1/2,1/1)に拡張し、第3極形成シーケンス(0/1,1/3,1/2,2/3,1/1)に拡張し、第4段目に拡張するとシーケンスを形成するシーケンスである(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)が2つのスコアの間に挿入される.与えられたn値について、そのn段目のシーケンスに含まれる各スコアが順次出力される.
Input
整数n(0)を入力
Output
n段目のシーケンスに含まれる各スコアを順次出力し、各行に10個のスコアを出力し、同じ行の2つの隣接スコアが1つのタブの距離を隔てている.
Sample Input
6

Sample 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
#include
#include
#include
using namespace std;

typedef struct Node{
    int top;
    int bottom;
    struct Node *next;
}node;

void create(node * &head){
    node *p,*tail;
    head = new Node;
    head->next = NULL;
    tail = head;
    p = new Node;
    p->bottom = 1;
    p->top = 0;
    tail->next = p;
    tail = p;
    p = new Node;
    p->bottom = 1;
    p->top = 1;
    tail->next = p;
    tail = p;
}

void handle(node * &head,int n){
    node *p,*q,*k;
    int i;
    for(i = 2; i <= n ;i++){
        p = head->next;
        q = p->next;
        while(q){
            if((p->bottom + q->bottom) <= i){
                k = new Node;
                k->top = p->top + q->top;
                k->bottom = p->bottom + q->bottom;
                k->next = NULL;
                k->next = p->next;
                p->next = k;
            }
            p = q;
            q = q->next;
        }
    }
}
void printf(node * &head){
    node *cur;
    cur = head->next;
    int count = 0;
    while(cur){
        count++;
        if(count % 10 == 0){
            printf("%d/%d
",cur->top,cur->bottom); }else{ printf("%d/%d\t",cur->top,cur->bottom); } cur = cur->next; } } int main(){ int n; node *head; scanf("%d",&n); create(head); if(n == 1){ printf(head); }else{ handle(head,n); printf(head); } return 0; }

元々はpeを1発、スペースをtに変更して奏効