noip 2009信息学奥林匹克联赛初赛Pascal语言试题答案解析,只求第三大题解答,说为什么得到答案,

来源：学生作业帮助网编辑：作业帮时间：2024/05/01 00:48:17

noip 2009信息学奥林匹克联赛初赛Pascal语言试题答案解析,只求第三大题解答,说为什么得到答案,
noip 2009信息学奥林匹克联赛初赛Pascal语言试题答案解析,只求第三大题解答,说为什么得到答案,

noip 2009信息学奥林匹克联赛初赛Pascal语言试题答案解析,只求第三大题解答,说为什么得到答案,
1．拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列,使得图中任意一对顶点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