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


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#1

发表于 2004-10-18 21:49 资料主页文集短消息只看该作者

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

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

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

各位加油哦

[广告] 真诚支持说岳，携手共创辉煌


	kesin


	南郡公枢密直学士

组别	翰林学士
级别	镇东将军
好贴	5
功绩	1036
帖子	4004
编号	2725
注册	2003-11-30

#2

发表于 2004-10-18 22:04 资料文集短消息只看该作者

只问最少的次数吗？

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

[广告] 真诚支持说岳，携手共创辉煌


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#3

发表于 2004-10-18 23:23 资料主页文集短消息只看该作者

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

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


	i smile 1111

组别	羽林都尉
级别	安西将军
功绩	86
帖子	3114
编号	7711
注册	2004-5-18

#4

发表于 2004-10-19 07:50 资料主页文集短消息只看该作者

周瑜说的对

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	湘江子龙


	赵王枢密使

组别	诸侯
级别	骠骑将军
好贴	9
功绩	630
帖子	8100
编号	8098
注册	2004-6-4

#5

发表于 2004-10-19 11:49 资料主页个人空间短消息只看该作者

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

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#6

发表于 2004-10-19 12:08 资料主页文集短消息只看该作者

QUOTE:

原帖由周瑜于2004-10-18, 23:23:51发表
大汗，既然知道是降序排列了还装模做样用冒泡法来比一次做什么啊？
算了一下，应该是m(n-m)次。

正解！
小弟破费了下次来个难点的

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#7

发表于 2004-10-19 12:15 资料主页文集短消息只看该作者

QUOTE:

原帖由湘江子龙于2004-10-19, 11:49:39发表
青木是没去过我们雅座啊，这种题目也还不少啊！别被妹妹们吓住了，她们不做这个的！

在哪里啊?
我其实经常去的但看见的都是对联这个小弟不太在行所以一般只是欣赏

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


	本因坊秀策 (★御姐★)


	泉国公枢密直学士河东节度使 ★★★★★

组别	节度使
级别	大将军
好贴	5
功绩	2107
帖子	19336
编号	150
注册	2003-9-28
来自	六朝古都
家族	现视研

#8

发表于 2004-10-19 13:14 资料主页个人空间短消息只看该作者

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

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	重阳


	高阳侯光禄大夫

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

#9

发表于 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次。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#10

发表于 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次

QUOTE:

原帖由重阳于2004-10-19, 13:20:11发表
第4、5、6次把第四个排进去，按优劣顺序重新定名为一二三四号；

这里只需要比较2次即可。

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


	kesin


	南郡公枢密直学士

组别	翰林学士
级别	镇东将军
好贴	5
功绩	1036
帖子	4004
编号	2725
注册	2003-11-30

#11

发表于 2004-10-19 15:34 资料文集短消息只看该作者

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

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	i smile 1111

组别	羽林都尉
级别	安西将军
功绩	86
帖子	3114
编号	7711
注册	2004-5-18

#12

发表于 2004-10-19 16:01 资料主页文集短消息只看该作者

kesin在说笑了

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


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#13

发表于 2004-10-19 19:23 资料主页文集短消息只看该作者

QUOTE:

原帖由本因坊秀策于2004-10-19, 13:14:34发表
这个题是C语言教科书的例题。。。。。。

是吗？哈哈看来我高中可以编教科书了

开玩笑不要说我臭屁哦

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#14

发表于 2004-10-19 19:28 资料主页文集短消息只看该作者

QUOTE:

原帖由周瑜于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次即可。

这个就是算法了小弟我已经忘了毕竟两年没摸数学了

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

周瑜是电子科大的？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	重阳


	高阳侯光禄大夫

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

#15

发表于 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]

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


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#16

发表于 2004-10-19 22:56 资料主页文集短消息只看该作者

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

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！