网站建设需求规格说明书,中山模板建站公司,免费建站系统个人,移动网站二级域名m开头怎么做文章目录固定个数的砝码可称量重量砝码的组合方法40镑砝码的组合问 一个商人有一个40磅的砝码#xff0c;由于跌落在地而碎成4块。后来#xff0c;称得每块碎片的重量都是整磅数#xff0c;而且可以用这4 块来称从1 至40 磅之间的任意整数磅的重物。问这4 块砝码片各重多少由于跌落在地而碎成4块。后来称得每块碎片的重量都是整磅数而且可以用这4 块来称从1 至40 磅之间的任意整数磅的重物。问这4 块砝码片各重多少
这道题看上去其实不太靠谱毕竟要用4个数组合出40种情况看上去还是有些吃力的。因为四个数的组合至多有C41C42C43C4417C_4^1C_4^2C_4^3C_4^417C41C42C43C4417种情况。
考虑到用天平秤东西时砝码可以放在天平两侧这意味着两个砝码有2种称法3个砝码最多有4种称法4个砝码最多有6种称法这样一来总共有46种称法看来是合理的。
接下来考虑将40拆分成4个数共有多少种可能性如果不删除重复那就是40×39×38×3740\times39\times38\times3740×39×38×37。
这样一来这个问题的规模也就出来了大概在40540^5405量级直接暴力搜解就OK。
固定个数的砝码可称量重量
首先创建一个函数输入不同重量的砝码然后得到可以称量的所有重量
from itertools import permutations
# 可以称出的所有重量
def allWeight(lst):ws []N len(lst)//21for L in permutations(lst):for i in range(N):w abs(sum(L[:i])-sum(L[i:]))if w0: continuews.append(w)return set(ws)随便拿几个数组测试一下 allWeight([1,2])
{1, 3}allWeight([1,2,3])
{2, 4, 6}allWeight([1,2,3,4])
{2, 4, 6, 8, 10}以123为例123613-2223-14故可称量2,4,6三种重量。
砝码的组合方法
接下来考虑到可以用[1,2,3,4]中任意组合所能称出的所有重量其方法在allWeight的基础上需要加一个抽选的功能
import numpy as np
def allSubSet(lst):lst np.array(lst)N len(lst)subSet []for i in product(*([[0,1]]*N)):if np.sum(i)0:continuesubSet.append(lst[np.array(i)1])return subSet接下来测试一下 allSubSet([1,2,3])
[array([3]), array([2]), array([2, 3]), array([1]), array([1, 3]), array([1, 2]), array([1, 2, 3])]40镑砝码的组合
题意要求40磅的砝码摔成了整数个这个当然也能用组合来做而且可以非常暴力只需暴力搜索4个小于40个值和为40就可以了。
parts []
L40 list(range(40))
for i in product(*([L40]*4)):if sum(i) 40:parts.append(i)最后得到总共有12337种组合。
最后再对这12337种组合筛选就完事儿了
WS set(range(1,41))
for L in parts:subLs allSubSet(L)ws set()for sub in subLs:ws.update(allWeight(sub))if ws WS:print(sub)最后输出了24个结果无一列外都是[1,3,7,29]这说明这个暴力穷举还是很低效的可以考虑优化一下速度能提高24倍。
