小练习20160201：称量乒乓球

冬雪雪冬

记得有个小游戏，称量乒乓球。有多个乒乓球，除了一个球更重外，其他球重量一样，怎样用天平最少的称量次数找出重球。

这次要求主要功能编写成一个函数，问题的关键是怎样分球去称量。为了让大家春节快快乐乐，这次出题比较简单，只要答对都给予加分奖励。

考虑到大家春节期间事情比较多，结束时间定在 2016-2-17 23:59

具体要求如下：

1. def find(num1, num2, output = False):
   
2.     #将主要功能封装成一个函数。
   
3.     #其中num1为总的乒乓球数，num2为重球在第几个。
   
4.     #output为True时输出称量过程，为False时不显示过程。
   
5.     #过程示例如下：
   
6.    
   
7.     #以27个乒乓球，重球在第25个为例。
   
8.     #1次称量1-9球和10-18球，重量相同。
   
9.     #2次称量19-21和22-24求，重量相同。
   
10.     #3次称量25球和26球，25球重，重球为25球。
    
11.     #共计称量3次。
    
12.     ....
    
13.     ....
    
14.     return times#返回称量次数。
    
15. 
    
16. n = random.randint(1, 100)#重球在1~100之间
    
17. find(100, n, output = True)#调用find函数一次显示称量过程
    
18. #计时开始
    
19. for i in range(100000):#做100000次测试
    
20.     n = random.randint(1, 100)
    
21.     times = find(100, n)#调用find函数不显示称量过程
    
22. #计数结束
    
23. #输出平均几次称出重球
    
24. #输出用时

复制代码

有鱼油问：题目还有点不理解，是知道重球的位置去找出最少次数，还是不知道重球的位置要确定它在哪？解释一下：重球的位置是随机的，需要用最少的称量次数找出来。以3个球为例，将1、2球放在天平的左右两个盘中，如果左重，则重球是1号球，如果右重，则重球是2号球，如果一样重，则重球是3号球。

余欲渔

挖坟挖坟

1. def 称重(数组):
   
2.     数组长度=len(数组)
   
3.     长三分=数组长度//3
   
4.     长余留=数组长度%3
   
5.     数组1=数组[0:长三分]
   
6.     数组2=数组[长三分:长三分*2]
   
7.     数组3=数组[长三分*2:长三分*3]
   
8.     if sum(数组1)>sum(数组2):
   
9.         return 称重(数组1)   
   
10.     elif sum(数组1)<sum(数组2):
    
11.         return 称重(数组2)+长三分
    
12.     elif sum(数组1)<sum(数组3):
    
13.         return 称重(数组3)+长三分*2
    
14.     elif 数组[数组长度-1]<数组[数组长度-2]:
    
15.         return 数组长度-1
    
16.     else:
    
17.         return 数组长度
    
18. 
    
19. def 生成(长度):
    
20.     import random
    
21.     a=[]
    
22.     b=random.randint(0,长度-1)
    
23.     for i in range(长度):
    
24.         a.append(1)
    
25.     a[b]+=1
    
26.     return a
    
27. print(称重(生成(30)))

复制代码

zxc123qwe

学习学习

奈文魔尔

新人留名~ mark

qq81311976

学习，，

夏天的凤

不爱穿内裤 发表于 2016-2-2 10:38
等下做一下。。

加油

worry921

666666666666666666666666666666厉害

东印心迹静

抢占位置

zuobianfy

错过了

zooo

wei_Y 发表于 2016-2-5 13:36
写完才发现二分法是次优解，占坑待编辑。

在函数里生成随机数，赞~
答案很精炼~不愧是版主~

netikid

最近有事情，先拿了鱼币以后再来支持活动吧~

zooo

@DingRan 哦哦~ 受教了，严谨的分析对编程来讲很重要，哈哈~

DingRan

@zooo 谢谢哈哈~后面的最优算法写的仓促了，确实说的不是很清楚诶~地板除比round更优只是一个个例：当T==100时，地板除优于round，当T!=100时就未必啦~比如T==92时，round恰好是最优算法，地板除则不是。总之，地板除或者“屋顶除”或者round本身跟最优算法没什么关系，只是有时候碰巧和最优算法相等。有时候这三个都不是最优算法，比如T==18时，明明可以整除，最优算法却是5或者7。T==100时，27,28,29,31,32,33,35,36,37都是最优。最优算法这东西很诡异呐~

zooo

@DingRan 先赞下，高数666666~，但还没太理解你所说最优算法，数学知识都还给老师了，，而且我试了几次 '平均三分法' 找球的次数在4.27次附近呀
进行100000轮找重球所用的时间为 4.858,平均4.271次可以找出重球
输入一个字符结束
>>> ================================ RESTART ================================
进行100000轮找重球所用的时间为 5.041,平均4.269次可以找出重球
输入一个字符结束
----------------------------------- -----------------------------------------
突然发现是我的计数器少算了一次，尴尬了
刚刚改好了，找球次数是不会低于4.3次
你试试用地板除代替round，这种简单粗暴的方式好像比用round()找球的次数少，我也不知道为什么
triVer = (end-beg)//3
#triVer = round((end - beg)/3)#分片长度
-----------------------------------------------
使用地板除的测试结果
第一次：进行100000轮找重球所用的时间为 4.968,平均4.310次可以找出重球
第二次：进行100000轮找重球所用的时间为 4.883,平均4.311次可以找出重球
使用round()测试结果
第一次：进行100000轮找重球所用的时间为 6.379,平均4.401次可以找出重球
第二次：进行100000轮找重球所用的时间为 6.389,平均4.402次可以找出重球

我是大飞狗

好像之前见过  让我想一想

zuobianfy

恩，先研究研究再说

qq931843108

分奇数偶数，分两堆称，对重的那堆循环操作

worry921

研究研究

Lnan95

@DingRan 的这个思路有点意思啊！值得思考，再占坑。