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

Recommended Posts

Puzzle mathématique pour entraîner le cerveau du programmeur Q04 Découper un bâton
Puzzle mathématique pour entraîner le cerveau du programmeur Q01 "Translittération en décimal"
Puzzle mathématique pour entraîner le cerveau du programmeur Q03 Retourner la carte
Puzzle mathématique pour entraîner le cerveau du programmeur Q06 (version modifiée) Prédiction de Koratz
Puzzle mathématique pour entraîner le cerveau du programmeur Q08 Excellent robot de nettoyage
Puzzle mathématique pour former le cerveau du programmeur Q05 Vous payez toujours en espèces?