MPO 106 - Distribution de bonbons

[C.Ret]

Pour détecter la fin du cycle des "distributions de bonbons", on peut aussi se contenter de comparer la nouvelle répartition avec la précédente. En effet, une fois à équirépartition le vecteur (ou la liste) indiquant la répartition reste inchangée :

[ 1 2 3 4 5 ] → [ 4 2 3 4 5 ] → [ 5 3 3 4 5 ] → [ 6 5 4 4 5 ] → [ 6 6 5 4 5 ] → [ 6 6 6 5 5 ] → [ 6 6 6 6 6 ] → [ 6 6 6 6 6 ] → [ 6 6 6 6 6 ] → ...

Sur un certain système cela peut simplifier considérablement le test de fin Enfin, pour ceux qui utiliserai une boucle de calculs...


J'ai cependant quelques questions :

• Quel est le résultat attendu si l'instituteur donne le même nombre de bonbons à tous les élèves ?
• Quel est le résultat attendu s'il n'y a qu'un seul élève ?
  • Quel est le résultat attendu pour [ 2 ] ?
  • Quel est le résultat attendu pour [ 1 ] ?
  • Quel est le résultat attendu pour [ 0 ] ?
• L'instituteur sait-il distribuer un nombre négatif de bonbons ?
• Arrive-t-il que l'instituteur oublie un élève et ne lui donne initialement aucun bonbon ?
• Le code proposé doit-il tenir compte de ces cas extrêmes pour être valide ? Les codes ne traitant que le cas le plus général sont-ils acceptables ?

Voilà je crois préférable de ne pas trop commencer à coder avant d'avoir bien cerné l'étendue des problèmes à venir...

[badaze]

En ce qui me concerne, je sauvegarde la valeur du premier poste du tableau puis avec une boucle for next je compare les valeurs des autres postes. Si j’ai une différence je mets une variable à 0. Bien entendu, j’initialise la variable à 1 en début de traitement.

[C.Ret]

En ce qui me concerne, je sauvegarde la valeur du premier poste du tableau puis avec une boucle for next je compare les valeurs des autres postes. Si j’ai une différence je mets une variable à 0. Bien entendu, j’initialise la variable à 1 en début de traitement.

Oui , je fais aussi de cette façon mais en utilisant un drapeau. Selon les machines et leur language cela peut être efficace ou nécessaire que la machine en question ne sait pas manipuler de tableau.

[C.Ret]

MPO106({1,2,3,4,5}) retourne [6,6]
MPO106({10,2,8,22,16,4,10,6,15,20}) retourne [12,18]

Bon, j'avance doucement :
2nd CMs 1 A 2 R/S 3 R/S 4 R/S 5 R/S B affiche 6 puis x:t affiche 6 en 0'51"

et

2nd CMs 10 A 2 A 8 A 22 A 16 A 4 A 10 A 6 A 15 A 20 A B affiche 12 et x:t affiche 18 en 2'57"69

Entre les deux dernières versions j'ai gagné 4 octets et un gain de vitesse d'environ x1.3
Le dernier exemple prenait 3'51"

En théorie, je peut calculer pour une ronde de 57 élèves. Mais je n'ose pas essayer, je ne sais pas combien d'heures cela va prendre !!

[Schraf]

@C.Ret. Pour les cas où il n'y a qu'un seul élève, le nombre de tour est 0 et le nombre de bonbons est celui donné par l'instituteur. Il ne faudra pas oublié de prévenir les autorités compétentes par la même occasion, sauf dans le cas où le nombre de bonbons donné est 0.

On va considérer que sur notre planète il n'est pas possible de donner un nombre négatif de bonbons.
La distribution initiale peut être {0,0,0....,0,10}, c'est-à-dire qu'initialement il n'y a qu'un seul élève avec un paquet de bonbons et les autres rien. C'est d'ailleurs un cas intéressant puisque par exemple avec {0,0,0,4} les élèves n'auront à la fin 2 bonbons chacun, alors qu'avec {0,0,0,5} ils en auront 4 chacun.

Si la distribution initiale est déjà bien répartie (par exemple {6,6,6}, le résultat attendu est nb_de_tours = 0 et nb_bonbons_par_eleve = 6)

On voit déjà plusieurs techniques pour tester si tous les éléments d'une liste sont identiques :

