Cut a bar of length n by m people to make 1 cm units. However, only one person can cut at a time. How many steps will it take?
Code The version I tried without thinking about anything for the time being. The policy is "cut from the longest"
def cutbar(length, member):
bar = [length]
step = 0
while bar != [1]*len(bar): #End if all lengths are 1
for i in range(min(member, len(bar))):
piece = bar.pop(0) #lead(=Maximum value)Take out
if piece == 1:
break
else:
cut1 = round(piece/2)
cut2 = piece - cut1
bar += [cut1, cut2]
bar.sort(reverse=True) #Sort in descending order
step += 1
return step
print(cutbar(20, 3))
print(cutbar(100, 5))
It's smarter to do it recursively. Most of the code below is for sale in the text, but ...
#Q04 Carving a stick
#Using recursion
def cutbars(length, member, pieces): #Initial length of bar, number of people, current number of bar pieces
if pieces >= length: #Finished cutting
return 0
elif pieces < member: #Cut all bar pieces uniformly
return 1 + cutbars(length, member, pieces * 2)
else: #Cut only the sticks for members
return 1 + cutbars(length, member, pieces + member)
print(cutbars(20, 3 ,1))
print(cutbars(100, 5, 1))
Recommended Posts