现在的位置: 首页 > 综合 > 正文

关于《编程之美》的4.3 买票找零问题

2013年10月03日 ⁄ 综合 ⁄ 共 275字 ⁄ 字号 评论关闭

书中给出了两种很优雅的解法,尤其是第二种(构造sigma序列的方法),但由于太过精妙,我等凡人在没看过的情况下实在是很难想到。看完后想到种比较俗的做法,比较容易想得到,而且也比较好记。

 

1.证明每个合法序列可以构造出n个非法序列

    依次将前k(k = 1...n)组配对的()翻转(即()变成)()即可构造出n个非法序列。

2.证明每个非法序列唯一由一个合法序列构造

    反证法可证。

则在所有的可能序列中合法和非法序列比例为1:n,则合法占所有可能序列的1/(n+1),所有可能序列为组合数P(2n, n),则合法序列个数为1/(n + 1) * P(2n, n)。

抱歉!评论已关闭.