- Le + grand terme est égal au plus petit : min(L) = max(L)
- Un "ET" logique, est-ce que tous les termes sont égaux au premier : Produit(L==L(0))
- La liste suivante est-elle identique à la précédente : L == L_Suiv
- Trier la liste par ordre croissant et décroissant et tester si ↑L == ↓L
- Le nombre d'éléments différents de la liste est égal à 1 : taille(union(L)) == 1
- Je proposais aussi de faire la liste des différences entre les termes consécutifs (ΔL), de prendre les valeurs absolues et d'en regarder le max (ou en faire la somme), la liste est constante si max(abs(ΔL)) == 0 (ou somme(abs(ΔL)) == 0)
- On peut rechercher à quelle position dans la liste on a une valeur différente du premier élément. S'il trouve c'est que la liste n'est pas constante.

[C.Ret]

On va considérer que sur notre planète il n'est pas possible de donner un nombre négatif de bonbons.

Je te remercie car sur ma planète il est très facile de donner un nombre négatif de coups de pieds (ce qui nous fait reculer), mais aussi (3+2i) coups de pieds ce qui nous fait avancer de trois pas mais aussi monter de deux étages.

Alors quand je redescend sur Terre, j'ai un peu de mal avec les notions de donner ou prendre, monter ou descendre, droite ou gauche, etc. Sans compter que la dernière fois j'ai fait un bond de √749, ce qui est parfaitement irrationnel.

Mon code est donc conforme et je ne peux le simplifier d'avantage sans prendre le risque qu'il retourne des valeurs erronées dans ces cas extrêmes.

[Schraf]

@C.Ret Regardant actuellement la saison 2 de la série OVNI(s), je ne peux pas t'interdire de proposer des versions plus générales où notre planète ne serait qu'un cas particulier de ce MPO !

[zpalm]

Pour les cas où il n'y a qu'un seul élève, le nombre de tour est 0 et le nombre de bonbons est celui donné par l'instituteur. Il ne faudra pas oublié de prévenir les autorités compétentes par la même occasion, sauf dans le cas où le nombre de bonbons donné est 0.

On va considérer que sur notre planète il n'est pas possible de donner un nombre négatif de bonbons.
La distribution initiale peut être {0,0,0....,0,10}, c'est-à-dire qu'initialement il n'y a qu'un seul élève avec un paquet de bonbons et les autres rien. C'est d'ailleurs un cas intéressant puisque par exemple avec {0,0,0,4} les élèves n'auront à la fin 2 bonbons chacun, alors qu'avec {0,0,0,5} ils en auront 4 chacun.

Si la distribution initiale est déjà bien répartie (par exemple {6,6,6}, le résultat attendu est nb_de_tours = 0 et nb_bonbons_par_eleve = 6)

Merci pour ces précisions, du coup voici une nouvelle version sur HP Prime conforme avec ces cas particuliers:

Code : Tout sélectionner

EXPORT MPO106(Bo)
BEGIN
 LOCAL t;
 WHILE SIZE(UNION(Bo))>1 DO
  t+1▶t; EXECON("&1+&2",CEILING(CONCAT(Bo(0),Bo)/2))▶Bo; 
 END;
 [t,Bo(1)];
END;

SIZE(UNION(Bo))>1 permet de tester à la fois que l'on a plusieurs élèves et qu'ils n'ont pas tous le même nombre de bonbons.

[C.Ret]

Joli !

J'aime bien la structure qu'utilise zpalm dans son WHILE / DO / END qui ne fait plus rien (voir jamais rien) si UNION( Bo ) est un singleton !

Sur mon HP-28S, je ne peux pas utiliser le test d'arrêt qu'utilise Bernouilli92 « ... DUP SORT DUP REVLIST == ... » car pas de SORT ni de REVLIST.
J'utiliserai donc une structure WHILE DUP OVER 1 GET CON OVER == REPEAT ... END pour suivre l'organisation proposée par zpalm et utiliserai sur mon HP-28S un ARRAY et des complexes ainsi, j'obtiendrai à l'écran la même syntaxe que celle utilisé par Eric.

[ 1 2 3 4 5 ] → (6,6)
[ 5 4 3 2 1 ] → (6,6)
[ 2 1 4 3 5 ] → (6,6)
[ 1 3 2 5 4 ] → (6,6)
[ 5 1 4 3 2 ] → (2,4)

[ 60 12 48 36 24 ] → (7,38)

[ 10 2 8 22 16 4 10 6 15 20 ] → (12,18)

