[讨论]给大家出道题提提神
发表于 : 2006-06-16 0:38
拓扑排序
这是我们老师留的题目,我已经做出来了,但算法不很好,题目如下
用C写一个程序,该程序从一个文本文件中读入一组字符,该文件的内容格式如下:
ab
ac
bd
be
cd
ce
df
eg
fh
gi
这种排列方式产生了一个拓扑图形,如下:
b d f h
a
c e g i
a的后面是b, b的后面是d和e, c的后面是d和e................
以此类推。
要求1: 将这个图形重新排列,并按照类似下面的顺序重新输出到屏幕上:
abcdefghi
要求2: 找出所有符合要求1的排列顺序,类似这样的排列acbedgfih也是符合要求的,找出所有的,并输出到屏幕
////////////////////
我的做法是:把每一个字符都给一个等级,a是1级,b,c是2级,d,e是3级,f,g是4级,i,h是5级,然后按级别输出。第二步,把所有的字符所有的排列可能性都找出来,然后再按等级输出,这样就找出所有符合规定的排列。这种算法在寻找所有可能的排列顺序时候很费时间,如果一个图很大的话,时间会很久。
就这个,我题目已经交了,绝对不是为了骗答案,纯粹娱乐,各位朋友各抒己见吧
这是我们老师留的题目,我已经做出来了,但算法不很好,题目如下
用C写一个程序,该程序从一个文本文件中读入一组字符,该文件的内容格式如下:
ab
ac
bd
be
cd
ce
df
eg
fh
gi
这种排列方式产生了一个拓扑图形,如下:
b d f h
a
c e g i
a的后面是b, b的后面是d和e, c的后面是d和e................
以此类推。
要求1: 将这个图形重新排列,并按照类似下面的顺序重新输出到屏幕上:
abcdefghi
要求2: 找出所有符合要求1的排列顺序,类似这样的排列acbedgfih也是符合要求的,找出所有的,并输出到屏幕
////////////////////
我的做法是:把每一个字符都给一个等级,a是1级,b,c是2级,d,e是3级,f,g是4级,i,h是5级,然后按级别输出。第二步,把所有的字符所有的排列可能性都找出来,然后再按等级输出,这样就找出所有符合规定的排列。这种算法在寻找所有可能的排列顺序时候很费时间,如果一个图很大的话,时间会很久。
就这个,我题目已经交了,绝对不是为了骗答案,纯粹娱乐,各位朋友各抒己见吧