[PYTHON] Puzzle mathématique pour entraîner le cerveau du programmeur Q04 Découper un bâton

Résumé du problème

Coupez une tige de longueur n par m personnes pour faire des unités de 1 cm. Cependant, une seule personne peut couper à la fois. Combien d'étapes cela prendra-t-il?

Code La version que j'ai essayée sans penser à rien. La politique est "coupée du plus long"

def cutbar(length, member):
    bar = [length]
    step = 0
    while bar != [1]*len(bar): #Fin si toute la longueur est 1
        for i in range(min(member, len(bar))):
            piece = bar.pop(0) #conduire(=Valeur maximum)Sortir
            if piece == 1:
                break
            else:
                cut1 = round(piece/2)
                cut2 = piece - cut1
                bar += [cut1, cut2]
        bar.sort(reverse=True) #Trier par ordre décroissant
        step += 1
    return step

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

Avec un retour

Il est plus intelligent de le faire de manière récursive. La plupart du code ci-dessous est en vente dans le texte, mais ...

#Q04 Découper un bâton
#Utiliser la récurrence

def cutbars(length, member, pieces): #Longueur initiale du bâton, nombre de personnes, nombre actuel de bâtons
    if pieces >= length: #Coupe terminée
        return 0
    elif pieces < member: #Coupez tous les bâtons uniformément
        return 1 + cutbars(length, member, pieces * 2)
    else: #Ne coupez que les bâtons pour les membres
        return 1 + cutbars(length, member, pieces + member)
    
print(cutbars(20, 3 ,1))
print(cutbars(100, 5, 1))