[ 6 6 6 ] → (0,6)
[ 0 0 0 ] → (0,0)
[ 0 0 0 4 ] → (4,2)
[ 0 0 5 ] → (5,4)
[ 1 ] → (0,1)
[ 2 ] → (0,2)

[ 4 3 1968 ] → (13,664)
[ 6011 0 1759 0 2 0 789 ] → (70,1260)

Sur une HP-15C, j'utiliserai bien volontiers ses capacité à manipuler des matrices (ou des vecteurs). Par contre, pour vérifier que tous les éléments d'un vecteur sont identiques, il va falloir ruser un peu. Pour le moment mon astuce revient à faire une structure DO / UNTIL /END. mAis je crois que la nuit va me porter conseil

[bernouilli92]

Voici ma version avec un while repeat pour gérer le cas où il n'y a rien à faire:

Code : Tout sélectionner

« 
  DUP SIZE 0 → S N
  «
    WHILE DUP SORT DUP REVLIST ≠
    REPEAT 
      2 / CEIL 
      DUP S GET OVER 1 S 1 - SUB + 
      ADD 
      'N' 1 STO+
    END 
    N SWAP 1 GET 2 →LIST
  »
»

Pas mal l'astuce du CON pour vérifier quand c'est fini.

[badaze]

Version en Basic.
Je n’ai pas cherché à optimiser. J’ai mis un tableau de 8 postes avec remplissage aléatoire. Le portage avec un indice N est très facile tout comme la saisie des données par l’utilisateur. Ca devrait être intéressant de programmer en Basic du FX 880P car avec 99 niveaux de sous programmes on peut faire du récursif.

Code : Tout sélectionner

  10 : GOSUB "INIT"
  20 : GOSUB "CONTROLE"
  30 : GOSUB "AFFICHE"
  40 : "BOUCLE"
  50 : GOSUB "MOITIE"
  60 : GOSUB "ECHANGE"
  70 : GOSUB "CONTROLE"
  80 : GOSUB "AFFICHE"  
  90 : IF OK = 0 THEN "BOUCLE"
  95 : END
 
 100 : "INIT"
 110 : CLEAR
 120 : DIM A(8): DIM B(8) : DIM C(8) : N = 0
 130 : FOR I = 1 TO 8 : A(I) = RND(30) : NEXT I
 140 : RETURN
 
 200 : "MOITIE"
 210 : FOR I=1 TO 8
 220 :   K = A(I) / 2
 230 :   IF K <> INT(K) LET A(I) = A(I) + 1
 240 :   K = A(I) + 1
 250 :   B(I) = K
 260 :   A(I) = A(I) / 2
 270 : NEXT I
 280 : RETURN
 
 300 : "ECHANGE"
 310 : C(1) = A(1) + B(8)
 320 : FOR I=2 TO 8
 330 :   C(I) = A(I) + B(I-1)
 340 : NEXT I
 350 : FOR I=1 TO 8
 360 :   A(I) = C(I)
 370 : NEXT I
 380 : RETURN
 
 400 : "CONTROLE"
 410 : N = N+1
 420 : OK = 1
 420 : T = A(1)
 430 : FOR I = 2 TO 8
 440 :   IF T<>A(I) LET OK = 0
 450 : NEXT I
 460 : RETURN
 
 500 : "AFFICHE":CLS
 510 : A$ = "OK"
 520 : IF OK=0 LET A$ = "OK"
 530 : WAIT 0
 540 : PRINT A$ + " " + STR$(N) + "<"
 550 : FOR I=1 TO 8
 560 :   PRINT STR$(A(AI)) + " ";
 570 : NEXT I
 580 : RETURN

Factorielle en récursif sur FX 850P.

Code : Tout sélectionner

 10 INPUT "A=",A
 20 B = 1
 30 GOSUB 1000
 40 PRINT "......";B;
 50 END
 999 REM *** FACTORIELLE
 1000 IF A = 0 THEN RETURN
 1010 B = B * A
 1020 A = A - 1
 1030 GOSUB 1000
 1040 RETURN

[Marge]

[...]
Pas mal l'astuce du CON pour vérifier quand c'est fini.

C'est vrai qu'en général on n'y pense pas. On devrait !



Désolé... pas pu m'empêcher.

[C.Ret]

Pas mal l'astuce du CON pour vérifier quand c'est fini.

