小练习20160201：称量乒乓球

冬雪雪冬 · 发表于 2016-2-1 22:36:28

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2016-2-19 08:09 编辑

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

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

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

具体要求如下：

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

复制代码

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

lingtingliushen · 发表于 2016-2-2 08:20:13

沙发占鱼币

不爱穿内裤 · 发表于 2016-2-2 10:38:55

等下做一下。。

zooo · 发表于 2016-2-2 11:28:27

本帖最后由 zooo 于 2016-2-10 23:53 编辑

题目还有点不理解，是知道重球的位置去找出最少次数，还是不知道重球的位置要确定它在哪
-----------------------------------------------------------------------------------------------
【2月10日】终于完成了~~花的时间最久的一次编程，最终显示过程还不太理想，等后面看看
鱼油们的程序再完善下吧~

#称重算法：三分法，1代表重球，通过比较str的大小模拟称重
#显示过程：没有很好的实现，原因可能是：
#实际球的个数为100，但为解决第100号球不能被找出的问题，将球的上限+1，因此导致显示效果不好
import random as rand
import time
def find(num1,num2,output = False):
#num1--总数，num2--随机数，output--输出控制
#字符串不方便替换其中的元素，因此先使用列表初始化，再将列表转化为字符串
num1 += 1#上界加一
ball = ['0']*(num1)#index从0开始0-100
ball[num2] = '1'#放置重球位置
ball = ''.join(ball)#将列表转换为字符串
#三分法参数初始化
beg = 0#开始索引标记
end = num1#结束索引标记
account = 0#记录称重次数
bigBall = 103#一旦比出结果则bigBall为0-100中任一值，跳出循环
partLen = 0#重球所在区间的长度
#开始称重（三分法）
while 103 == bigBall:
beg0 = beg#显示从0开始的区间
account += 1
#划分区间
triVer = (end - beg)//3#分片长度
partOneEnd = beg+triVer
partTwoEnd = partOneEnd+triVer
if ball[beg:partOneEnd] == ball[partOneEnd:partTwoEnd]:
beg = partTwoEnd
elif ball[beg:partOneEnd] > ball[partOneEnd:partTwoEnd]:
end = partOneEnd
else:
beg = partOneEnd
end = partTwoEnd
partLen = end - beg
#打印过程
if True == output:
print('第{ccout}次：比较{begDis1}-{endDis1}号球和{begDis2}-{endDis2}号球\
的重量,确定重球在{begDis}-{endDis}中'.format(ccout=account,begDis1=beg0,
endDis1=partOneEnd-1,begDis2=partOneEnd,endDis2=partTwoEnd-1,
begDis=beg,endDis=end-1))
#如果最后还剩两球则还需要再称一次
if 2 == partLen:
if ball[beg] < ball[end-1]:
bigBall = end-1
else:
bigBall = beg
if True == output:
print('第{ccout}次：比较{begDis}号球和{endDis}号球\
的重量,确定重球为{bigBall}'.format(ccout=account+1,begDis=beg,endDis=end-1,bigBall=bigBall))
elif 1 == partLen:
bigBall = beg
#调试代码
#if bigBall != num2:
#print('mistake = -----------------',num2)
if True == output:
print('设置的重球为：%d号，找到的重球为：%d号'%(num2,bigBall))
print('-------------------------------------------------')
return (bigBall,account)#返回元组，第二个参数用于计算平均称重的次数
begTime = time.time()#记录开始游戏的时间点
cycleTimes = 100000#找重球的总轮数
ballScope = 100#球的总个数
weighTimes = 0#每轮平均比较次数
for i in range(1,cycleTimes+1):
bigBall = rand.randint(1,ballScope)
findBall = find(ballScope,bigBall,output=0)
weighTimes += findBall[1]
runTime = float( time.time()-begTime)
print('进行{cycleTimes}轮找重球所用的时间为{run: .3f},平均{weigh:.3f}次可以找出重球'.format(
cycleTimes=cycleTimes,run=runTime,weigh=weighTimes/cycleTimes))#可以用同样的名字

复制代码

Lnan95 · 发表于 2016-2-2 21:42:37

本帖最后由 Lnan95 于 2016-2-3 13:58 编辑

终于弄出来了，【更新：重修修改了一下之前的错误，加了注释】。【加入计时模块】

