[PYTHON] Mathe-Puzzle zum Trainieren des Gehirns des Programmierers Q04 Schnitzen eines Stocks

Problemzusammenfassung

Schneiden Sie einen Stab mit einer Länge von n mal m Personen zu Einheiten von 1 cm. Es kann jedoch immer nur eine Person gleichzeitig schneiden. Wie viele Schritte wird es dauern?

Code Die Version, die ich ausprobiert habe, ohne an irgendetwas zu denken. Die Politik ist "vom längsten abgeschnitten"

def cutbar(length, member):
    bar = [length]
    step = 0
    while bar != [1]*len(bar): #Beenden Sie, wenn alle Länge 1 ist
        for i in range(min(member, len(bar))):
            piece = bar.pop(0) #führen(=Maximalwert)Mitnahme
            if piece == 1:
                break
            else:
                cut1 = round(piece/2)
                cut2 = piece - cut1
                bar += [cut1, cut2]
        bar.sort(reverse=True) #In absteigender Reihenfolge sortieren
        step += 1
    return step

print(cutbar(20, 3))
print(cutbar(100, 5))

Mit einem Comeback

Es ist klüger, es rekursiv zu machen. Der größte Teil des folgenden Codes steht im Text zum Verkauf, aber ...

#Q04 Schnitzen eines Stocks
#Wiederholung verwenden

def cutbars(length, member, pieces): #Anfangslänge des Stocks, Anzahl der Personen, aktuelle Anzahl der Stöcke
    if pieces >= length: #Fertiges Schneiden
        return 0
    elif pieces < member: #Schneiden Sie alle Sticks gleichmäßig ab
        return 1 + cutbars(length, member, pieces * 2)
    else: #Schneiden Sie nur die Stöcke für Mitglieder
        return 1 + cutbars(length, member, pieces + member)
    
print(cutbars(20, 3 ,1))
print(cutbars(100, 5, 1))