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

编程之美4.3 买票找零解法二

2019年01月04日 ⁄ 综合 ⁄ 共 183字 ⁄ 字号 评论关闭

解法二利用了数学分析的方法得到非法序列和Sigma序列是一一对应的,其中很关键的一步是:

在一个非法序列中,存在某个(些)k,使得序列的前k项中1的个数比0的个数刚好少1个

原因:

1) 若第一位为0,则成立

2) 若第一位为1,又该序列为非法序列,因此必然存在某个(些)k,使得在该位上0的个数超过1的个数,此时1的个数刚好比0的个数少1个

对于后面Sigma序列也是同样的解释

抱歉!评论已关闭.