Énigmes de gebrane et Namiswan

Rescassol · June 2020

Bonsoir,

> les fichiers pyhon ne sont pas supportés, je vais donc polluer le fil ...

Un fichier Python étant un fichier texte, tu n'as qu'à le renommer en .txt et nous dire de renommer en .py ensuite.

Cordialement,

Rescassol

Cere · June 2020

Merci de ta réponse Rescassol,
Je n'ai pas vu que les fichiers txt étaient supportés, je me trompe peut-être. J'avais choisi de renommer en png du coup, mais de jouer la sécurité et de mettre la version du code sans affichage des étapes, en message sur le forum.

gebrane · June 2020

Merci infiniment Cere pour ce travail. Je vais le regarder avec une amie qui comprend en programation.
Merci encore

Cere · June 2020

@Gebrane
Je t'en prie,j'ai fait ce que j'ai pu, si il y'a une question sur mon code n'hésite pas à relancer ce fil ou bien m'envoyer un message privé je serais ravi d'essayer d'aider.

J'ai modifié les ficher en .pdf pour éviter le message d'erreur d'affichage d'image et j'ai vérifier par la même occasion que le .txt n'est pas accepté.

Rescassol · June 2020

Bonsoir,

Oui, je voulais dire, le renommer en .tex qui est supporté.

Cordialement,

Rescassol

Namiswan · June 2020

Cere: Je n'ai pas de problème avec ton N=73 pour ce que tu m'as montré. A cette étape 17, (66,76,77) est comme on le désire raisonnablement proche de l'équilibre (73,73,73).

Ensuite, A étant en manque, on fait AB, BC, CA
20: (68,75,76)
De nouveau
23:(70,74,75)
Encore une petite fois
26:(73,74,72)
On arrive au but, plus qu'à équilibrer en faisant CB, BC
28:(73,73,73)
On peut passer à l'étape 3 (avec un nombre d'étapes restantes 73-28=45= 1 mod 4)

Bonne chance pour régler tes problèmes personnels

bisam · June 2020

Voici une autre version de l'algorithme de Namiswan :

# -*- coding: utf-8 -*-

"""D'après une énigme tirée de :
http://www.les-mathematiques.net/phorum/read.php?4,2006748
"""

import math

def deplacement(nb, park1, park2, parkings, verbose):
    """Modifie les parkings en enlevant nb voitures au park1 pour les mettre dans le park2.
    Renvoie le numéro du déplacement suivant"""

    assert parkings[park1] >= nb, "Pas assez de voitures dans le parking {} à l'étape {}".format(park1, nb)

    parkings[park1] -= nb
    parkings[park2] += nb
    if verbose:
        print(nb, parkings)

    return nb+1


def parking(N, verbose=True):
    """Affiche la liste des occupations des parkings.
    Si verbose est égal à False, n'affiche que la fin de chaque étape."""
    #Algorithme de Namiswan

    parkings = [3*N, 0, 0]

    K = math.floor(2*math.sqrt(N))
    print(0, parkings,"--> K =", K)
    nb = 1

    print(" --- Étape I --- on répartit grossièrement")
    if K%2: #si K est impair
        nb = deplacement(nb, 0, 1, parkings, verbose)
    while nb <= K:
        nb = deplacement(nb, 0, 1, parkings, verbose)
        nb = deplacement(nb, 0, 2, parkings, verbose)
        if nb <= K:
            nb = deplacement(nb, 0, 2, parkings, verbose)
            nb = deplacement(nb, 0, 1, parkings, verbose)
    if not verbose:
        print("[...]")
        print(nb-1, parkings)

    print(" --- Étape II --- on affine")
    while parkings[0] < N-1:
        nb = deplacement(nb, 0, 1, parkings, verbose)
        nb = deplacement(nb, 1, 2, parkings, verbose)
        nb = deplacement(nb, 2, 0, parkings, verbose)
    while parkings[0] > N+1:
        nb = deplacement(nb, 2, 0, parkings, verbose)
        nb = deplacement(nb, 1, 2, parkings, verbose)
        nb = deplacement(nb, 0, 1, parkings, verbose)
    imax = imin = 0
    for j in (1, 2):
        park = parkings[j]
        if park > parkings[imax]:
            imax = j
        if park < parkings[imin]:
            imin = j
    if imax != imin:
        nb = deplacement(nb, imin, imax, parkings, verbose)
        nb = deplacement(nb, imax, imin, parkings, verbose)
    if not verbose:
        print("[...]")
        print(nb-1, parkings)

    print(" --- Étape III --- on tourne en rond")
    reste = (N-nb+1)%4
    temporaires = [[],
                   [(0, 1), (1, 2), (2, 0), (1, 0), (0, 1), (1, 0), (0, 1), (2, 1), (1, 2)],
                   [(0, 1), (1, 2), (2, 0), (2, 0), (1, 2), (0, 1)],
                   [(0, 1), (1, 2), (2, 0), (1, 0), (0, 1), (2, 0), (0, 2)]]
    for park1, park2 in temporaires[reste]:
        nb = deplacement(nb, park1, park2, parkings, verbose)
    while nb < N:
        nb = deplacement(nb, 0, 1, parkings, verbose)
        nb = deplacement(nb, 1, 0, parkings, verbose)
        nb = deplacement(nb, 1, 0, parkings, verbose)
        nb = deplacement(nb, 0, 1, parkings, verbose)
    if not verbose:
        print("[...]")
        print(nb-1, parkings)
    print(" --- C'est fini !! ---")

Pour l'utiliser, il suffit de taper "parking(N)" où N est la valeur voulue.
L'affichage des différentes étapes prend beaucoup de temps lorsque N devient grand, donc j'ai rajouté un paramètre "verbose" valant True ou False suivant que l'on veut l'affichage complet ou seulement les étapes principales.
J'ai également fait un petit calcul pour montrer que dans tous les cas l'entier $K$ vaut en fait la partie entière de $2\sqrt{N}$, ce qui simplifie pas mal.
Le code semble fonctionner pour tout entier $N>16$.
Il faudrait ensuite faire des cas particuliers pour chacun des cas de $N=5$ à $N=16$.

gebrane · June 2020

Merci Bisam

gebrane · June 2020

Pour ceux qui sont nuls en informatique et qui aimerait tester le programme de bissam
aller dans cette page https://repl.it/repls/RichFuzzyLicensing
copier coller le code de bissam fenêtre gauche
taper parking(30) fenêtre à droite
Amusez vous bien pour d'autres valeurs de N 103612

Cere · June 2020

Je ne sais pas sous quelles médocs j'étais pour avoir perdu du temps à faire tout les cas de fonctions de déplacements au lieu d'avoir fait comme toi (Ah bin si en fait) (:P) !