def find(num1, num2, output = False):
#num1总球数，num2重球为第几个球
int1 = int(num1)
int2 = int(num2)
count = [0,0,0]
#count为称重方法的索引值，为了之后print对应的method_count
method_count = ["将第一第二组拿来秤，第一组重，所以重球在第一组！","将第一第二组拿来称，第二组重，所以重球在第二组！","将第一第二组拿来称，一样重，所以重球在第三组！"]
times = 0
remainder = int1 % 3#【—|—|—-】←分法
division_1 = [1,1/3*(int1-remainder)]
division_2 = [division_1[1]+1,2*division_1[1]]
division_3 = [2*division_1[1]+1,3*division_1[1]+remainder]
if output == True:
print("\n\n首先将小球分为三组：\t【偷偷告诉你，重球是%d号】\n第一组为[%d,%d]\n第二组为[%d,%d]\n第三组为[%d,%d]\n===============================================" % (int2,division_1[0],division_1[1],division_2[0],division_2[1],division_3[0],division_3[1]))
while 1:
times += 1
length = division_1[1]-division_1[0]
if output == True:
print("\t 开始第%d次秤量" % times)
#重球在第一组中
if int2 <= division_1[1]:
count[0] = 1
if length <= 2:
#小于等于3只（length为小组球数-1）需一次即可得到答案。
if output == True:
print("第一组%d号，第二组%d号,这次秤得第一组重，所以重球为%d号。" % (division_1[0],division_2[0],division_1[0]))
print("本次秤了%d次。" % times)
break
else:
if length <= 4:
#重新分组，old_division为了简便运算，是要被覆盖的division_1[1]的暂存，之后为重新分组
old_division = division_1[1]
division_1 = [division_1[0],division_1[0]]
division_2 = [division_1[0]+1,division_1[0]+1]
division_3 = [division_2[0]+1,old_division]
else:
remainder = length % 3
old_division = division_1[1]
division_length = 1/3*(division_1[1]-remainder-division_1[0])
division_1 = [division_1[0],division_1[0]+division_length]
division_2 = [division_1[1]+1,division_1[1]+division_length+1]
division_3 = [division_2[1]+1,old_division]
#重球在第二组中
elif int2 <= division_2[1]:
count[1] = 1
if length <= 2:
if output == True:
print("第一组%d号，第二组%d号，发现第二组重，则重球为%d。" % (division_1[0],division_2[0],division_2[0]),"本次秤了%d次。" % times)
break
else:
if length <= 4:
old_division = division_2[1]
division_1 = [division_2[0],division_2[0]]
division_2 = [division_1[0]+1,division_1[0]+1]
division_3 = [division_2[0]+1,old_division]
else:
remainder = length % 3
old_division = division_2[1]
division_length = 1/3*(length-remainder)
division_1 = [division_2[0],division_2[0]+division_length]
division_2 = [division_1[1]+1,division_1[1]+division_length+1]
division_3 = [division_2[1]+1,old_division]
elif int2 <= division_3[1]:#重球在第三组中
count[2] = 1
if (division_3[1]-division_3[0]) < 1:
if output == True:
print("第一、二组一样重，在第三组为",division_3[0],"号这次便可秤出来。")
print("本次秤了%d次。" % times)
break
else:
if (division_3[1]-division_3[0]) <= 4:
if (division_3[1]-division_3[0]) <= 1:
#第三组的特殊处理→此时重球在第三组剩下的两个中，此时还需要最后一次秤量。
times += 1
if output == True:
print("第一、二组一样重，则重球在第三组。\n第三组剩下2个球，再来一次便可秤出，所以最终需要%d次" % times)
break
else:
old_division = division_3[1]
division_1 = [division_3[0],division_3[0]]
division_2 = [division_1[0]+1,division_1[0]+1]
division_3 = [division_2[0]+1,old_division]
else:
remainder = (division_3[1]-division_3[0]) % 3
old_division = division_3[1]
division_length = 1/3*(division_3[1]-remainder-division_3[0])
division_1 = [division_3[0],division_3[0]+division_length]
division_2 = [division_1[1]+1,division_1[1]+division_length+1]
division_3 = [division_2[1]+1,old_division]
if output == True:
index = count.index(1)
print(method_count[index])
count = [0,0,0]
print("重新分组！将原先的第%d组分为三组，\n新的三个组分别是第一组%d到%d,第二组%d到%d，第三组%d到%d。\n===============================================" % (index+1,division_1[0],division_1[1],division_2[0],division_2[1],division_3[0],division_3[1]))
return times
import time
import random
total_times = 0
start_time = time.clock()
for i in range(100000):
n = random.randint(1, 100)
total_times += find(100, n)
mean_total_times = total_times/100000
end_time = time.clock()
waste_time= end_time - start_time
print("平均需要%g次秤出来重球在哪。\n总用时%g秒" % (mean_total_times,waste_time))

复制代码

落殇飞羽 · 发表于 2016-2-3 00:27:19

忙了好几个小时才把所有要求差不多满足，在打印重球编号结果时，十万次的用时为1340.128179 secs（这真是我等的最长的一次......），在不打印重球编号结果时，十万次运行时间为11.658666 secs,也是够了！！

————————————————————————————
代码如下：

