我正在写一个算法对于这个问题,算法很简单,我已经写的代码,但我看不到任何可能的优化:优化的基于时间的算法
我有一个有100个石头和5个使用它来装饰沙堡的小孩。 每个孩子反复拿起一块石头每一定的时间跨度,每个孩子都是独立于他人,更多的孩子可以拿起在同一时间一块石头,有5个孩子合计:
- 埃里克挑一块石头,每5分钟
- 马克拿起石每10分钟
- 拉拉拿起石每7分钟
- 艾玛拿起石每3分钟
- 弗兰克拿起石每3分钟
我们需要多少分钟才能清空存储桶?要更加清楚:10分钟后,埃里克有两块石头(分钟5和分钟10),而艾玛有3块石头(分钟3,6和9)。
所以,10分钟后的儿童有总共2 + 1 + 1 + 3 + 3 = 10结石,有90个结石铲斗
这是我的代码(Python 3中):
children_rate = [3, 3, 5, 7, 10]
bucket = 100
minutes = 0
while True:
minutes += 1
for child in children_rate:
if minutes % child == 0:
bucket -= 1
if bucket == 0:
print('bucket empty in',minutes,'minutes')
exit()
此代码有效,在这种情况下,所需的分钟数是91,但我不能使用此代码处理一百万个石头和500个孩子的桶。
我可以看到的唯一优化是在总和/加操作中转换mod操作,因为分割/乘法更昂贵。我可以使用numpy数组等等,但没有什么能够真正加速这个过程。
我试着将问题适应于我的算法教科书中描述的一些典型的知识问题,但没有运气。
由于问题被标记为“python-3.x”,不应该将floor division设置为“//”吗? –