J'ai rajouté les cas N= 1 à 16 (avec une petite touche d'humour), pour les cas faisables, j'ai réutilisé mon algo stochastique, les algos stochastiques c'est très plouc mais bon c'est toujours mieux que d'écrire les cas à la main.
J'ai aussi vérifié qu'il donne bien le bon résultat pour ces valeurs.

@Bisam. J'avais commencé à vouloir me coller à ta rédaction mais après deux trois contraintes, j'ai préféré juste caser mon algo quasi non modifié, en espérant que cela ne te dérange pas trop, l'essentiel est que cela marche !
J'ai juste modifié ta partie du code pour qu'il donne l'étape à chaque fois et non le tableau changé (affaire de goût).
On a donc sûrement fini là B-) !

import math
import random

def deplacement(nb, park1, park2, parkings, verbose):
    """Modifie les parkings en enlevant nb voitures au park1 pour les mettre dans le park2.
    Renvoie le numéro du déplacement suivant"""
    assert parkings[park1] >= nb, "Pas assez de voitures dans le parking {} à l'étape {}".format(park1, nb)

    parkings[park1] -= nb
    parkings[park2] += nb
    if verbose:
        print("Etape ",nb, " : déplacer ",nb," voitures de", str(park1), "vers ", park2)

    return nb+1


def parking(N, verbose=True):
    """Affiche la liste des occupations des parkings.
    Si verbose est égal à False, n'affiche que la fin de chaque étape."""
    #Algorithme de Namiswan
    parkings = [3*N, 0, 0]
    if (N <3 or N==4):
        print("Le problème n'a pas de solution, hormis peut-être sur Shtam")
    elif N<17: ### Pour ces cas, l'algorithme test ls chemins possibles jusqu'à avoir trouvé le bon
        test = False
        while test == False:
            log = 'Etape 1 : 1 voiture de 0 vers 1 \n'
            parkings = [3*N-1,1,0]
            for i in range(2,N+1):
                log += 'Etape '+str(i)+ ' : '
                if(parkings[0] <i and parkings[1]<i and parkings[2]<i):
                    continue
                else:
                    chosen= -1
                    while chosen == -1:
                        source = random.randint(0,2)
                        if parkings[source]>=i:
                            chosen = 0
                    vers = source
                    while vers == source:
                        vers= random.randint(0,2)
                    parkings[source] -= i
                    parkings[vers] += i
                    log+= "déplacer "+ str(i) +' voitures de '+str(source)+' vers ' + str(vers) + '\n'
                test= (parkings[0]==N and parkings[1]==N and parkings[2] == N)
        print(log)
        print(" --- C'est fini !! ---")

    else:
        K = math.floor(2*math.sqrt(N))
        print(0, parkings,"--> K =", K)
        nb = 1
    
        print(" --- Étape I --- on répartit grossièrement")
        if K%2: #si K est impair
            nb = deplacement(nb, 0, 1, parkings, verbose)
        while nb <= K:
            nb = deplacement(nb, 0, 1, parkings, verbose)
            nb = deplacement(nb, 0, 2, parkings, verbose)
            if nb <= K:
                nb = deplacement(nb, 0, 2, parkings, verbose)
                nb = deplacement(nb, 0, 1, parkings, verbose)
        if not verbose:
            print("[...]")
            print(nb-1, parkings)
    
        print(" --- Étape II --- on affine")
        while parkings[0] < N-1:
            nb = deplacement(nb, 0, 1, parkings, verbose)
            nb = deplacement(nb, 1, 2, parkings, verbose)
            nb = deplacement(nb, 2, 0, parkings, verbose)
        while parkings[0] > N+1:
            nb = deplacement(nb, 2, 0, parkings, verbose)
            nb = deplacement(nb, 1, 2, parkings, verbose)
            nb = deplacement(nb, 0, 1, parkings, verbose)
        imax = imin = 0
        for j in (1, 2):
            park = parkings[j]
            if park > parkings[imax]:
                imax = j
            if park < parkings[imin]:
                imin = j
        if imax != imin:
            nb = deplacement(nb, imin, imax, parkings, verbose)
            nb = deplacement(nb, imax, imin, parkings, verbose)
        if not verbose:
            print("[...]")
            print(nb-1, parkings)
    
        print(" --- Étape III --- on tourne en rond")
        reste = (N-nb+1)%4
        temporaires = [[],
                       [(0, 1), (1, 2), (2, 0), (1, 0), (0, 1), (1, 0), (0, 1), (2, 1), (1, 2)],
                       [(0, 1), (1, 2), (2, 0), (2, 0), (1, 2), (0, 1)],
                       [(0, 1), (1, 2), (2, 0), (1, 0), (0, 1), (2, 0), (0, 2)]]
        for park1, park2 in temporaires[reste]:
            nb = deplacement(nb, park1, park2, parkings, verbose)
        while nb < N:
            nb = deplacement(nb, 0, 1, parkings, verbose)
            nb = deplacement(nb, 1, 0, parkings, verbose)
            nb = deplacement(nb, 1, 0, parkings, verbose)
            nb = deplacement(nb, 0, 1, parkings, verbose)
        if not verbose:
            print("[...]")
            print(nb-1, parkings)
        print(" --- C'est fini !! ---")

gebrane · June 2020

Cere ton code ne marche pas en tapant par exemple
parking(30)
peux-tu dire ce qu'il faut taper exactement

Cere · June 2020

@Gebrane
Je crois que c'est le message qui n'allait pas, si tu as copié le code jusqu'en bas, il y avait un reste de la balise html "/code]"
J'ai édité le poste, normalement cela doit marcher.

Je ne serais pas fidèle à moi même si je ne faisais pas une étourderie par poste ! :-D 103620

Cere · June 2020

J'ai vérifié au cas où, avec le lien que tu as mit. Il faut bien juste enlever le "/code]" à la fin (ce que j'ai édité dans mon post. 103622

gebrane · June 2020

Ça marche
A ceux qui s'interesse essayer le sur le site https://repl.it/repls/RichFuzzyLicensing#main.py
et l'affichage est plus beau
Merci Cere 103626

Cere · June 2020

Super, tout les cas roulent maintenant, ne pas hesiter à essayer N=4 par exemple ! B-)-

gebrane · June 2020

Pour que vos étudiants ne copient pas collez bêtement le code, vous pouvez leurs proposer l'inverse
Au départ N voitures dans chaque parc, et le but est de mettre toutes les voitures dans le parc A par exemple avec les mêmes exigences

gebrane · June 2020

Bonjour

Énigme 2 même type

