MPO 106 - Distribution de bonbons

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

MPO 106 - Distribution de bonbons

Message par Schraf »

Voici un exercice tiré du site Codewars qu'il peut être amusant de programmer sur nos pockets

À la maternelle, l’instituteur a donné des bonbons aux enfants. Le nombre de bonbons que chaque enfant reçoit n'est pas toujours le même. Voici par exemple une répartition initiale : candies = [10,2,8,22,16,4,10,6,14,20]. Remarquez que le nombre d'enfants peut lui-aussi être variable.

L’instituteur a demandé aux enfants de faire un cercle et de jouer à un jeu : chaque enfant donne la moitié de ses bonbons à l'enfant sur sa droite (en même temps). Si le nombre de bonbons est un nombre impair, l'enseignant lui donne un bonbon supplémentaire pour que le partage tombe juste.

On répète cette procédure jusqu'à ce que les enfants aient le même nombre de bonbons. Vous devez renvoyer deux nombres :

1 - Combien de temps va durer la distribution
2 - Combien chaque enfant a de bonbons à la fin du jeu

Exemple de déroulement :

Code : Tout sélectionner

candies = [ 1,2,3,4,5 ]

Distribution 1: [ 4,2,3,4,5 ]
Distribution 2: [ 5,3,3,4,5 ]
Distribution 3: [ 6,5,4,4,5 ]
Distribution 4: [ 6,6,5,4,5 ]
Distribution 5: [ 6,6,6,5,5 ]
Distribution 6: [ 6,6,6,6,6 ]

Le programme donnera donc en réponse [6,6] (6 tours et 6 bonbons par enfant)
Sommaire des MPO
Modifié en dernier par Schraf le 04 mars 2022 09:49, modifié 1 fois.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: MPO 106 - Distribution de bonbons

Message par zpalm »

Cool 😎

Pour ce genre de problème j’aime bien commencer par une première approche sur HP Prime, c’est plus simple pour moi que de se lancer directement dans du RPN ou du RPL.

Voici donc un premier programme basé sur des listes et indépendant du nombre d’enfants :

Code : Tout sélectionner

EXPORT MPO106(Bo)
BEGIN
 LOCAL Bn,t;
 REPEAT
  t+1▶t; REVERSE(CEILING(Bo/2)▶Bo)▶Bn; Bo+REVERSE(SUPPRESS(Bn(1)▶Bn(0),1))▶Bo;
 UNTIL ΠLIST(Bo==Bo(1));
 [t,Bo(1)];
END;
MPO106({1,2,3,4,5}) retourne [6,6]
MPO106({10,2,8,22,16,4,10,6,15,20}) retourne [12,18]

On peut ajouter une ligne PRINT(Bo); avant UNTIL pour suivre l’évolution de la distribution des bonbons à chaque tour.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 106 - Distribution de bonbons

Message par C.Ret »

Moi, je commence par essayer de comprendre de quoi il s'agit.

Le vecteur [ 1 2 3 4 5 ] signifie donc qu'il y a cinq enfants formant une ronde.

je vais les appeler [ A B C D E ]

Donc Annie ne reçois qu'un seul bonbon, Bernard deux, Claude trois, Denis quatre et Eric cinq.

Ca m'étonne pas, Eric est certainement le chouchou de cet instituteur.
Bon, les enfants ont pour instruction de donner la moitié de leur lot à leur voisin de droite. Bon j'entends déjà les pleurs et grincement de dents, certains enfants ont reçu un nombre impair de bonbons (La pauvre Annie en particulier n'en a qu'un seul :(
Heureusement, l'instituteur leur donnera un bonbon de plus à chaque fois pour qu'ils puissent diviser par deux leur trésor.

Chaque enfant passe donc la moitié de ces bonbons à son voisin de droite. Chaque voisin donne donc la moitié de son capital et reçois en retour la moitié donc la moitié du capital de son voisin de gauche. Et le tout boucle sur lui-même puise qu'ils forment une ronde.

Tiens, tiens, cette façon de fonctionner me rappelle vaguement quelque chose, il faut que je retrouve mon Manuel de Cinétique Chimique, il y a un paragraphe dans le chapitre des réactions chimiques que j'aimerai relire ...
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8384
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: MPO 106 - Distribution de bonbons

Message par badaze »

J’ai fait un programme pour Sharp PC 1350. Étonnamment, il a fonctionné du premier coup… Enfin je veux dire que ça ne boucle pas et que ça s’arrête autour de 10 itérations pour 8 valeurs de entre 1 et 15.
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: MPO 106 - Distribution de bonbons

Message par zpalm »

En testant différentes combinaisons j’ai eu brièvement l’espoir que le résultat final soit indépendant de l’ordre de distribution des bonbons.

En effet:
{1,2,3,4,5} donne [6,6]
{5,4,3,2,1} donne [6,6]
{2,1,4,3,5} donne [6,6]
{1,3,2,5,4} donne [6,6]

Mais:
{5,1,4,3,2} donne [2,4]

les deux tours sont:
{4,3,4,3,4}
{4,4,4,4,4}

Donc s’il existe une formule directe donnant le résultat elle doit tenir compte de l’ordre des valeurs.

ÉDIT: voici une version un peu plus courte de mon programme pour la HP Prime qui n’utilise plus qu’une seule liste au lieu de deux:

Code : Tout sélectionner

EXPORT MPO106(Bo)
BEGIN
 LOCAL t;
 REPEAT
  t+1▶t; EXECON("&1+&2",CEILING(CONCAT(Bo(0),Bo)/2))▶Bo; 
 UNTIL ΠLIST(Bo==Bo(1));
 [t,Bo(1)];
END;
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 106 - Distribution de bonbons

Message par Schraf »

Pour les calculatrices récentes (Ti-83 Edition Python, NUMWORKS, CASIO GRAPH 90, 35+E II) :

Code : Tout sélectionner

from math import ceil

def MPO106(Bo):
    t = 0
    while max(Bo) != min(Bo):
        t += 1
        Bo = [ceil(b/2) + ceil(Bo[k-1]/2) for (k,b) in enumerate(Bo)]
    return [t, Bo[0]]

>> MPO106([1,2,3,4,5])
[6, 6]

>> MPO106([10,2,8,22,16,4,10,6,15,20])
[12, 18]
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8384
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: MPO 106 - Distribution de bonbons

Message par badaze »

Je ne connais pas le langage de programmation…

Code : Tout sélectionner

while max(Bo) != min(Bo):
Si je me réfère aux langages que je connais, la boucle boucle tant que le plus grand élément de la liste est différent du plus petit.
Si c’est le cas alors on peut sortir de la boucle bien avant que toutes les valeurs de la liste aient la même valeur. Non ?
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8384
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: MPO 106 - Distribution de bonbons

Message par badaze »

Schraf a écrit : 04 mars 2022 08:31 Pour les calculatrices récentes (Ti-83 Edition Python, NUMWORKS, CASIO GRAPH 90, 35+E II) :

Code : Tout sélectionner

from math import ceil

def MPO106(Bo):
    t = 0
    while max(Bo) != min(Bo):
        t += 1
        Bo = [ceil(b/2) + ceil(Bo[k-1]/2) for (k,b) in enumerate(Bo)]
    return [t, Bo[0]]

>> MPO106([1,2,3,4,5])
[6, 6]

>> MPO106([10,2,8,22,16,4,10,6,15,20])
[12, 18]
Dans ton code, quelle est la partie qui passe les bonbons du dernier élément au premier ?
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 106 - Distribution de bonbons

Message par Schraf »

@badaze : si dans une liste la plus grande valeur est égale à la plus petite, c'est que tous les éléments de la liste sont égaux, non ?

Pour le passage du dernier enfant au premier :

1) (k,b) in enumerate(Bo) permet d'obtenir le rang k (0 puis 1 puis...) et la valeur correspondante b dans la liste Bo
2) j'utilise le fait qu'en Python Bo[-1] permet de récupérer le dernier élément de la liste Bo. Donc lorsque k = 0, Bo[k-1]/2 = Bo[-1]/2 est bien la moitié des bonbons du dernier enfant + b/2 (ce que le premier enfant garde)
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: MPO 106 - Distribution de bonbons

Message par bernouilli92 »

Voici ma version pour hp48g/gx :

Code : Tout sélectionner

« 
  DUP SIZE 0 → S N
  «
    DO 
      2 / CEIL 
      DUP S GET OVER 1 S 1 - SUB + 
      ADD 
      'N' 1 STO+
    UNTIL 
      DUP SORT DUP 1 GET 
      SWAP S GET ==
    END 
    N SWAP 1 GET 2 →LIST
  »
»
Ça prend en entrée une liste de nombres, exemple { 1 2 3 4 }
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 106 - Distribution de bonbons

Message par Schraf »

@bernouilli92 : concernant le test final sur la liste pour savoir si tous les éléments sont identiques, est-il possible en RPL d'obtenir le max d'une liste ? Je vois que {-1. -2.} ABS donne bien {1. 2.} mais message d'erreur avec MAX...

Je pensais à quelque chose comme 0 == max(abs(ΔLIST liste)) pour savoir si les éléments sont identiques.
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: MPO 106 - Distribution de bonbons

Message par bernouilli92 »

Je ne sais pas trop.
En général les opérateurs fonctionnent sur les listes et s'appliquent à chaque élément de la liste.
exemple : { 2 4 6 } { 5 4 2 } MAX -> { 5 4 6 }

Mais j'ai trouvé comment économiser 9 octets, on trie la liste et ensuite on compare la liste avec la liste inversée.

Nouvelle version :

Code : Tout sélectionner

« 
  DUP SIZE 0 → S N
  «
    DO 
      2 / CEIL 
      DUP S GET OVER 1 S 1 - SUB + 
      ADD 
      'N' 1 STO+
    UNTIL 
      DUP SORT DUP REVLIST ==
    END 
    N SWAP 1 GET 2 →LIST
  »
»
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8384
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: MPO 106 - Distribution de bonbons

Message par badaze »

Schraf a écrit : 04 mars 2022 08:53 @badaze : si dans une liste la plus grande valeur est égale à la plus petite, c'est que tous les éléments de la liste sont égaux, non ?
Tu as raison.
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8384
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: MPO 106 - Distribution de bonbons

Message par badaze »

Schraf a écrit : 04 mars 2022 08:53
Pour le passage du dernier enfant au premier :

1) (k,b) in enumerate(Bo) permet d'obtenir le rang k (0 puis 1 puis...) et la valeur correspondante b dans la liste Bo
2) j'utilise le fait qu'en Python Bo[-1] permet de récupérer le dernier élément de la liste Bo. Donc lorsque k = 0, Bo[k-1]/2 = Bo[-1]/2 est bien la moitié des bonbons du dernier enfant + b/2 (ce que le premier enfant garde)
Merci pour cette explication.
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: MPO 106 - Distribution de bonbons

Message par zpalm »

Schraf a écrit : 04 mars 2022 08:53 2) j'utilise le fait qu'en Python Bo[-1] permet de récupérer le dernier élément de la liste Bo.
Pour la HP Prime j'utilise aussi le fait qu'en PPL Bo(0) adresse le dernier élément de la liste (les listes en PPL commencent à partir de 1 et non de 0 comme en Python).
Répondre

Retourner vers « Tous les Pockets »