前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最多7次比较解决5个数的排序问题的解法

最多7次比较解决5个数的排序问题的解法

作者头像
窗户
发布2018-02-07 16:12:00
9480
发布2018-02-07 16:12:00
举报
文章被收录于专栏:窗户窗户

  这一篇是上一篇《12(13)个球1个不同重量称3次称出的详细分析》的姊妹篇,分析手段同出一辙,此题源于《算法导论》。

  和上面一样分析,5个数的排列总共有5!=120种,排序的本质是从这120种排列中确定其中的一种;而每次比较会有两种结果,小于、大于等于。7次比较总共有27=128种结果,用最多128种比较结果去分辨120种排列,是有可能的。解答过程中充斥着大量的排列组合计算以计算出各种选择所要分辨的可能性数量,计算起来可能并不轻松。时刻要记住一点,不断用信息论下界来排除可能,但信息论下界只能用于排除,而无法做到肯定。

  用圈和叉代表数,两个数之间如果存在连线,代表线上面的数大于等于线下面的数。

  每一步两个叉代表本步选择来比较的两个数。

  当5个数用一条线串在一起,当然就是排序结束。

  同一行可能有多种情况,我都标了出来。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-10-27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档