import random as r
import time as t
import datetime as d
def find(num1, num2, times, start, end, output = False):
#num1为乒乓球总数，num2为重球在第几个
#output为True时输出称量过程，为False时不显示过程
if output == False:
upper = start + (num1 * 2 // 3)
lower = upper + 1
list1 = []
list2 = []
for each_1 in range(start+1, lower):
list1.append(each_1)
for each_2 in range(lower, end+1):
list2.append(each_2)
if num2 in list1:
if len(list1) == 1:
print('重球为：%d球'%list1[0])
elif len(list1) == 2:
num1 = len(list1)
start = start
end = lower
times += 1
list3.append(times)
find(num1, num2, times, start, end)
elif len(list1) == 3:
num1 = len(list1)
start = start
end = lower
times += 1
list3.append(times)
find(num1, num2, times, start, end)
else:
num1 = len(list1)
start = start
end = lower
times += 1
list3.append(times)
find(num1, num2, times, start, end)
if num2 in list2:
if len(list2) == 1:
print('重球为：%d球'%list2[0])
elif len(list2) == 2:
num1 = len(list2)
start = upper
end = end
times += 1
list3.append(times)
find(num1, num2, times, start, end)
elif len(list2) == 3:
num1 = len(list2)
start = upper
end = end
times += 1
list3.append(times)
find(num1, num2, times, start, end)
else:
num1 = len(list2)
start = upper
end = end
times += 1
list3.append(times)
find(num1, num2, times, start, end)
if output == True:
upper = start + (num1 * 2 // 3)
lower = upper + 1
list1 = []
list2 = []
for each_1 in range(start+1, lower):
list1.append(each_1)
for each_2 in range(lower, end+1):
list2.append(each_2)
if num2 in list1:
if len(list1) == 1:
print('重球为：%d球'%list1[0])
elif len(list1) == 2:
print('称量[%d]和[%d]'%(list1[0], list1[1]))
num1 = len(list1)
start = start
end = lower
times += 1
list3.append(times)
find(num1, num2, times, start, end, output == True)
elif len(list1) == 3:
print('称量[%d-%d]和[%d]'%(list1[0], list1[1], list1[2]))
num1 = len(list1)
start = start
end = lower
times += 1
list3.append(times)
find(num1, num2, times, start, end, output == True)
else:
print('称量[%d-%d]和[%d—%d]'%(list1[0], (list1[0]+list1[len(list1)-1]) //2,((list1[0]+list1[len(list1)-1]) //2 + 1), list1[len(list1)-1]))
num1 = len(list1)
start = start
end = lower
times += 1
list3.append(times)
find(num1, num2, times, start, end, output == True)
if num2 in list2:
if len(list2) == 1:
print('重球为：%d球'%list2[0])
elif len(list2) == 2:
print('称量[%d]和[%d]'%(list2[0], list2[1]))
num1 = len(list2)
start = upper
end = end
times += 1
list3.append(times)
find(num1, num2, times, start, end, output == True)
elif len(list2) == 3:
print('称量[%d-%d]和[%d]'%(list2[0], list2[1], list2[2]))
num1 = len(list2)
start = upper
end = end
times += 1
list3.append(times)
find(num1, num2, times, start, end, output == True)
else:
print('称量[%d-%d]和[%d—%d]'%(list2[0], (list2[0]+list2[len(list2)-1]) //2,((list2[0]+list2[len(list2)-1]) //2 + 1), list2[len(list2)-1]))
num1 = len(list2)
start = upper
end = end
times += 1
list3.append(times)
find(num1, num2, times, start, end, output == True)
#实验一次
times = 0
start = 0
end = num1 = 100
list3 = []
n = r.randint(1, 100)
print(n)
find(num1, n, times, start, end, output = True)
#实验结束
#计时开始
d_time1 = d.datetime.now()
time1 = t.time()
times = 0
start = 0
end = num1 = 100
list3 = []
count = 100000
for i in range(count):#100000次测试
n = r.randint(1, 100)
#print(n)
find(num1, n, times, start, end, output = False)#调用find函数不显示称量过程
count1 = len(list3)#计算总次数
mean = count1 / count#计算平均数
time2 = t.time()#计时结束
d_time2 = d.datetime.now()
print('平均%.2f次称出重球'%mean)#输出平均几次称出重球
print('运行时间为：%f secs'%(time2 - time1))#输出用时
print(d_time2 - d_time1, 'secs')

复制代码

shuofxz · 发表于 2016-2-3 20:19:30

还是没太明白题的意思
#以27个乒乓球，重球在第25个为例。
#1次称量1-9球和10-18球，重量相同。
#2次称量19-21和22-24求，重量相同。
#3次称量25球和26球，25球重，重球为25球。
#共计称量3次。

这个例子为什么要这么分？
如果是27个球的话
第一次左边放13个，右边放13个
哪边重重球就在哪边，然后继续二分称量，若果一样重那剩余的那个就是重球

这样做不是更快吗？
如果这么分的话，是不是直接用二分法就可以了呢？

zooo · 发表于 2016-2-3 21:37:43

本帖最后由 zooo 于 2016-2-5 00:23 编辑

二分法貌似不是最快的，就算是用二分法实现也和猜数的方式不同，个人感觉比之前那题难一些。
------------------------------------------分割线------------------------------------------------
【2016-2-5】主要功能实现了，100个球，称4-5次可以找出重球，1000个球6-7次可以找出重球，先放上代码，后面再做些优化，各位鱼油加油哦~

import random as rand
import time
def find(num1,num2):
#num1--总数，num2--随机数，output--输出控制
ball = ['0']*(num1+1)#index从0开始0-100
ball[num2] = '1'#放置重球位置
ball = ''.join(ball)
beg = 0#开始索引标记
end = num1#结束索引标记
account = 0#计数
#开始称重（三分法）
while True:
account += 1
#划分区间
triVer = (end - beg)//3#地板除
partOneEnd = beg+triVer
partTwoEnd = partOneEnd+triVer
if ball[beg:partOneEnd] == ball[partOneEnd:partTwoEnd]:
beg = partTwoEnd
elif ball[beg:partOneEnd] > ball[partOneEnd:partTwoEnd]:
end = partOneEnd
else:
beg = partOneEnd
end = partTwoEnd
partLen = end - beg
if 2 == partLen:
if ball[beg] < ball[end]:
return end
else:
return beg
if 1 == partLen:
#print('猜的次数：',account)
return beg
sTime = time.time()#记录开始游戏的时间点
for i in range(5):
n = rand.randint(1,100)
locate = find(100,n)
#print('n = %d locate = %d'%(n,locate))
print('%.6f'%float( time.time()-sTime))

复制代码

z379652501 · 发表于 2016-2-4 20:22:41

水平不够，来学习的

dongzhang0725 · 发表于 2016-2-4 20:24:40

提前预祝春节快乐

DingRan · 发表于 2016-2-4 22:43:49

本帖最后由 DingRan 于 2016-2-14 23:11 编辑

想了半天不知道该怎么写（智商余额不足…我就先占个位吧…

说一下目前的一些理解：

如果乒乓球个数是固定的，如题目给出的100，那么在num1=100的条件下定义一个find函数，使称重的次数最少，这是可以做到的。

但是根据我对题目的理解，要求定义一个函数，其第一个参数num1并非一定是100，这就要求在任意传入一个num1值的情况下find函数都是一个最优的算法，这就有点难了。

因为根据初步分析，我感觉最优的算法对num1的依赖性使非常大的，即对于不同性质的num1（奇数偶数素数平方数n次方数等等）可能会有着不同的最优算法…当然这一点还有待继续考证，但如果真是如此的话，要定义一个对任何num1都适合的最优算法，就很困难了…

以上是一些不成熟的个人看法，希望大家一起研究，一起进步~^O^

【2月10日填坑】
先上代码
这里用的“三均分法”，但后来证明这并不总是最优算法
1.0版

import random
import time
def step(start, total, secret):
'''
单步称量函数：分成三组，前两组数量要相等，剩下是第三组；比较前两组，确定目标所在组，缩小范围。
参数：start是最小编号减一，total是球的数量，两者决定待测范围；secret是重球的编号。
'''
group = round(total/3)#前两组球的个数
ex_start = start#这里copy一个称量之前的start，待用…
if start < secret <= start+group:
total = group
result = '前者重'
elif start+group < secret <= start+2*group:
start = start+group
total = group
result = '后者重'
else:
start = start+2*group
total = total - 2*group
result = '重量相同'
return start, total, secret, ex_start, group, result
#返回缩小范围后的start和total，以及其他有用的值…
def display(i, ex_start, group, result):
'''
输出单步测量结果：
'''
if group != 1:#如果是多个球则显示范围
string = '第 %d 次称量 %d-%d 球和 %d-%d 球，'\
%(i, ex_start+1, ex_start+group, ex_start+group+1, ex_start+2*group)\
+ result + '。'
else:#如果是单个球则显示球号
string = '第 %d 次称量 %d 球和 %d 球，'\
%(i, ex_start+1, ex_start+2)\
+ result + '。'
print(string)
def find(num1, num2, output=False):
'''
主函数
'''
#初始化参数
start = 0
total = num1
secret = num2
para = [start, total, secret]
i = 0
#循环单步称量并输出
while para[1] != 1:
para = step(para[0], para[1], para[2])
i +=1
if output == True:
display(i, para[3], para[4], para[5])
#输出最后结果
if output == True:
print('重球为 %d 球。共计称量 %d 次。'%(para[0]+1,i))
#看看猜对没…
if para[0]+1 != para[2]:
print('猜错了！！！！！！！===========================')
return i
#测试
m = 100#总球数
gameRound = 100000#轮数
#调用find函数一次显示称量过程
n = random.randint(1, m)#随机生成重球
print('====================单次测试====================')
find(m, n, output=True)
#做gameRound=100000次测试
print('====================多次测试====================')
begin = time.clock()#计时开始
times = 0
for j in range(gameRound):
n = random.randint(1, m)
times += find(m, n)#调用find函数不显示称量过程
end = time.clock()#计数结束
print('平均 %.3f 次称出重球。'%(times/gameRound))#输出平均几次称出重球
print('用时 %.3f 秒。'%(end-begin))#输出用时

复制代码

运行结果：

>>>
====================单次测试====================
第 1 次称量 1-33 球和 34-66 球，前者重。
第 2 次称量 1-11 球和 12-22 球，后者重。
第 3 次称量 12-15 球和 16-19 球，重量相同。
第 4 次称量 20 球和 21 球，重量相同。
重球为 22 球。共计称量 4 次。
====================多次测试====================
平均 4.378 次称出重球。
用时 1.640 秒。
>>>

复制代码

然后我来说一下“三均分法”和最优解的一些想法：

0.
【我们先来比较两个概念：“三分法”“三均分法”】

为了说明的方便，我萌做如下定义：

<1>“三分法”是把所有的球任意分成三组，比如10个球分成（1,1,8）或者（2,2,6）等等都是“三分法”

<2>“三均分法”是把球平均分成三组，如果遇到除不尽的情况，则尽量做到均分，比如9个球必然是（3,3,3），7个球除不尽就只能（2,2,3），但（1,1,5）就不行了（它也太不“平均”了。。）

无论“三分法”还是“三均分法”都要有两组是个数相等的，因为我们要称量嘛~

1.
【所有的方法，本质上都是循环使用“三分法”】

所以我萌就可以不用纠结“到底是用二分法呢？还是三分法呢？还是n分法呢？。。。”这样的问题乐！
有童鞋可能不服：这不坑爹么！我有好多方法呢！我明明可以分成3组4组6组10组…你凭啥说所有的方法都是“三分法”？

待我细细道来~
在这个问题中，不论多么复杂的算法，都可以归结为许多个基本操作的重复，这个基本操作就是单次称量。
而单次称量说白了就是：

(1)篮子里有好多球，左手抓起一把球，右手抓起一把球，并且要保证两只手的球数相等，然后放天平上称一称。
(2)如果左（右）边重，重球就在左（右）手抓的那一把里面，如果一样重，重球就在篮子剩下的球里。
(3)接下来，我们把存在犯罪嫌疑球的那一堆球放在一个新篮子里。
(1*)新的轮回~新篮子里有好多球…左手抓起一把球……右手一个慢动作重复。。。

看~我们发现，每一次基本操作，无形中都把球分成了三组（其中至少有两组个数相等），所以基本操作都是“三分法”！
那么，总的算法，都是基本操作的重复，本质上都是在循环使用“三分法”！

所以，不是我们选择了“三分法”，而是这个世界上除了“三分法”再没有其他方法

对于每一次基本操作，我们用（a,a,T-2a）表示，其中T为总数。这样一来模型的建立是不是就简单多了~~

2.
【寻找最优算法，本质上就是给定T，寻找一个最优的a】

怎样的a才是最优的a呢？
每一次基本操作，都会排除一部分良民球，缩小犯罪嫌疑球的范围。所以我一开始的想法（后来证明是不准确的）是：
如果这个a能排除尽可能多的良民球，它就是最优的a，对应的算法就是最优算法。

怎样排除尽可能多的良民球呢？推导如下：

不妨设基本操作为（a,a,T-2a），T为总数已知。
犯罪嫌疑球出现在前两组的概率为2a/T,此时我们能排除的良民球为T-a
犯罪嫌疑球出现在第三组的概率为（T-2a）/T,此时我们能排除的良民球为2a
于是我们能排除的良民球的数学期望E=(T-a)*2a/T + 2a*(T-2a)/T
整理一下，E=(-6a^2+4Ta)/T
求导…求极值…得出：当a=T/3时，E存在最大值

但是问题来了，T/3可能不是整数呀？？！！
这简单~因为数学期望E的表达式是二次函数，左右对称，所以我们取最接近T/3的整数，同样能达到效果：
即a=round(T/3)

也就是说，当我们取a的值为round(T/3)时，可以排除最多的良民球，也就是最优的算法！
所以，我们在“三分法”的基础上选择了“三均分法”~鼓掌~~

【回来填坑 2月14日】

3.
【然而令人失望的是，“三均分法”并不总是最优算法】
口说无凭，先上代码。
2.0版

import random
import time
def step(start, total, secret):
'''
单步称量函数：分成三组，前两组数量要相等，剩下是第三组；比较前两组，确定目标所在组，缩小范围。
参数：start是最小编号减一，total是球的数量，两者决定待测范围；secret是重球的编号。
'''
s0 = {1:0,
2:1,
3:1,
4:1,
5:1,
11:3,
12:4,
33:11,
34:11,
100:33}
group = s0[total]#最优算法
ex_start = start#这里copy一个称量之前的start，待用…
if start < secret <= start+group:
total = group
result = '前者重'
elif start+group < secret <= start+2*group:
start = start+group
total = group
result = '后者重'
else:
start = start+2*group
total = total - 2*group
result = '重量相同'
return start, total, secret, ex_start, group, result
#返回缩小范围后的start和total，以及其他有用的值…
def display(i, ex_start, group, result):
'''
输出单步测量结果：
'''
if group != 1:#如果是多个球则显示范围
string = '第 %d 次称量 %d-%d 球和 %d-%d 球，'\
%(i, ex_start+1, ex_start+group, ex_start+group+1, ex_start+2*group)\
+ result + '。'
else:#如果是单个球则显示球号
string = '第 %d 次称量 %d 球和 %d 球，'\
%(i, ex_start+1, ex_start+2)\
+ result + '。'
print(string)
def find(num1, num2, output=False):
'''
主函数
'''
#初始化参数
start = 0
total = num1
secret = num2
para = [start, total, secret]
i = 0
#循环单步称量并输出
while para[1] != 1:
para = step(para[0], para[1], para[2])
i +=1
if output == True:
display(i, para[3], para[4], para[5])
#输出最后结果
if output == True:
print('重球为 %d 球。共计称量 %d 次。'%(para[0]+1,i))
#看看猜对没…
if para[0]+1 != para[2]:
print('猜错了！！！！！！！===========================')
return i
#测试
m = 100#总球数
gameRound = 100000#轮数
#调用find函数一次显示称量过程
n = random.randint(1, m)#随机生成重球
print('====================单次测试====================')
find(m, n, output=True)
#做gameRound=100000次测试
print('====================多次测试====================')
begin = time.clock()#计时开始
times = 0
for j in range(gameRound):
n = random.randint(1, m)
times += find(m, n)#调用find函数不显示称量过程
end = time.clock()#计数结束
print('平均 %.3f 次称出重球。'%(times/gameRound))#输出平均几次称出重球
print('用时 %.3f 秒。'%(end-begin))#输出用时

复制代码

运行结果

>>>
====================单次测试====================
第 1 次称量 1-33 球和 34-66 球，后者重。
第 2 次称量 34-44 球和 45-55 球，前者重。
第 3 次称量 34-36 球和 37-39 球，重量相同。
第 4 次称量 40 球和 41 球，前者重。
重球为 40 球。共计称量 4 次。
====================多次测试====================
平均 4.299 次称出重球。
用时 1.709 秒。
>>>

复制代码

首先来比较一下两段代码有什么不同：
代码2.0新增了一个字典s0，这个字典用在了哪儿呢？请看第22行，它由1.0版本里的“group = round(total/3)”改为现在的“group = s0[total]”，引用了这个字典。我们说过，“寻找最优算法，本质上就是给定T，寻找一个最优的a”，之前的“三均分法”被我们换成了这个字典，而这个字典的键就是不同的T，对应的值就是针对每个T的最优的a。

下面我来帮大家吐槽。
“坑爹呢吧！原来你的新算法已经事先写好了，做成字典放在那里现用现查啊？？！！”
“你那字典怎么来的啊？？凭啥就说里面的a就是最优的a啊！！？？”
“干嘛要把T和a都列出来啊？？就没个表达式么？？！！”

然后我来解释…
这个字典里面的a值的确都是最优算法，不是我信手写的，而是由另外一段用来“寻找最优算法”的代码生成的，因为图省事我就先把结果手动复制粘贴来了，另外关于“寻找最优算法”之后会详细说…为啥不用表达式？废话！要是能推出表达式的话谁愿意费这劲全都列出来啊T_T

呼…再看看运行结果吧：
嗯，代码2.0的新算法，平均次数在4.30附近
代码1.0的“三均分法”，平均次数在4.38附近
事实上，之后我们可以严格证明：
旧算法“三均分法”称量次数的数学期望为4.38，新算法的为4.3，并且新算法是最优算法。
显然，“三均分法”悲惨地降级为次优算法，它也有马失前蹄的时候诶~

写到这里可能会有童鞋说：诶~~其实“三均分法”与最优算法也没差多少嘛~~就差0.08而已也不用再麻烦啦~~次优算法就次优算法吧！
这样想的童鞋那就可以愉快的return啦~~（说实话我也觉得次优算法足够了…要不是强迫症又犯了才不来填这个坑……
ps：
1).我感觉吧…之后的东西与Python本身不怎么相关了，倒像是在借用强大的Python暴力解决一道数学题的过程…
2).还有啊…因为智商余额不足…虽然得出了最优算法，却没有得到数学意义上的完美论证（说了是暴力解决T_T对，没有表达式…）
所以请童鞋们特别是数学好的同学要多多交流批评指正啊！！！

4.
【更好的评价标准】
又回到最初的起点：给定T，寻找一个最优的a

为什么“三均分法”得到的a不是最优的a呢？这是一个评价标准的问题。
我们之前曾假定：如果某个a所代表的基本操作，干掉的良民球是最多的（或者说剩下的包含犯罪嫌疑球的球堆是最少的），那么这个a就是最优的a。可见那时的评价标准是：剩下的球数最少。
然而我们的最终目的是什么？是称量的次数最少。

所以问题来了，有两个评价标准，“剩下球数最少”和“称量次数最少”，它俩是不是等价的呢？如果是等价的，我们就可以用前者代替后者，如果是等价的，“三均分法”就可以拍着胸脯说自己是最优算法了…（要是那样我也就不会写这一段了是不是~

所以很显然…很遗憾…并不等价T_T

并不等价的意思就是：假设有一堆球，我最少可以用平均1.857次称量找到目标球；而另一堆球，球数要比前面的少，但是无论我怎么做，最少也得用平均2次称量找到目标球。

球少了反而次数多了？！看上去有违常理是不是？但这是个真实的栗子…第一组球数为7，第二组球数为6，大家可以试一下~

如此这般，就必须老老实实地用“称量次数最少”作评价标准去寻找最优的a

5.
【重寻最优算法】
给定T，每取一个a，都会有一个对应的平均次数（即数学期望），用ES(a,T)表示。
对于所有可能取到的a，必有ES(a,T)的一个最小值，用ES0(T)表示。即T个球的最小称量次数为：
ES0(T) = min{ES(a,T)},其中a历遍(0,T/2]的所有整数

下面计算ES(a,T)的表达式：
给定T，不妨设首次基本操作为（a,a,T-2a）
犯罪嫌疑球出现在前两组的概率为2a/T,称量之后我们剩下的球数为a，而a个球所需要的最小称量次数为ES0(a)，所以总的次数为1+ES0(a)；
犯罪嫌疑球出现在第三组的概率为（T-2a）/T,称量之后我们剩下的球数为T-2a，而T-2a个球所需要的最小称量次数为ES0(T-2a)，所以总的次数为1+ES0(T-2a)
于是称量次数的数学期望
ES(a,T) = [1+ES0(a)]*2a/T + [1+ES0(T-2a)]*(T-2a)/T
= ES0(a)*2a/T + ES0(T-2a)*(T-2a)/T + 1
接下来有两条路可走：
1)计算ES0(T)的数学表达式，代入ES(a,T)的表达式，求最小值，得到a的最优解；
2)将所有可能取到的a代入ES(a,T)的表达式，求最小的ES(a,T)所对应的a，就是a的最优解。
方法1)做下去可以给本案例一个完美的数学论证，但是臣妾实在做不到啊，这也就是为什么代码2.0没有表达式的原因…求数学大神指点！！！
方法2)属于暴力求解，而且计算过程中涉及到递归，在大计算量面前，只能让代码做苦力了~

