Mathematical puzzle to train the programmer's brain Q04 Carving a stick

Problem summary

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))

With a comeback

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

Mathematical puzzle to train the programmer's brain Q04 Carving a stick
Mathematical puzzle to train the programmer's brain Q01 "Palindrome in decimal"
Mathematical puzzle to train the programmer's brain Q03 Turn the card over
Mathematical puzzle to train the programmer's brain Q06 (modified version) Collatz's prediction
Mathematical puzzles that train the programmer's brain Q08 Excellent cleaning robot
Mathematical puzzles that train the programmer's brain Q05 Still paying cash?