【味子圣诞礼物】(3+3+3+4+3=16分)
圣诞节到了,妈妈在味子的圣诞树上挂满了礼物(一共有n个),妈妈挂礼物的方法很独特,那就是每个礼物都是挂在某个礼物的下面(最上面的礼物除外),这样,所有的礼物挂在圣诞树上就形成了一个树型结构(如下图所示)。
味子当然很高兴,可以高兴之余,味子又担心了,因为妈妈告诉她“我给生日礼物都编了号,你要从上往下逐层往下数,最后要告诉妈妈,你按照这个顺序数礼物,得到的礼物的编号序列是什么。如果你答对了,今年春节我会在圣诞树上给你挂更多的礼物,否则,春节的礼物就会比圣诞节礼物要少。”
可是味子很聪明,她略加思索就说出了所有礼物从上下排序的顺序是如下序列:
1 2 3 4 5 9 11 12 6 7 8 10 13
但味子不满足于现在的成绩,她想到了用程序来解决这个问题的所有情况。就是告诉程序一共有多少礼物,以及礼物挂在圣诞树上的顺序,程序应能输出从上往下逐层(每层中的礼物从左到右排列)排列的结果。
味子的程序首先能读入一个整数n,表示所有圣诞礼物的总数,然后能读入n行(该n行数据表示礼物挂在圣诞树上的位置顺序),每行的第一个编号表示某个礼物的本身编号i,该行后面的编号依次表示挂在礼物i下面的其他礼物,(按从左到右的顺序给出)。比如,输入样例第二行中的“1 2 3 4 5 0 ”,2、3、4、5分别表示挂在礼物1下面的其他礼物编号分别是2、3、4、5,最后的表示挂在礼物1下面没有其他礼物了。
味子编写了以下程序来达到上面的目的,该程序运行后能用一行输出数据来表示礼物从上入下逐层排列的顺序序列,每个编号之间用一个空格分隔,请帮助味子完成程序。
输入样例:
13
1 2 3 4 5 0
2 9 0
3 11 12 0
4 0
5 6 7 8 0
6 0
7 0
8 0
9 10 0
10 0
11 0
12 13 0
13 0
输出样例:1 2 3 4 5 9 11 12 6 7 8 10 13
program test6;
var first,tail,i,j,n:interer;
a:array[1..20,1..20] of integer;
list:array[1..1000]of integer;
begin
for i:=1 to 20 do
for j:=1 to 20 do a[i,j]:=0;
reaaln( n );
for i:=1 to n do
begin
j:=1;
read(a[i,j]);
while a[i,j]<>0 do
begin inc(j) ;readln(a[i,j]);end;
readln;
end;
first:=1;tail:=1; list[1]:=a[1,1];
while first<=tail do
begin
j:= list[tail] ;i:=list[first];
while a[i,j]<>0 do
begin
inc(tail) ;list[tail];=a[i,j];j:=j+1;
end;
first:=first+1;
end;
for i:=1 to n do write( list[i] ,’ ‘);
end.