上代码
寻找最优算法的代码：

from fractions import Fraction #浮点数在递归过程中误差会比较大，所以用分数
#这个字典用来储存对于不同的T，最优算法的所有参数
#键就是T，值是一个列表，列表的零号元素是ES0(T)，一号元素是距离t/3最近的那个最优的a，二号元素是所有最优的a组成的列表。
#事先写好的这两个键值对是初始条件
solution = {0:[0,0,[0]],
1:[0,0,[0]]}
#这个函数用来求，在给定T的情况下，最少次数ES0(T)、距离t/3最近的那个最优的a、所有最优的a
#在本函数中，这三个变量分别用esMax,aThird,aBest表示
def es0(t):
if t in solution:
return solution[t]
else:
aMax = t // 2
esMax = float('inf')
for a in range(1,aMax+1):
b = t - 2*a
esTemp = Fraction((2*a*(1+es0(a)[0]) + b*(1+es0(b)[0]))/t)
if esTemp < esMax:
esMax = esTemp
aBest = [a]
elif esTemp == esMax:
aBest.append(a)
cmp = []
for each in aBest:
cmp.append(abs(each-t/3))
aThird = aBest[cmp.index(min(cmp))]
global solution
solution[t] = [esMax,aThird,aBest]
return [esMax,aThird,aBest]
#把之前得到的最优算法的所有参数简化一下，储存在这个字典中
#键是T，值是距离t/3最近的那个最优的a
#只储存总函数里用得着的键值对，而不是全部
s0 = {}
#这个函数用来挑取有用的数据，储存在s0
def disp(t):
if t == 0 or t == 1 or t in s0:
return
a = es0(t)[1]
b = t - 2*a
global s0
s0[t] = a
disp(a)
disp(b)
#测试
M = 100#总球数
disp(M)
print(s0)

复制代码

运行结果

>>>
{33: 11, 34: 11, 3: 1, 100: 33, 5: 1, 4: 1, 11: 3, 12: 4, 2: 1}
>>>

复制代码

看！我们的代码把需要的最优算法都做出来啦~鼓掌~~

6.
【合体！合体！合体！】
最后我们把“寻找最优算法”的代码和“称量乒乓球”的代码连接起来起来，让前者作为一个函数出现在后者中：

import random
import time
from fractions import Fraction
def bestSolution(t):
solution = {0:[0,0,[0]],
1:[0,0,[0]]}
def es0(t):
if t in solution:
return solution[t]
else:
aMax = t // 2
esMax = float('inf')
for a in range(1,aMax+1):
b = t - 2*a
esTemp = Fraction((2*a*(1+es0(a)[0]) + b*(1+es0(b)[0]))/t)
if esTemp < esMax:
esMax = esTemp
aBest = [a]
elif esTemp == esMax:
aBest.append(a)
cmp = []
for each in aBest:
cmp.append(abs(each-t/3))
aThird = aBest[cmp.index(min(cmp))]
nonlocal solution
solution[t] = [esMax,aThird,aBest]
return [esMax,aThird,aBest]
s0 = {}
def disp(t):
if t == 0 or t == 1 or t in s0:
return
a = es0(t)[1]
b = t - 2*a
nonlocal s0
s0[t] = a
disp(a)
disp(b)
disp(t)
return s0
def step(start, total, secret,s0):
'''
单步称量函数：分成三组，前两组数量要相等，剩下是第三组；比较前两组，确定目标所在组，缩小范围。
参数：start是最小编号减一，total是球的数量，两者决定待测范围；secret是重球的编号。
'''
group = s0[total]#前两组球的个数
ex_start = start#这里copy一个称量之前的start，待用…
if start < secret <= start+group:
total = group
result = '前者重'
elif start+group < secret <= start+2*group:
start = start+group
total = group
result = '后者重'
else:
start = start+2*group
total = total - 2*group
result = '重量相同'
return start, total, secret, ex_start, group, result
#返回缩小范围后的start和total，以及其他有用的值…
def display(i, ex_start, group, result):
'''
输出单步测量结果：
'''
if group != 1:#如果是多个球则显示范围
string = '第 %d 次称量 %d-%d 球和 %d-%d 球，'\
%(i, ex_start+1, ex_start+group, ex_start+group+1, ex_start+2*group)\
+ result + '。'
else:#如果是单个球则显示球号
string = '第 %d 次称量 %d 球和 %d 球，'\
%(i, ex_start+1, ex_start+2)\
+ result + '。'
print(string)
def find(num1, num2, output=False):
'''
主函数
'''
#初始化参数
start = 0
total = num1
secret = num2
para = [start, total, secret]
i = 0
#循环单步称量并输出
while para[1] != 1:
para = step(para[0], para[1], para[2],s0)
i +=1
if output == True:
display(i, para[3], para[4], para[5])
#输出最后结果
if output == True:
print('重球为 %d 球。共计称量 %d 次。'%(para[0]+1,i))
#看看猜对没…
if para[0]+1 != para[2]:
print('猜错了！！！！！！！===========================')
return i
#测试
m = 100#总球数
gameRound = 100000#轮数
s0 = bestSolution(m)#先导出最优算法
#调用find函数一次显示称量过程
n = random.randint(1, m)#随机生成重球
print('====================单次测试====================')
find(m, n, output=True)
#做gameRound=100000次测试
print('====================多次测试====================')
begin = time.clock()#计时开始
times = 0
for j in range(gameRound):
n = random.randint(1, m)
times += find(m, n)#调用find函数不显示称量过程
end = time.clock()#计数结束
print('平均 %.3f 次称出重球。'%(times/gameRound))#输出平均几次称出重球
print('用时 %.3f 秒。'%(end-begin))#输出用时

