小弟喜欢做数学题 今天看到居然有做题的帖子喜出望外 上高中的时候个人有个小发现
这里给出来 看看轩辕网友的水平 纯属娱乐  

题目如下：
现有n个苹果 优劣各不相同 只能通过两两比较判断出孰优孰劣（如甲苹果比乙苹果优秀，乙苹果比丙苹果优秀 所以有甲〉乙〉丙） 请给出从这n个苹果中选出m个最优秀的 所需的最小比较次数

如 3 个苹果 选出两个最优秀的 最少需两次
甲〉乙 丙〉乙（或乙〉丙） 因此有甲 丙

  各位加油哦

只问最少的次数吗？

假设n个苹果正好是按照从优到劣降序排列，则用冒泡排序法，前面m个苹果需比较m-1次（每个苹果都和它前面的苹果比较），后面的n-m个苹果需要比较n-m次（每个苹果和第m个苹果比较），所以共比较n-1次就出来了。

大汗，既然知道是降序排列了还装模做样用冒泡法来比一次做什么啊？
算了一下，应该是m(n-m)次。

周瑜说的对

青木是没去过我们雅座啊，这种题目也还不少啊！别被妹妹们吓住了，她们不做这个的！

[quote]原帖由[i]周瑜[/i]于2004-10-18, 23:23:51发表
大汗，既然知道是降序排列了还装模做样用冒泡法来比一次做什么啊？
算了一下，应该是m(n-m)次。 [/quote]
正解！
小弟破费了   下次来个难点的

[quote]原帖由[i]湘江子龙[/i]于2004-10-19, 11:49:39发表
  青木是没去过我们雅座啊，这种题目也还不少啊！别被妹妹们吓住了，她们不做这个的！ [/quote]
在哪里啊?
我其实经常去的 但看见的都是对联 这个小弟不太在行 所以一般只是欣赏

这个题是C语言教科书的例题。。。。。。

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

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

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

根据重阳的二分法，算出n里面选出m个共需要比较的次数：
令p=[logm]，log以2为底，[]为向上取整。
若n<2m，则令m=n-m，以保证n>2m
(mp+1-2^p)+(n-2m)(p+1)+(mp+m+1-2^p)
三部分意义分别是
1.二分插入法对m个元素排序
2.将n-2m个元素二分插入序列，并淘汰，剩下m个
3.将剩下m个元素二分插入m序列，同时注意不需与较优的元素进行比较的情况。

由此可知8选4只需要比较14次
[quote]原帖由[i]重阳[/i]于2004-10-19, 13:20:11发表
第4、5、6次把第四个排进去，按优劣顺序重新定名为一二三四号；[/quote]
这里只需要比较2次即可。

真是搞不懂哎，8选4周瑜的答案是16次，我的答案只要7次，还说我错？

kesin在说笑了

[quote]原帖由[i]本因坊秀策[/i]于2004-10-19, 13:14:34发表
这个题是C语言教科书的例题。。。。。。 [/quote]
是吗？哈哈 看来我高中可以编教科书了

开玩笑 不要说我臭屁哦

[quote]原帖由[i]周瑜[/i]于2004-10-19, 15:31:57发表
根据重阳的二分法，算出n里面选出m个共需要比较的次数：
令p=[logm]，log以2为底，[]为向上取整。
若n<2m，则令m=n-m，以保证n>2m
(mp+1-2^p)+(n-2m)(p+1)+(mp+m+1-2^p)
三部分意义分别是
1.二分插入法对m个元素排序
2.将n-2m个元素二分插入序列，并淘汰，剩下m个
3.将剩下m个元素二分插入m序列，同时注意不需与较优的元素进行比较的情况。

由此可知8选4只需要比较14次

这里只需要比较2次即可。 [/quote]
这个就是算法了 小弟我已经忘了  毕竟两年没摸数学了

不过对于大的数据。。。小弟的初衷不是编程题

周瑜是电子科大的？

[quote]原帖由[i]周瑜[/i]于2004-10-19, 15:31:57发表
第4、5、6次把第四个排进去，按优劣顺序重新定名为一二三四号；
这里只需要比较2次即可。 [/quote]
是，这个地方考虑不周，只想先与三号比较，无论如何也得三次才能保证排进去，其实先与二号比，两次就够了。

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

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

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

看来是我定义向上取整有误，如果此处定义为向下取整，就能直接用
此处q=[logm]........................[]向下取整
或者q=[log((m+1)/2)]............[]向上取整
q代替中间一项中p的位置，前后两项的p不变，仍是向上取整的，q只用于中间一项。