En fait pas le choix sur HP-28S, le RPL est assez pénible et limité avec les matrices ou vecteurs.
C'est comme la séquence 2 / CEIL, elle ne fonctionne pas avec les matrices ou vecteurs. Il faut utiliser une séquence équivalente 2 / RND en utilisant le mode d'affichage 0 FIX.

USAGE : CEIL IP FLOOR FP
1: Real Number
1: Algebraic or Name

USAGE: RND
1: Real Number
1: Complex Number
1: Array
1: Algebraic or Name

Ce qui donne le code suivant:

Code : Tout sélectionner

MPO106:
« 0 FIX 0 SWAP                                 // initialise format d'affichage et compteur c=0
  WHILE
    DUP OVER 1 GET CON OVER ≠                  // Tant que pas [ r r r ... r ]
  REPEAT
    1 ROT +                                        // Incrémente compteur
    SWAP 2 / RND                                  // Effectue division par deux avec  arrondi supérieur (CEIL)
    DUP ARRY→ 1 GET → n « n ROLLD n →ARRY » +    // Distribue chaque moitié de bonbons à droite
  END
  1 GET R→C STD »                             //  Récupère la valeur finale r et format affichage libre (c,r)

Usage:
Entrer la distribution sous forme d'un vecteur simple :
[ 5 1 4 3 2 ] (MPO106) affiche 1: (2,4)

Mécanisme:
[ 5 1 4 3 2 ] → (1) [ 3. 1. 2. 2. 1. ] + [ 1. 3. 1. 2. 2. ] = [ 4. 4. 3. 4. 3. ] → (2) [ 2. 2. 2. 2. 2. ] + [ 2. 2. 2. 2. 2. ] = [ 4. 4. 4. 4. 4. ] → ( 2 , 4 )

Version en Basic.
Je n’ai pas cherché à optimiser. J’ai mis un tableau de 8 postes avec remplissage aléatoire. Le portage avec un indice N est très facile tout comme la saisie des données par l’utilisateur. Ca devrait être intéressant de programmer en Basic du FX 880P car avec 99 niveaux de sous programmes on peut faire du récursif.

J'aime bien cette façon de faire. Commencer naturellement sans chercher la petite bête, juste avoir un code clair et fonctionnel.
Je vais m'inspirer de cette version et voir si cela passe sur mon SHARP PC-1211 et ses quatre niveaux maximum d'appels.

[dprtl]

Voici ma première version en C61-Basic (pour Casio PB1000, FX850P, etc.). Il suffit d'éditer la première ligne pour donner le vecteur en entrée :

Code : Tout sélectionner

10 DATA 6011,0,1759,0,2,0,789
20 CLEAR
30 READ T:ON ERROR GOTO 50
40 L=L+1:GOTO 30
50 L=L-1:DIM A(L):DIM B(L):RESTORE
60 FOR I=0 TO L:READ A(I):NEXT
70 FOR I=0 TO L:PRINT A(I);:NEXT: PRINT
80 FOR I=1 TO L:IF A(I)<>A(0) THEN 100
90 NEXT: PRINT N;A(0):END
100 N=N+1:FOR I=0 TO L
110 J=I-1:IF J<0 THEN J=L
120 T=A(J):T=T+T MOD 2:B(J)=T/2:NEXT
130 FOR I=0 TO L:J=I-1:IF J<0 THEN J=L
140 A(I)=B(J)+B(I):NEXT
150 GOTO 70

Cette version affiche les résultats intermédiaires. Il n'y a rien de très original, mais c'est un programme relativement lisible et rapide à mettre en œuvre. La difficulté et le temps de programmation sont réduits (contexte calculette des années 80-90).

[Schraf]

Version pour les TI-82, 83, 84... mais pas TI-80 qui ne connaissait pas encore le While

Code : Tout sélectionner

PROGRAM:BONBON
Input L₁
0→T
While min(L₁)≠max(L₁		// Tant que tous les éléments ne sont pas identiques
ent(.5+.5L₁→L₁				// Ce qui revient à faire CEIL sur chaque élément
augmenter({L₁(dim(L₁))},L₁→L₂		// Copie dernier élément en 1ere position
dim(L₁→dim(L₂				// On redimensionne la nouvelle liste à la taille de l'ancienne (càd dernier élément est supprimé)
L₁+L₂→L₁				// Nouvelle liste
1+T→T
End
Disp T,L₁(1

Version TI

bonbons.png (9.55 Kio) Vu 3913 fois