标题: 悬赏500通宝的数学题目 [打印本页]
作者:
青木风亮 时间: 2004-10-18 21:49
小弟喜欢做数学题 今天看到居然有做题的帖子喜出望外 上高中的时候个人有个小发现
这里给出来 看看轩辕网友的水平 纯属娱乐
题目如下：
现有n个苹果 优劣各不相同 只能通过两两比较判断出孰优孰劣（如甲苹果比乙苹果优秀，乙苹果比丙苹果优秀 所以有甲〉乙〉丙） 请给出从这n个苹果中选出m个最优秀的 所需的最小比较次数
如 3 个苹果 选出两个最优秀的 最少需两次
甲〉乙 丙〉乙（或乙〉丙） 因此有甲 丙
各位加油哦
作者:
kesin 时间: 2004-10-18 22:04
只问最少的次数吗？
假设n个苹果正好是按照从优到劣降序排列，则用冒泡排序法，前面m个苹果需比较m-1次（每个苹果都和它前面的苹果比较），后面的n-m个苹果需要比较n-m次（每个苹果和第m个苹果比较），所以共比较n-1次就出来了。
作者:
周瑜 时间: 2004-10-18 23:23
大汗，既然知道是降序排列了还装模做样用冒泡法来比一次做什么啊？
算了一下，应该是m(n-m)次。
作者:
i smile 1111 时间: 2004-10-19 07:50
周瑜说的对
作者:
湘江子龙 时间: 2004-10-19 11:49
青木是没去过我们雅座啊，这种题目也还不少啊！别被妹妹们吓住了，她们不做这个的！
作者:
青木风亮 时间: 2004-10-19 12:08
原帖由周瑜于2004-10-18, 23:23:51发表
大汗，既然知道是降序排列了还装模做样用冒泡法来比一次做什么啊？
算了一下，应该是m(n-m)次。
正解！
小弟破费了 下次来个难点的
作者:
青木风亮 时间: 2004-10-19 12:15
原帖由湘江子龙于2004-10-19, 11:49:39发表
青木是没去过我们雅座啊，这种题目也还不少啊！别被妹妹们吓住了，她们不做这个的！
在哪里啊?
我其实经常去的 但看见的都是对联 这个小弟不太在行 所以一般只是欣赏
作者:
本因坊秀策 时间: 2004-10-19 13:14
这个题是C语言教科书的例题。。。。。。
作者:
重阳 时间: 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次。
作者:
周瑜 时间: 2004-10-19 15:31
根据重阳的二分法，算出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次
原帖由重阳于2004-10-19, 13:20:11发表
第4、5、6次把第四个排进去，按优劣顺序重新定名为一二三四号；
这里只需要比较2次即可。
作者:
kesin 时间: 2004-10-19 15:34
真是搞不懂哎，8选4周瑜的答案是16次，我的答案只要7次，还说我错？
作者:
i smile 1111 时间: 2004-10-19 16:01
kesin在说笑了
作者:
青木风亮 时间: 2004-10-19 19:23
原帖由本因坊秀策于2004-10-19, 13:14:34发表
这个题是C语言教科书的例题。。。。。。
是吗？哈哈 看来我高中可以编教科书了
开玩笑 不要说我臭屁哦
作者:
青木风亮 时间: 2004-10-19 19:28
原帖由周瑜于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次即可。
这个就是算法了 小弟我已经忘了 毕竟两年没摸数学了
不过对于大的数据。。。小弟的初衷不是编程题
周瑜是电子科大的？
作者:
重阳 时间: 2004-10-19 22:34
原帖由周瑜于2004-10-19, 15:31:57发表
第4、5、6次把第四个排进去，按优劣顺序重新定名为一二三四号；
这里只需要比较2次即可。
是，这个地方考虑不周，只想先与三号比较，无论如何也得三次才能保证排进去，其实先与二号比，两次就够了。
这个办法再引申一下，后面的比较也可以用到。比如8选3，在排第四个的时候，也是两次即可，不必[logm]+1=3次。
这么说来p=[log（m-1）]才对，是不是？十来年没玩这些东西了，说说还行，真要列公式脑子就有点乱了。
不对，应该是p=[log（m+1）/2]
作者:
周瑜 时间: 2004-10-19 22:56
看来是我定义向上取整有误，如果此处定义为向下取整，就能直接用
此处q=[logm]........................[]向下取整
或者q=[log((m+1)/2)]............[]向上取整
q代替中间一项中p的位置，前后两项的p不变，仍是向上取整的，q只用于中间一项。
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |