📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Taobao : 分鸡蛋问题

🔗
 楼主| wwwyhx 2011-5-12 12:54:02 | 只看该作者
全局:
又写了个程序计算方法的数目,复杂度还是有点大,但至少是多项式了,为了简练几个搜索中的优化没有加:
darksteel 发表于 2011-5-10 13:13



    还没完呢,还没有人能证明这种逻辑不会漏掉组合啊!
    你的逻辑是按篮子装鸡蛋数的升序考虑,比如x1,x2....xm, 第i个篮子前所有的篮子的鸡蛋数目可以组合成小于x1+..+xi的所有数,没错这个充分条件,但没有人证明这个条件的必要性,就是没有人证明这种逻辑不会漏掉组合
回复

使用道具 举报

🔗
darksteel 2011-5-12 13:21:27 | 只看该作者
全局:
回复 11# wwwyhx
应该是不会漏,这个方法会尝试所有可能的情况。对任何一个可能的组合,总有一个升序的排法,那这个搜索的方法就应该能搜出来
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-15 02:47:26 | 只看该作者
全局:
回复  wwwyhx
应该是不会漏,这个方法会尝试所有可能的情况。对任何一个可能的组合,总有一个升序的排法,那这个搜索的方法就应该能搜出来
darksteel 发表于 2011-5-12 13:21


我给一个证明:
反证法:
假设下标为i时,存在第一个漏网之鱼(i之前的篮子都可以组合成 1到sum=a[0]+..a[i-1]的各个数),那么,也就是说在区间[sum+1,sum+a[i]]会漏掉一个,这个数不能由前i个篮子组合得到。

但不会漏掉,因为a[i]一定<=sum,如果漏掉了就和题设矛盾。

而a[i]一定不能大于sum,为什么?? 因为如果a[i]大于sum,那么(sum+1,sum+a[i])之间会漏掉无法弥补的数字, 因为a[i]后面的数只会比a[i]大
回复

使用道具 举报

🔗
darksteel 2011-5-15 06:12:34 | 只看该作者
全局:
回复 13# wwwyhx
嗯,搜索策略保证了不会漏掉
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表