Gebrane possède 3 types de jetons qui remplacent la monnaie.
J'ai 10 jetons de type A d'une valeur chacun de (edit 1 77) 57 euro
J'ai 10 jetons de type B d'une valeur chacun de 62euro
J'ai 10 jetons de type A d'une valeur chacun de 72euro
Je commande des gâteaux pour une grande fête qui coûtent 4 euro la pièce.
Je donne au caissier moins de 600 euros ( Je vous cache le montant exact que j'ai donné, je vous cache le nombre de gâteaux que j'ai acheté et je vous cache la combinaison des jetons que j'ai donné). Le caissier m'a rendu la monnaie exacte avec aussi des jetons ( types A,B et C) edit2 ajout explicatif il ne doit pas me rendre le même type des jetons que j'ai donné, (édit 3) aussi il ne doit pas me rendre 0 jetons)
Quelle somme j'ai pu donné au caissier ( chercher toutes les solutions possibles)

Pour comprendre l’énigme une solution est S=570 euro

Pour résoudre l'exercice
Soit analyser la situation et chercher par soit même toutes les combinaisons possibles
Soit analyser la situation, donner un algorithme , programmer et trouver !

Si le gâteau coûte 12 euro la pièce , croyez moi, seul un programmeur peut donner le nombre de solutions possibles !

JLT · June 2020

Si on suppose que tu achètes au moins 1 gâteau, que chaque gâteau vaut 4€ et que tes jetons valent 77, 62 et 72 €, je trouve les solutions

124.   134.   144.   149.   154.   186.   196.   201.
206.   211.   216.   221.   226.   231.   248.   258.
263.   268.   273.   278.   283.   288.   293.   298.
303.   308.   310.   320.   325.   330.   335.   340.
345.   350.   355.   360.   365.   370.   372.   375.
380.   382.   385.   387.   392.   397.   402.   407.
412.   417.   422.   427.   432.   434.   437.   442.
444.   447.   449.   452.   454.   457.   459.   462.
464.   469.   474.   479.   484.   489.   494.   496.
499.   504.   506.   509.   511.   514.   516.   519.
521.   524.   526.   529.   531.   534.   536.   539.
541.   546.   551.   556.   558.   561.   566.   568.
571.   573.   576.   578.   581.   583.   586.   588.
591.   593.   596.   598.

J'ai peut-être fait une erreur de programmation. Peux-tu expliquer comment tu obtiens 570 ?

bisam · June 2020

Ce deuxième exercice est plutôt simple quand on connait la programmation dynamique.

Tu veux seulement une liste des montants que l'on a pu payer ou bien tu veux également le nombre de gâteaux achetés et les différentes façons de payer et de se faire rendre la monnaie ?

Considères-tu que si l'on donne des pièces d'un certain type au vendeur alors celui-ci ne doit pas rendre de pièces de ce même type (sinon on aurait pu simplifier la transaction) et même chose dans l'autre sens, bien entendu ?

gebrane · June 2020

Bonjour à tous

bisam

Considères-tu que si l'on donne des pièces d'un certain type au vendeur alors celui-ci ne doit pas rendre de pièces de ce même type: Oui, en plus il doit rendre au moins un jeton
L’idéal c'est de donner les sommes possibles que j'ai pu verser au caissier avec la monnaie exacte rendu par le caissier et le nombre de gâteaux achetés
Sinon on donne seulement les sommes possibles à verser
JLT,

570 est une solution car gebrane a pu donner 10 jetons de 57 euro et le caissier rend 1 jeton de 62 euro et 7 jetons de 72 euro donc j'ai acheté seulement un gâteau. 103646

JLT · June 2020

Tu as changé les données, au début tu disais 77, 62, 72 et maintenant c'est 57, 62, 72.

Maintenant je trouve

     72

   114   124   129   134   144   171   176   181

   186   191   196   201   206   216   228   233

   238   243   248   253   258   263   268   273

   278   285   288   290   295   300   305   310

   315   320   325   330   335   340   342   345

   347   350   352   357   360   362   367   372

   377   382   387   392   397   399   402   404

   407   409   412   414   417   419   422   424

   429   432   434   439   444   449   454   456

   459   461   464   466   469   471   474   476

   479   481   484   486   489   491   494   496

   501   504   506   511   513   516   518   521

   523   526   528   531   533   536   538   541

   543   546   548   551   553   556   558   561

   563   566   568   570   573   575   576   578

   580   583   585   588   590   593   595   598

   600

gebrane · June 2020

JLT malgré mon plus grand soin, j'ai commis cet erreur, j'ai corrigé

gebrane · June 2020

JLT est -il possible d’intégrer dans ton programme la somme rendu et le nombre de gâteux achetés?

JLT · June 2020

Je n'ai pas le temps tout de suite, mais d'abord est-ce que tu acceptes la réponse 129 ?

J'achète 18 gâteaux. Je donne 57+72, le marchand me rend 57.

gebrane · June 2020

Non inacceptable, il ne doit pas me rendre le même type des jetons que j'ai donné, autrement dit dans mon achat je dois payer avec 0 jetons d'un certain type

JLT · June 2020

Est-ce que tu acceptes 72 ? Je paye 72, le marchand ne me rend rien.

gebrane · June 2020

Le caissier a rendu des jetons. Ce cas à éliminer
edit si le programme affiche les combinaisons des jetons donnés et rendus ça facilite la vérification

JLT · June 2020

 114 = 2A+0B+0C, rendu 0A+1B+0C
 124 = 0A+2B+0C, rendu 0A+0B+1C
 134 = 0A+1B+1C, rendu 2A+0B+0C
 144 = 0A+0B+2C, rendu 0A+2B+0C
 176 = 2A+1B+0C, rendu 0A+0B+1C
 186 = 2A+0B+1C, rendu 0A+1B+0C
 206 = 0A+1B+2C, rendu 2A+0B+0C
 216 = 0A+0B+3C, rendu 0A+2B+0C
 228 = 4A+0B+0C, rendu 0A+0B+1C
 248 = 0A+4B+0C, rendu 0A+0B+1C
 258 = 2A+0B+2C, rendu 0A+1B+0C
 268 = 0A+2B+2C, rendu 4A+0B+0C
 278 = 0A+1B+3C, rendu 2A+0B+0C
 288 = 0A+0B+4C, rendu 0A+2B+0C
 300 = 4A+0B+1C, rendu 0A+2B+0C
 310 = 0A+5B+0C, rendu 2A+0B+0C
 320 = 0A+4B+1C, rendu 4A+0B+0C
 330 = 2A+0B+3C, rendu 0A+1B+0C
 340 = 0A+2B+3C, rendu 4A+0B+0C
 342 = 6A+0B+0C, rendu 0A+1B+0C
 350 = 0A+1B+4C, rendu 2A+0B+0C
 352 = 4A+2B+0C, rendu 0A+0B+1C
 360 = 0A+0B+5C, rendu 0A+2B+0C
 372 = 4A+0B+2C, rendu 0A+2B+0C
 382 = 0A+5B+1C, rendu 2A+0B+0C
 392 = 0A+4B+2C, rendu 4A+0B+0C
 402 = 2A+0B+4C, rendu 0A+1B+0C
 404 = 6A+1B+0C, rendu 0A+0B+1C
 412 = 0A+2B+4C, rendu 4A+0B+0C
 414 = 6A+0B+1C, rendu 0A+1B+0C
 422 = 0A+1B+5C, rendu 2A+0B+0C
 424 = 2A+5B+0C, rendu 0A+0B+1C
 432 = 0A+0B+6C, rendu 0A+2B+0C
 434 = 0A+7B+0C, rendu 2A+0B+0C
 444 = 4A+0B+3C, rendu 0A+2B+0C
 454 = 0A+5B+2C, rendu 2A+0B+0C
 456 = 8A+0B+0C, rendu 0A+0B+1C
 464 = 0A+4B+3C, rendu 4A+0B+0C
 474 = 2A+0B+5C, rendu 0A+1B+0C
 476 = 4A+4B+0C, rendu 0A+0B+1C
 484 = 0A+2B+5C, rendu 4A+0B+0C
 486 = 6A+0B+2C, rendu 0A+1B+0C
 494 = 0A+1B+6C, rendu 2A+0B+0C
 496 = 0A+8B+0C, rendu 0A+0B+1C
 504 = 0A+0B+7C, rendu 0A+2B+0C
 506 = 0A+7B+1C, rendu 2A+0B+0C
 516 = 4A+0B+4C, rendu 0A+2B+0C
 526 = 0A+5B+3C, rendu 2A+0B+0C
 528 = 8A+0B+1C, rendu 0A+2B+0C
 536 = 0A+4B+4C, rendu 4A+0B+0C
 546 = 2A+0B+6C, rendu 0A+1B+0C
 548 = 2A+7B+0C, rendu 0A+0B+1C
 556 = 0A+2B+6C, rendu 4A+0B+0C
 558 = 6A+0B+3C, rendu 0A+1B+0C
 566 = 0A+1B+7C, rendu 2A+0B+0C
 568 = 0A+8B+1C, rendu 4A+0B+0C
 570 = 10A+0B+0C, rendu 0A+1B+0C
 576 = 0A+0B+8C, rendu 0A+2B+0C
 578 = 0A+7B+2C, rendu 2A+0B+0C
 580 = 8A+2B+0C, rendu 0A+0B+1C
 588 = 4A+0B+5C, rendu 0A+2B+0C
 598 = 0A+5B+4C, rendu 2A+0B+0C
 600 = 8A+0B+2C, rendu 0A+2B+0C

gebrane · June 2020

Merci JLT
Peux-tu joindre ton code ici

Cet énigme a été discuté ici par des programmeurs, ( j'ai mis ma touche personnelle :-D
personne n'as trouvé toutes les combinaisons possibles.
Il leur manquait l'analyse mathématiques

Moralité
Si on fait les maths seuls : [size=large]on sait tout et rien ne marche[/size] ( rien ne marche dans le sens qu'aucun programme ne tourne )
Si on fait la programmation seule, [size=large]tout marche et personne ne sait pourquoi[/size] ( dans le sens on peut programmer tout et personne ne sait si le programme résout bien le problème

Anecdote pour rire ; Ici dans le forum d'analyse des mathematiques.net on réunit Maths et programmation , résultat :

rien ne marche et personne ne sait pourquoi
:-D

JLT · June 2020

J'ai fait ça sur scilab. Mon code est un peu moche, je n'ai pas cherché à optimiser quoi que ce soit. Voici le début :

a=57;b=62;c=72;

function t=rendu(x,y,z);
    t=[0 0 0];
    n=x*a+y*b+z*c;
    c=modulo(n,4);
    if c==0 then
        if z==0 & c<n then t=[0 0 1];
        elseif y==0 & 2*b<n then t=[0 2 0];
            elseif x==0 & 4*a<n then t=[4 0 0]; 
        end
    elseif c==2 then
        if (y==0 & b<n) then t=[0 1 0];
        elseif (x==0 & 2*a<n) then t=[2 0 0];
        end
    end
endfunction

Ce code crée une fonction [u,v,w]=rendu(x,y,z) :
Je donne x jetons A, y jetons B et z jetons C au marchand.
Le marchand rend u jetons A, v jetons B et w jetons C afin que la différence soit un multiple non nul de 4 si c'est possible, sinon la fonction retourne [0,0,0].

A partir de là, il suffit d'essayer toutes les valeurs de x entre 0 et 10, y entre 0 et 9, z entre 0 et 8 en contrôlant que $xyz=0$ et $xa+yb+zc\leqslant 600$ :

N=zeros(7,600);
for x=0:10
    for y=0:9;
        for z=0:8;
            n=x*a+y*b+z*c;
            if n<601 & n>0 & x*y*z==0 then
                t=rendu(x,y,z);
                u=t(1);v=t(2);w=t(3);
                if u+v+w>0 then N(:,n)=[1 x y z u v w];
                end
            end
        end
    end
end

for n=1:600;
    if N(1,n)==1 then
        x=N(2,n);y=N(3,n);z=N(4,n);u=N(5,n);v=N(6,n);w=N(7,n);
        disp(string(n)+" = "+string(x)+"A+"+string(y)+"B+"+string(z)+"C, rendu "+string(u)+"A+"+string(v)+"B+"+string(w)+"C");
    end
end

gebrane · June 2020

merci JLT

gebrane · June 2020

GLT Bonjour,
Il y a un problème dans ton programme
par exemple pour la somme 134 euro, ton programme me dit que pour acheter 5 gâteaux ( d'une valeur de 20 euro)
il y a possibilité que je donne 134 =1B+1C euro pour qu'il me rend 114=2B euro. mais logiquement dans ce , je dois donner seulement un jeton , n'importe lequel, ça suffit pour acheter les 5 gâteaux. il faut prendre compte de cette condition même si ce n'est pas dit

edit , après réflexion je me sens bête et ton programme est plus intelligent que moi . car si je donne seulement une pièce pour acheter les 5 gâteaux , je serai perdant car le marchand ne va rien me rendre et ton programme me donne une façon intelligente d'acheter 5 gâteaux sans perte

bisam · June 2020

J'ai fait une méthode très générale.
Pour chaque montant payé, il peut y avoir plusieurs achats possibles : j'ai donné toutes les réponses envisageables.

def valeur(distrib, pieces):
    return sum(p*x for p,x in zip(distrib, pieces))

def payables(pieces, maxi):
    """Renvoie un dictionnaire associant à tous les montants inférieurs ou égaux
    à maxi et payables avec des pièces ayant les valeurs données une liste des
    distributions possibles de pièces représentant les différentes façons de
    payer ces montants."""

    distributions = {0: [[0 for piece in pieces]]}
    for j in range(maxi+1):
        if j in distributions:
            for k, piece in enumerate(pieces):
                if j+piece <= maxi:
                    distributions[j+piece] = []
                    for distrib in distributions[j]:
                        new = distrib[:]
                        new[k] += 1
                        distributions[j+piece].append(new)
    return distributions

def payback(montant, pieces, maxi):
    """Renvoie les différentes façons de payer le montant donné avec des pièces
    ayant les valeurs données, en donnant au vendeur un montant inférieur ou
    égal à maxi."""

    distributions = payables(pieces, maxi)
    facons = set()
    for payable in distributions:
        if payable + montant in distributions:
            for donne in distributions[payable + montant]:
                for rend in distributions[payable]:
                    facons.add(tuple(d-r for d,r in zip(donne, rend)))
    return facons

def solution(prix_gateau, pieces, maxi):
    """Affiche la liste des montants que l'on a pu payer ainsi que le montant rendu
    et les distributions correspondantes et le nombre de gâteaux achetés."""

    results = {}
    for prix in range(prix_gateau, maxi+1, prix_gateau):
        for distrib in payback(prix, pieces, maxi):
            donne = tuple(max(m,0) for m in distrib)
            rend = tuple(max(-m,0) for m in distrib)
            montant_donne = valeur(donne, pieces)
            montant_rendu = valeur(rend, pieces)
            if montant_rendu:
                if montant_donne in results:
                    results[montant_donne].append((donne, rend))
                else:
                    results[montant_donne] = [(donne, rend)]

    for montant_donne in sorted(results.keys()):
        for donne, rend in results[montant_donne]:
            montant_rendu = valeur(rend, pieces)
            nombre_gateaux = (montant_donne - montant_rendu)//prix_gateau
            str1 = "Pour acheter {} gâteaux, on a payé {} =".format(nombre_gateaux, montant_donne)
            str2 = " + ".join("{}x{}".format(d,p) for d,p in zip(donne, pieces))
            str3 = "et on nous a rendu {} =".format(montant_rendu)
            str4 = " + ".join("{}x{}".format(r,p) for r,p in zip(rend, pieces))
            print(str1, str2, str3, str4)

Du coup, l'appel de

solution(4, (57,62,72), 600)

affiche :

Pour acheter 13 gâteaux, on a payé 114 = 2x57 + 0x62 + 0x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 13 gâteaux, on a payé 124 = 0x57 + 2x62 + 0x72 et on nous a rendu 72 = 0x57 + 0x62 + 1x72
Pour acheter 5 gâteaux, on a payé 134 = 0x57 + 1x62 + 1x72 et on nous a rendu 114 = 2x57 + 0x62 + 0x72
Pour acheter 5 gâteaux, on a payé 144 = 0x57 + 0x62 + 2x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 8 gâteaux, on a payé 176 = 2x57 + 1x62 + 0x72 et on nous a rendu 144 = 0x57 + 0x62 + 2x72
Pour acheter 26 gâteaux, on a payé 176 = 2x57 + 1x62 + 0x72 et on nous a rendu 72 = 0x57 + 0x62 + 1x72
Pour acheter 31 gâteaux, on a payé 186 = 2x57 + 0x62 + 1x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 23 gâteaux, on a payé 206 = 0x57 + 1x62 + 2x72 et on nous a rendu 114 = 2x57 + 0x62 + 0x72
Pour acheter 10 gâteaux, on a payé 216 = 0x57 + 0x62 + 3x72 et on nous a rendu 176 = 2x57 + 1x62 + 0x72
Pour acheter 23 gâteaux, on a payé 216 = 0x57 + 0x62 + 3x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 3 gâteaux, on a payé 228 = 4x57 + 0x62 + 0x72 et on nous a rendu 216 = 0x57 + 0x62 + 3x72
Pour acheter 8 gâteaux, on a payé 228 = 4x57 + 0x62 + 0x72 et on nous a rendu 196 = 0x57 + 2x62 + 1x72
Pour acheter 21 gâteaux, on a payé 228 = 4x57 + 0x62 + 0x72 et on nous a rendu 144 = 0x57 + 0x62 + 2x72
Pour acheter 26 gâteaux, on a payé 228 = 4x57 + 0x62 + 0x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 39 gâteaux, on a payé 228 = 4x57 + 0x62 + 0x72 et on nous a rendu 72 = 0x57 + 0x62 + 1x72
Pour acheter 49 gâteaux, on a payé 258 = 2x57 + 0x62 + 2x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 10 gâteaux, on a payé 268 = 0x57 + 2x62 + 2x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 41 gâteaux, on a payé 278 = 0x57 + 1x62 + 3x72 et on nous a rendu 114 = 2x57 + 0x62 + 0x72
Pour acheter 15 gâteaux, on a payé 288 = 0x57 + 0x62 + 4x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 28 gâteaux, on a payé 288 = 0x57 + 0x62 + 4x72 et on nous a rendu 176 = 2x57 + 1x62 + 0x72
Pour acheter 41 gâteaux, on a payé 288 = 0x57 + 0x62 + 4x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 44 gâteaux, on a payé 300 = 4x57 + 0x62 + 1x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 67 gâteaux, on a payé 330 = 2x57 + 0x62 + 3x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 28 gâteaux, on a payé 340 = 0x57 + 2x62 + 3x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 16 gâteaux, on a payé 342 = 6x57 + 0x62 + 0x72 et on nous a rendu 278 = 0x57 + 1x62 + 3x72
Pour acheter 34 gâteaux, on a payé 342 = 6x57 + 0x62 + 0x72 et on nous a rendu 206 = 0x57 + 1x62 + 2x72
Pour acheter 52 gâteaux, on a payé 342 = 6x57 + 0x62 + 0x72 et on nous a rendu 134 = 0x57 + 1x62 + 1x72
Pour acheter 70 gâteaux, on a payé 342 = 6x57 + 0x62 + 0x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 2 gâteaux, on a payé 350 = 0x57 + 1x62 + 4x72 et on nous a rendu 342 = 6x57 + 0x62 + 0x72
Pour acheter 59 gâteaux, on a payé 350 = 0x57 + 1x62 + 4x72 et on nous a rendu 114 = 2x57 + 0x62 + 0x72
Pour acheter 16 gâteaux, on a payé 352 = 4x57 + 2x62 + 0x72 et on nous a rendu 288 = 0x57 + 0x62 + 4x72
Pour acheter 34 gâteaux, on a payé 352 = 4x57 + 2x62 + 0x72 et on nous a rendu 216 = 0x57 + 0x62 + 3x72
Pour acheter 52 gâteaux, on a payé 352 = 4x57 + 2x62 + 0x72 et on nous a rendu 144 = 0x57 + 0x62 + 2x72
Pour acheter 70 gâteaux, on a payé 352 = 4x57 + 2x62 + 0x72 et on nous a rendu 72 = 0x57 + 0x62 + 1x72
Pour acheter 2 gâteaux, on a payé 360 = 0x57 + 0x62 + 5x72 et on nous a rendu 352 = 4x57 + 2x62 + 0x72
Pour acheter 33 gâteaux, on a payé 360 = 0x57 + 0x62 + 5x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 46 gâteaux, on a payé 360 = 0x57 + 0x62 + 5x72 et on nous a rendu 176 = 2x57 + 1x62 + 0x72
Pour acheter 59 gâteaux, on a payé 360 = 0x57 + 0x62 + 5x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 62 gâteaux, on a payé 372 = 4x57 + 0x62 + 2x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 85 gâteaux, on a payé 402 = 2x57 + 0x62 + 4x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 11 gâteaux, on a payé 404 = 6x57 + 1x62 + 0x72 et on nous a rendu 360 = 0x57 + 0x62 + 5x72
Pour acheter 29 gâteaux, on a payé 404 = 6x57 + 1x62 + 0x72 et on nous a rendu 288 = 0x57 + 0x62 + 4x72
Pour acheter 47 gâteaux, on a payé 404 = 6x57 + 1x62 + 0x72 et on nous a rendu 216 = 0x57 + 0x62 + 3x72
Pour acheter 65 gâteaux, on a payé 404 = 6x57 + 1x62 + 0x72 et on nous a rendu 144 = 0x57 + 0x62 + 2x72
Pour acheter 83 gâteaux, on a payé 404 = 6x57 + 1x62 + 0x72 et on nous a rendu 72 = 0x57 + 0x62 + 1x72
Pour acheter 46 gâteaux, on a payé 412 = 0x57 + 2x62 + 4x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 88 gâteaux, on a payé 414 = 6x57 + 0x62 + 1x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 20 gâteaux, on a payé 422 = 0x57 + 1x62 + 5x72 et on nous a rendu 342 = 6x57 + 0x62 + 0x72
Pour acheter 77 gâteaux, on a payé 422 = 0x57 + 1x62 + 5x72 et on nous a rendu 114 = 2x57 + 0x62 + 0x72
Pour acheter 7 gâteaux, on a payé 432 = 0x57 + 0x62 + 6x72 et on nous a rendu 404 = 6x57 + 1x62 + 0x72
Pour acheter 20 gâteaux, on a payé 432 = 0x57 + 0x62 + 6x72 et on nous a rendu 352 = 4x57 + 2x62 + 0x72
Pour acheter 51 gâteaux, on a payé 432 = 0x57 + 0x62 + 6x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 64 gâteaux, on a payé 432 = 0x57 + 0x62 + 6x72 et on nous a rendu 176 = 2x57 + 1x62 + 0x72
Pour acheter 77 gâteaux, on a payé 432 = 0x57 + 0x62 + 6x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 80 gâteaux, on a payé 444 = 4x57 + 0x62 + 3x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 6 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 432 = 0x57 + 0x62 + 6x72
Pour acheter 11 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 412 = 0x57 + 2x62 + 4x72
Pour acheter 24 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 360 = 0x57 + 0x62 + 5x72
Pour acheter 29 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 340 = 0x57 + 2x62 + 3x72
Pour acheter 42 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 288 = 0x57 + 0x62 + 4x72
Pour acheter 47 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 268 = 0x57 + 2x62 + 2x72
Pour acheter 60 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 216 = 0x57 + 0x62 + 3x72
Pour acheter 65 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 196 = 0x57 + 2x62 + 1x72
Pour acheter 78 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 144 = 0x57 + 0x62 + 2x72
Pour acheter 83 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 96 gâteaux, on a payé 456 = 8x57 + 0x62 + 0x72 et on nous a rendu 72 = 0x57 + 0x62 + 1x72
Pour acheter 103 gâteaux, on a payé 474 = 2x57 + 0x62 + 5x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 7 gâteaux, on a payé 484 = 0x57 + 2x62 + 5x72 et on nous a rendu 456 = 8x57 + 0x62 + 0x72
Pour acheter 64 gâteaux, on a payé 484 = 0x57 + 2x62 + 5x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 106 gâteaux, on a payé 486 = 6x57 + 0x62 + 2x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 38 gâteaux, on a payé 494 = 0x57 + 1x62 + 6x72 et on nous a rendu 342 = 6x57 + 0x62 + 0x72
Pour acheter 95 gâteaux, on a payé 494 = 0x57 + 1x62 + 6x72 et on nous a rendu 114 = 2x57 + 0x62 + 0x72
Pour acheter 12 gâteaux, on a payé 504 = 0x57 + 0x62 + 7x72 et on nous a rendu 456 = 8x57 + 0x62 + 0x72
Pour acheter 25 gâteaux, on a payé 504 = 0x57 + 0x62 + 7x72 et on nous a rendu 404 = 6x57 + 1x62 + 0x72
Pour acheter 38 gâteaux, on a payé 504 = 0x57 + 0x62 + 7x72 et on nous a rendu 352 = 4x57 + 2x62 + 0x72
Pour acheter 69 gâteaux, on a payé 504 = 0x57 + 0x62 + 7x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 82 gâteaux, on a payé 504 = 0x57 + 0x62 + 7x72 et on nous a rendu 176 = 2x57 + 1x62 + 0x72
Pour acheter 95 gâteaux, on a payé 504 = 0x57 + 0x62 + 7x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 98 gâteaux, on a payé 516 = 4x57 + 0x62 + 4x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 101 gâteaux, on a payé 528 = 8x57 + 0x62 + 1x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 121 gâteaux, on a payé 546 = 2x57 + 0x62 + 6x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 25 gâteaux, on a payé 556 = 0x57 + 2x62 + 6x72 et on nous a rendu 456 = 8x57 + 0x62 + 0x72
Pour acheter 82 gâteaux, on a payé 556 = 0x57 + 2x62 + 6x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 124 gâteaux, on a payé 558 = 6x57 + 0x62 + 3x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 56 gâteaux, on a payé 566 = 0x57 + 1x62 + 7x72 et on nous a rendu 342 = 6x57 + 0x62 + 0x72
Pour acheter 113 gâteaux, on a payé 566 = 0x57 + 1x62 + 7x72 et on nous a rendu 114 = 2x57 + 0x62 + 0x72
Pour acheter 1 gâteaux, on a payé 570 = 10x57 + 0x62 + 0x72 et on nous a rendu 566 = 0x57 + 1x62 + 7x72
Pour acheter 19 gâteaux, on a payé 570 = 10x57 + 0x62 + 0x72 et on nous a rendu 494 = 0x57 + 1x62 + 6x72
Pour acheter 37 gâteaux, on a payé 570 = 10x57 + 0x62 + 0x72 et on nous a rendu 422 = 0x57 + 1x62 + 5x72
Pour acheter 55 gâteaux, on a payé 570 = 10x57 + 0x62 + 0x72 et on nous a rendu 350 = 0x57 + 1x62 + 4x72
Pour acheter 73 gâteaux, on a payé 570 = 10x57 + 0x62 + 0x72 et on nous a rendu 278 = 0x57 + 1x62 + 3x72
Pour acheter 91 gâteaux, on a payé 570 = 10x57 + 0x62 + 0x72 et on nous a rendu 206 = 0x57 + 1x62 + 2x72
Pour acheter 109 gâteaux, on a payé 570 = 10x57 + 0x62 + 0x72 et on nous a rendu 134 = 0x57 + 1x62 + 1x72
Pour acheter 127 gâteaux, on a payé 570 = 10x57 + 0x62 + 0x72 et on nous a rendu 62 = 0x57 + 1x62 + 0x72
Pour acheter 30 gâteaux, on a payé 576 = 0x57 + 0x62 + 8x72 et on nous a rendu 456 = 8x57 + 0x62 + 0x72
Pour acheter 43 gâteaux, on a payé 576 = 0x57 + 0x62 + 8x72 et on nous a rendu 404 = 6x57 + 1x62 + 0x72
Pour acheter 56 gâteaux, on a payé 576 = 0x57 + 0x62 + 8x72 et on nous a rendu 352 = 4x57 + 2x62 + 0x72
Pour acheter 87 gâteaux, on a payé 576 = 0x57 + 0x62 + 8x72 et on nous a rendu 228 = 4x57 + 0x62 + 0x72
Pour acheter 100 gâteaux, on a payé 576 = 0x57 + 0x62 + 8x72 et on nous a rendu 176 = 2x57 + 1x62 + 0x72
Pour acheter 113 gâteaux, on a payé 576 = 0x57 + 0x62 + 8x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 1 gâteaux, on a payé 580 = 8x57 + 2x62 + 0x72 et on nous a rendu 576 = 0x57 + 0x62 + 8x72
Pour acheter 19 gâteaux, on a payé 580 = 8x57 + 2x62 + 0x72 et on nous a rendu 504 = 0x57 + 0x62 + 7x72
Pour acheter 37 gâteaux, on a payé 580 = 8x57 + 2x62 + 0x72 et on nous a rendu 432 = 0x57 + 0x62 + 6x72
Pour acheter 55 gâteaux, on a payé 580 = 8x57 + 2x62 + 0x72 et on nous a rendu 360 = 0x57 + 0x62 + 5x72
Pour acheter 73 gâteaux, on a payé 580 = 8x57 + 2x62 + 0x72 et on nous a rendu 288 = 0x57 + 0x62 + 4x72
Pour acheter 91 gâteaux, on a payé 580 = 8x57 + 2x62 + 0x72 et on nous a rendu 216 = 0x57 + 0x62 + 3x72
Pour acheter 109 gâteaux, on a payé 580 = 8x57 + 2x62 + 0x72 et on nous a rendu 144 = 0x57 + 0x62 + 2x72
Pour acheter 127 gâteaux, on a payé 580 = 8x57 + 2x62 + 0x72 et on nous a rendu 72 = 0x57 + 0x62 + 1x72
Pour acheter 116 gâteaux, on a payé 588 = 4x57 + 0x62 + 5x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72
Pour acheter 119 gâteaux, on a payé 600 = 8x57 + 0x62 + 2x72 et on nous a rendu 124 = 0x57 + 2x62 + 0x72

gebrane · June 2020

Bissam. Ton programme affiche des résultats erronés. Un gâteau coûte 4 euro .A la première ligne , le programme doit afficher pour acheter 13 gâteaux

bisam · June 2020

Ah oui, j'ai oublié de modifier une ligne... Je corrige.

gebrane · June 2020

Merci bissam pour ce programmme . Ça montre par exemple si je viens de vous dire que j' ai acheté 4 gâteaux. Vous pouvez répondre tu as menti gebrane d'après le programme de Bissam.

On peut rendre l'enigme plus difficile. On suppose gebrane a assez de jetons de tous types aussi le marchand. Existe-t-il toujours une stratégie pour acheter n gâteaux sans perte:
Si on donne la somme exacte du prix des n gateaux, donc le marchand ne rend rien, on accepte
Si on donne une somme supérieure au prix des n gâteaux, le marchand doit nous rendre la différence exacte.
Bien sûr, le marchand ne doit rendre la monnaie avec les mêmes jetons donnés

Pour simplifier puis-je acheté 4 gateaux sans perte.

bisam · June 2020

Mathématiquement, (si j'ai bonne mémoire), on peut démontrer que pour toute liste d'entiers naturels non nuls $(m_1,\dots,m_p)$ premiers entre eux dans leur ensemble, il existe un entier $N$ tel que que pour tout $n\geq N$, il existe des entiers naturels $(c_1,\dots,c_p)$ tels que $c_1m_1+\cdots+c_pm_p=n$.
Lorsque $p=2$, on peut même préciser la valeur de $N$.

On en déduit immédiatement que pour toute liste d'entiers naturels non nuls $(m_1,\dots,m_p)$ premiers entre eux dans leur ensemble et pour tout entier $n$, il existe des entiers relatifs $(c_1,\dots,c_p)$ tels que $c_1m_1+\cdots+c_pm_p=n$.

Si les $(m_1,\dots,m_p)$ sont les valeurs des jetons, on en déduit que l'on peut payer n'importe quel montant (avec rendu de monnaie) dès que les valeurs sont premières entre elles.

Le problème qui se pose, c'est que l'on n'a a priori aucune idée du nombre minimal de jetons à utiliser.

Pour 4 gâteaux à 4 euros, en augmentant le seuil à 650€, on voit que l'on peut payer 9*72€ et se faire rendre 10*57 + 1*62. Il suffit d'appeler "payback(4*4, (57,62,72), 650)" pour avoir cette solution.

gebrane · June 2020

Merci bisam pour tes explications riches et profondes.
Si des membres intéressés, je peux donner une énigme 3.

gebrane · June 2020

Je laisse ce fil reposé en paix .
Je remercie tous les intervenants 103886

Rescassol · June 2020

Bonjour,

Gebrane, ton Hanoï se résout simplement en utilisant l'algorithme classique de Hanoï ordinaire très légèrement modifié.

Cordialement,

Rescassol

bisam · June 2020

J'ai écrit un petit programme qui me donne les résultats suivants :
Pour $n=2$, c'est-à-dire pour 4 disques bicolores, j'ai une réponse en 12 mouvements.
Pour $n=3$, c'est-à-dire pour 6 disques bicolores, j'ai une réponse en 58 mouvements.
Pour $n=4$, c'est-à-dire pour 8 disques bicolores, j'ai une réponse en 248 mouvements.
Pour $n=5$, c'est-à-dire pour 10 disques bicolores, j'ai une réponse en 1014 mouvements.

Ma stratégie consiste à appliquer la méthode classique des tours de Hanoi et faire les mouvements ainsi :
- déplacer 2n-1 disques de A vers B
- déplacer le plus grand disque, noir, de A vers C
- déplacer 2n-2 disques de B vers C
- déplacer 2n-3 disques de C vers B
- ...
- déplacer 2 disques de B vers C
- déplacer le dernier disque, blanc, de C vers B

Il y a peut-être plus rapide...

Voici le code

def move(nb_disques, tour1, tour2, verbose=False, all_moves=None):
    """Renvoie la liste des mouvements nécessaires pour déplacer nb_disques de la
    tour1 à la tour2."""

    if all_moves is None:
        all_moves = []

    if nb_disques == 1:
        if verbose:
            print("De {} vers {}".format(tour1, tour2))
        all_moves.append((tour1, tour2))
    elif nb_disques > 1:
        tour3 = 3-tour1-tour2
        move(nb_disques-1, tour1, tour3, verbose, all_moves)
        move(1, tour1, tour2, verbose, all_moves)
        move(nb_disques-1, tour3, tour2, verbose, all_moves)
    return all_moves

def move_bicolore(N, verbose=False):
    """Renvoie la liste des mouvements nécessaires pour déplacer 2*N disques
    bicolores, alternativement blancs et noirs, avec un noir tout en bas, placés
    sur la tour 0, afin de placer les blancs sur la tour 1 et les noirs sur la tour 2."""

    all_moves = []
    move(2*N-1, 0, 1, verbose, all_moves)
    move(1, 0, 2, verbose, all_moves)
    for k in range(2*N-2, 0, -1):
        move(k, 1+(k%2), 2-(k%2), verbose, all_moves)
    return all_moves

Les tours sont nommées 0,1,2 au lieu de A,B,C et un mouvement est simplement enregistré sous la forme d'un couple (départ, arrivée). Les fonctions renvoient la liste des mouvements à effectuer dans l'ordre.
Je n'ai pas fait d'affichage, mais ce n'est pas très difficile de créer des piles correspondants à chaque tour et de faire l'affichage correspondant.

Rescassol · June 2020

Bonjour,

Bisam, c'est la méthode que j'avais en tête, mais je ne l'avais pas programmée.
Je ne suis pas sûr qu'il y ait plus rapide.

Cordialement,

Rescassol

gebrane · June 2020

Bonjour
Ça!, c’était la question la plus facile de l’énigme.

Pour Hanoi classique, pour n disques, le nombre d’étapes minimale est $2^n -1$
Chercher le nombre d’étapes minimale pour la tour de gebrane
Pour 4 disques , Hanoï classique se fait en 15 étapes et Hanoï gebrane se fait en 11 étapes ' le programme de bisam n'est pas optimisé)

Il y a donc un travail informatique qui suggère une formule mathématiques de nombre d’étapes.
Merci bisam et Rescassoll pour l’intérêt.

Namiswan · June 2020

Pour N disques, j'obtiens que le nombre d'étapes vaut $\displaystyle\left[\frac{5\cdot 2^N}{7}\right]$

gebrane · June 2020

Namiswan bonjour

Peux-tu expliquer comment arrives-tu à la formule

Namiswan · June 2020

Je laisse un petit peu les curieux chercher d'où ça sort :-)

bisam · June 2020

A la main, j'ai réussi à améliorer le nombre de mouvements, et j'ai une petite idée pour améliorer l'algorithme... mais je n'arrive pas à mettre la main sur le cas général qui semble dépendre de la décomposition en base $2$ de $n$.
Pour $n=2,3,4$, j'ai désormais $11,45,182$ déplacements, ce qui semble correspondre à la formule de Namiswan.

gebrane · June 2020

Ok namiswan. je fais confiance à bisam ou JLT (s'il a un temps pour regarder).
Ce Hanoi modifié est un casse tête. Je confirme le nombre 45 pour 6 disques

jandri · June 2020

Je trouve comme Namiswan.

Cela résulte d'une formule de récurrence qui n'est pas très difficile à démontrer quand on connait le résultat pour les tours de Hanoï classiques.

bisam · June 2020

J'ai trouvé un moyen de m'en sortir !!
Voici le nouveau code qui donne bien les résultats voulus :

def move_bicolore(N, depart=0, verbose=False, all_moves=None):
    """Renvoie la liste des mouvements nécessaires pour déplacer N disques
    bicolores, alternativement blancs et noirs, avec un blanc en haut, placés
    sur la tour depart, afin de placer les blancs sur la tour 1 et les noirs sur la tour 2."""

    if all_moves is None:
        all_moves = []

    if N == 1:
        if depart != 1:
            if verbose:
                print("De {} vers {}".format(depart, 1))
            all_moves.append((depart, 1))
    elif N > 1:
        if N%2:
            if depart == 1:
                move(N-2, 1, 0, verbose, all_moves)
                move(1, 1, 2, verbose, all_moves)
                move_bicolore(N-2, 0, verbose, all_moves)
            else:
                move(N-1, depart, 2-depart, verbose, all_moves)
                move(1, depart, 1, verbose, all_moves)
                move_bicolore(N-1, 2-depart, verbose, all_moves)
        else:
            if depart == 2:
                move(N-2, 2, 0, verbose, all_moves)
                move(1, 2, 1, verbose, all_moves)
                move_bicolore(N-2, 0, verbose, all_moves)
            else:
                move(N-1, depart, 1-depart, verbose, all_moves)
                move(1, depart, 2, verbose, all_moves)
                move_bicolore(N-1, 1-depart, verbose, all_moves)
    return all_moves

Le principe est le même que pour les tours de Hanoi classiques sauf que l'on regarde la parité du nombre de disques à déplacer et la pile depuis laquelle on part. En gros, si le disque le plus bas de la pile à déplacer est déjà à sa place finale... on ne le déplace pas ! Du coup, on économise des mouvements.

Énigmes de gebrane et Namiswan

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 33