第3个回答 推荐于2017-10-04
1．拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为 。
这道题考的是拓扑排序，由题意可知8,9可插入1到7中的任意节点中，那么我们讨论8,9并在一起插入和分开插入两种情况，7个节点有8个个空位，则有C(8,1)+c(8,2)种情况； 根据拓扑排序原理，我们在讨论删除一个节点1后的情况，5节点从2,3,4,6,7中分离开，那么我们将节点5插入2,3,4,6,7中，则有c(6,1)种情况，然后我们再继续删除节点， 由于删除节点3的时候有3,4,6；3,7,6两条路径情况
综上所诉，该排序一共有（c(8,1)+c(8,2)）*c(6,1)*2=432种情况
2．某个国家的钱币面值有1, 7, 72, 73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通 张钱币。
这是一道贪心题，我们先把（10015）10转化为7进制数为（41125）7，因为该国只有7^0,7^1,7^2,7^3四种钱币，我们先用贪心得到得到的钱币数为：(4*7+1)+1+2+5=37 张钱币
又因为有条件‘假设买卖双方各种钱币的数量无限且允许找零’，我们讨论个位数的5元情况我们发现可以多用一张7元钱币再找回两张1元钱币这种情况比原先决策2+1<5更优；
综上所诉，该国这次交易至少需流通(4*7+1)+1+2+（1+2）=35张钱币
ps：我写得好辛苦啊~~麻烦给点分吧..本回答被提问者采纳