复制代码

运行结果

>>>
====================单次测试====================
第 1 次称量 1-33 球和 34-66 球，重量相同。
第 2 次称量 67-77 球和 78-88 球，重量相同。
第 3 次称量 89-92 球和 93-96 球，前者重。
第 4 次称量 89 球和 90 球，后者重。
重球为 90 球。共计称量 4 次。
====================多次测试====================
平均 4.301 次称出重球。
用时 1.263 秒。
>>>

复制代码

ps:
另外有些注释还写的不好，有空回来修改
其实，对于寻找最优算法我还有一个优化的算法，可以让程序运行更快（当然这得球数达到1000以上才能体现出来），如果有机会（应该概率不大）再来填坑吧。。。

-1.
【至此，对于乒乓球这个案例，终于有了一个不怎么圆满，但总算是完整的解答】
呼……原谅我的啰嗦和强迫症哈哈哈~~~

我是大飞狗 · 发表于 2016-2-4 22:46:47

并不知道啊！！！

wei_Y · 发表于 2016-2-5 13:36:54

import random
def find(num1, num2, output=False):
# 初始化。
all_nums = ['0' for i in range(num1)]
all_nums[num2-1] = '00'
result = []
# 称量。
def calc(all_nums=all_nums, time=0):
# 取标志单双。
length = len(all_nums)
flag = length % 2
if length == 2 or length == 3:
print("{0}次称量得出结果。".format(time+1))
result.append(time+1)
return
# 双数。
if not flag:
half = length / 2
half = int(half)
# 比较大小。
if len(''.join(all_nums[:half])) > len(''.join(all_nums[half:])):
if output:
print('{0}次称量,称量剩余的{1}-{2}球和{3}-{4}球,重量不同，继续称量。 '.format(time+1, 1, half, half+1, length))
calc(all_nums=all_nums[:half], time=time+1)
else:
if output:
print('{0}次称量,称量剩余的{1}-{2}球和{3}-{4}球,重量不同，继续称量。 '.format(time+1, 1, half, half+1, length))
calc(all_nums=all_nums[half:], time=time+1)
# 单数。
else:
half = (length-1) / 2
half = int(half)
# 比较大小。
if len(''.join(all_nums[:half])) > len(''.join(all_nums[half:-1])):
if output:
print('{0}次称量,称量剩余的{1}-{2}球和{3}-{4}球,重量不同，继续称量。 '.format(time+1, 1, half, half+1, length))
calc(all_nums=all_nums[:half], time=time+1)
elif len(''.join(all_nums[:half])) < len(''.join(all_nums[half:-1])):
if output:
print('{0}次称量,称量剩余的{1}-{2}球和{3}-{4}球,重量不同，继续称量。 '.format(time+1, 1, half, half+1, length))
calc(all_nums=all_nums[half:-1], time=time+1)
else:
print('{0}次称量,称量剩余的{1}-{2}球和{3}-{4}球,重量相同 '.format(time+1, half, length, half+1, length))
result.append(time+1)
return
calc()
return result[0]

