悬赏500通宝的数学题目 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	重阳


	高阳侯光禄大夫

组别	翰林学士
级别	前将军
好贴	2
功绩	585
帖子	1775
编号	50
注册	2003-8-21

发表于 2004-10-19 13:20 资料主页文集短消息看全部作者

好题。我觉得不是那么简单啊。

尝试一下8选4。
第1次选两个比较排好顺序；
第2、3次把第三个排进去；
第4、5、6次把第四个排进去，按优劣顺序重新定名为一二三四号；
第7次，将第五个与四号比较，若劣于四号则淘汰，优于四号则：
第8次，五号与二号比较，
第9次，若五号优于二号，与一号比较；若五号劣于二号，与三号比较。
经以上三次比较，可把第五个排进去，按优劣顺序重新定名为一二三四号，最劣者淘汰。
第10-12次，把第六个排进去，按优劣顺序重新定名为一二三四号；
第13次，将第七个与四号比较，若劣于四号则淘汰，若优于四号则：
第14次，将第七个与三号比较，若劣于三号，可确定其代替原四号成为新四号，第15次将第八个与此新四号比较即可选出前四。若第七个优于三号，则必定入选，勿需再与前面的比较，第15次将第八个与三号比较即可，若优于三号，则一二七八入选，若劣于三号，则一二三七入选。

因此8选4只需15次，而不是4X（8-4）=16次。

[广告] 《精忠报国岳飞传完整版》火热发布


	重阳


	高阳侯光禄大夫

组别	翰林学士
级别	前将军
好贴	2
功绩	585
帖子	1775
编号	50
注册	2003-8-21

发表于 2004-10-19 22:34 资料主页文集短消息看全部作者

QUOTE:

原帖由周瑜于2004-10-19, 15:31:57发表
第4、5、6次把第四个排进去，按优劣顺序重新定名为一二三四号；
这里只需要比较2次即可。

是，这个地方考虑不周，只想先与三号比较，无论如何也得三次才能保证排进去，其实先与二号比，两次就够了。

这个办法再引申一下，后面的比较也可以用到。比如8选3，在排第四个的时候，也是两次即可，不必[logm]+1=3次。

这么说来p=[log（m-1）]才对，是不是？十来年没玩这些东西了，说说还行，真要列公式脑子就有点乱了。

不对，应该是p=[log（m+1）/2]

[广告] 《精忠报国岳飞传完整版》火热发布