データ構造実験のチェーンテーブル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
Sample Output
元々はpeを1発、スペースをtに変更して奏効
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に変更して奏効