复制代码

写完才发现二分法是次优解，占坑待编辑。

65230215 · 发表于 2016-2-6 14:33:10

本帖最后由 65230215 于 2016-2-6 16:37 编辑

这道题，提问本身就已经暴露了三分法是最好的解法了~哈哈。先占个，一会儿上代码。
更新~代码如下：

# 2016-2-6 measure the heavy ball
import time
def findheavyball(num1, num2, output=False):
# num1 is total number
# num2 is the heavy one
# output is whether to show the process of measuring
global display
if output=='1':
display=1
list1 = [0] * (num1 - 1)
list1.insert(num2 - 1, 1)
list1 = list(enumerate(list1, start=1)) # 生成一个初始的索引，初始索引为1
# print(list1)
trichotomy(list1,1,num1)
def trichotomy(list,start,end): #按照三分法进行分组，如1-50会被分为 1-17,18-34,35-50三组
num=end-start+1
if num==1:
print('重球是第%s个球'%start)
else:
a = -(-num // 3)
x=start+a-1 #start——x
y=x+a
z=end #y+1——z
# print(x,y,z)
return bijiao(list,start,x,y,z)
#print(trichotomy(2,27))
def mysum(list,st,end): #计算从开始到结束位置的求和
sum=0
for each in list[st-1:end]:
sum+=each[1]
# print(sum)
return sum
def bijiao(list,start,x,y,z): # 比较大小
a=mysum(list,start,x)
b=mysum(list,x+1,y)
if display==1:
print('比较第%s-%s球与第%s-%s球这两组球的重量：'%(start,x,x+1,y))
# print(a,b)
if a > b:
if display==1:
print('前一组球更重,说明在第%s-%s球中有重球'%(start,x))
return trichotomy(list,start,x)
elif a < b:
if display==1:
print('后一组球更重,说明在第%s-%s球中有重球'%(x+1,y))
return trichotomy(list,x+1,y)
else:
if display==1:
print('两组球一样重,说明在第%s-%s球中有重球'%(y+1,z))
return trichotomy(list,y+1,z) #y+1 到 z更重
# print(list)
if __name__ == '__main__':
list1=[]
display=0
num1=int(input('请输入总球数：'))
num2=int(input('请输入重球所在的位置：'))
output=input('请选择是否打开过程显示功能。(打开则输入1，不打开则按任意键回车):')
time1=time.time()
if num2>num1:
print('您输入的重球位置数超过了总球数，请重新输入！')
else:
findheavyball(num1,num2,output)
time2=time.time()
print('用时为%s秒'%(time2-time1),'我是天才~猜对了吧，速度是不是很惊人，哈哈！')

复制代码

zooo · 发表于 2016-2-6 22:42:06

本帖最后由 zooo 于 2016-2-9 00:16 编辑

@65230215 对啊，版主已经提示的很明显了~~我也是用的三分法，但有些数会漏掉，还没找出问题所在。。
【2月9日】可以准确找出重球，输出过程还存在问题

#称重算法
#显示过程
import random as rand
import time
def find(num1,num2,output = False):
#num1--总数，num2--随机数，output--输出控制
num1 += 1#上界加一
ball = ['0']*(num1)#index从0开始0-100
ball[num2] = '1'#放置重球位置
ball = ''.join(ball)
beg = 0#开始索引标记
end = num1#结束索引标记
account = 0#计数
bigBall = 103
partLen = 0
#开始称重（三分法）
while 103 == bigBall:
beg1 = beg#显示过程
account += 1
#划分区间
triVer = (end - beg)//3#地板除
partOneEnd = beg+triVer
partTwoEnd = partOneEnd+triVer
if ball[beg:partOneEnd] == ball[partOneEnd:partTwoEnd]:
beg = partTwoEnd
elif ball[beg:partOneEnd] > ball[partOneEnd:partTwoEnd]:
end = partOneEnd
else:
beg = partOneEnd
end = partTwoEnd
partLen = end - beg
if 2 == partLen:#还需要再称一次
account += 1
if ball[beg] < ball[end-1]:
bigBall = end-1
else:
bigBall = beg
elif 1 == partLen:
finalResult = 1
bigBall = beg
#打印过程
if True == output:
if 1 == partLen:#比较三球
print('第{ccout}次：比较{begDis1}号球和{begDis2}号球\
的重量,找出重球为{ballDis}'.format(ccout=account,begDis1=beg,
begDis2=beg+1,ballDis=bigBall))
elif 2 == partLen:#比较两球
print('第{ccout}次：比较{begDis}号球和{endDis}的重量\
,找出重球为{ballDis}'.format(ccout=account,begDis=beg,endDis=beg+1,ballDis=bigBall))
else:
print('第{ccout}次：比较{begDis1}-{endDis1}号球和{begDis2}-{endDis2}号球\
的重量,确定重球在{begDis}-{endDis}中'.format(ccout=account,begDis1=beg1+1,
endDis1=partOneEnd,begDis2=partOneEnd+1,endDis2=partTwoEnd,
begDis=beg+1,endDis=end,ballDis=bigBall))
if bigBall != num2:
print('mistake = -----------------',num2)
return (bigBall,account)#可以返回元组
begTime = time.time()#记录开始游戏的时间点
cycleTimes = 10
ballScope = 100
weighTimes = 0
for i in range(1,cycleTimes+1):
bigBall = rand.randint(1,ballScope)
findBall = find(ballScope,bigBall,output=False)
weighTimes += findBall[1]
#print('--------------------------------------------')
#print('bigBall = %d locate = %d'%(bigBall,findBall[0]))
runTime = float( time.time()-begTime)
print('进行{cycleTimes}轮找重球所用的时间为{run: .3f},平均{weigh:.3f}次可以找出重球'.format(
cycleTimes=cycleTimes,run=runTime,weigh=weighTimes/cycleTimes))#可以用同样的名字

复制代码

Lnan95 · 发表于 2016-2-11 00:23:11

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

worry921 · 发表于 2016-2-11 12:23:54

研究研究

qq931843108 · 发表于 2016-2-14 19:55:59

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

zuobianfy · 发表于 2016-2-15 07:52:25

恩，先研究研究再说

我是大飞狗 · 发表于 2016-2-15 10:23:25

好像之前见过让我想一想

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习20160201：称量乒乓球

马上注册，结交更多好友，享用更多功能^_^

评分

本帖被以下淘专辑推荐:

回帖奖励 +3 鱼币

回帖奖励 +3 鱼币

回帖奖励 +3 鱼币

评分

回帖奖励 +3 鱼币

评分

回帖奖励 +3 鱼币

评分

回帖奖励 +3 鱼币

回帖奖励 +3 鱼币

回帖奖励 +3 鱼币

回帖奖励 +3 鱼币

评分

回帖奖励 +3 鱼币

回帖奖励 +3 鱼币

评分

回帖奖励 +3 鱼币

评分

回帖奖励 +3 鱼币

回帖奖励 +3 鱼币

回帖奖励 +3 鱼币

浏览过的版块