Misez p'tit Optimisez en version APL

Vous ne possédez pas l'original ? Découvrez la machine via l'émulation !

Modérateur : Politburo

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

Misez P'tit, Optimisez - N°23 (Nombres consécutifs)

Message par Schraf »

Merci à @C.Ret pour sa belle présentation !

On peut encore programmer sur plusieurs lignes numérotées, en commençant et finissant par le symbole ∇, mais pas sur Try APL. Ca permet de faire des GOTO vers des n°, des INPUT, IF, ajouter des commentaires etc. Mais pour la rubrique MPO, le modèle "One-liner program" s'impose !

HP 2641A
HP 2641A
apl.jpg (82.49 Kio) Vu 12867 fois

Enoncé de l'exercice : http://www.silicium.org/forum/viewtopic ... 46&t=33931
- on entre trois nombres entiers a, b et c dans la bécane
- le pocket retourne vrai ou faux (ou 1 ou 0 si ça vous arrange, ou tout autre codage qui vous plaît), si les nombres sont strictement consécutifs, donc si b = a + 1 et c = b + 1
En APL, on fait des réductions en utilisant le symbole /, par exemple : +/ 1 2 3 4 -> 10
Mais on peut également ajouter un nombre devant : 2+/ 1 2 3 4 -> 3 5 7. La réduction se fait ici 2 par 2 (1+2=3 puis 2+3=5 etc.). On peut alors tester :

Code : Tout sélectionner

2-/ 1 2 3 4
¯1 ¯1 ¯1
qui correspond bien à 1-2=-1 puis 2-3=-1 et 3-4=-1. Pour inverser le calcul, il suffit de mettre -2 :

Code : Tout sélectionner

¯2-/ 1 2 3 4
1 1 1
Pour notre exercice, il faut tester s'il n'y a que des 1, pour cela on compare tous les éléments avec 1 et on assemble les 3 résultats avec un ET logique ^ :

Code : Tout sélectionner

^/1=¯2-/ 2 3 4
1
Ce qui donne la fonction :

Code : Tout sélectionner

inc←{^/1=¯2-/⍵}
      inc 17 18 19
1
      inc 17 20 21
0
Et en version classique :
APL Classique
APL Classique
INC.jpg (12.39 Kio) Vu 12867 fois
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

M.P.O. n°67 : Les nombres de Hamming

Message par Schraf »

Enoncé de l'exercice http://www.silicium.org/forum/viewtopic ... 46&t=39472
Les 20 premiers Nombre de Hamming sont : 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
Ceux sont les nombres dont les seuls diviseurs premiers sont 2,3 ou 5.
Voici une proposition (100 est un nombre de Hamming, 104 non) :

Code : Tout sélectionner

ham←{~3∊1↓+⌿0≠2 3 5∘.|∪⍵∨⍳⍵}
      ham 100
1
      ham 104
0
      (ham¨⍳50)/⍳50
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50
Explications

Le GCD (ou PGDC en français) de 2 nombres se calcule avec le symbole ∨ :

Code : Tout sélectionner

      10∨24
2
      10 ∨ ⍳10
1 2 1 2 5 2 1 2 1 10
La seconde ligne nous dit que : PGCD(10,1)=1, PGCD(10,2)=2, PGCD(10,3)=1... PGCD(10,10)=10
Donc en utilisant la réunion, on a tous les diviseurs d'un nombre :

Code : Tout sélectionner

      ∪104 ∨ ⍳104
1 2 4 8 13 26 52 104
Si le nombre est de Hamming, tous ces diviseurs doivent être divisibles par 2, 3 ou 5 uniquement. Calculons tous les restes en utilisant modulo | :

Code : Tout sélectionner

      {2 3 5∘.|∪⍵∨⍳⍵}104
1 0 0 0 1 0 0 0
1 2 1 2 1 2 1 2
1 2 4 3 3 1 2 4
Première ligne : tous les restes des divisions par 2 des diviseurs de 104
Idem pour les divisions par 3 puis 5.
Si dans une colonne il n'y a aucun 0, le nombre n'est pas de Hamming. C'est le cas ici, la 5e colonne contient 1-1-3 et cela correspond au diviseur 13.
On va donc compter le nombre d'éléments différents de 0 dans chaque colonne :

Code : Tout sélectionner

{+⌿0≠2 3 5∘.|∪⍵∨⍳⍵}104
3 2 2 2 3 2 2 2
Il est temps de virer le premier élément (il y aura forcément toujours un 3) et de regarder s'il reste encore un 3 quelque part :

Code : Tout sélectionner

      {3∊1↓+⌿0≠2 3 5∘.|∪⍵∨⍳⍵}104
1
      {3∊1↓+⌿0≠2 3 5∘.|∪⍵∨⍳⍵}100
0
Et on prend la négation du résultat en utilisant ~.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez en version APL

Message par gege »

Bonjour,
Aaaaah je retrouve l'APL que j'ai connu dans la version "classique".
Tu n'as pas besoin des deux caractères de gauche ligne [1] dans INC, je crois ?
Les lignes étaient numérotées de 1 en 1 et pour insérer par exemple entre la ligne [1] et la ligne [2] ou pouvait taper :
[1.25] P<-+/R
Et ça renumérotait !
Aaaaah cool
G.E.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: N°72: Chiffrement par transposition par dprtl- Chiffrement d'un nombre.

Message par dprtl »

Schraf a écrit : 26 mai 2020 10:20 L'énoncé complet : http://www.silicium.org/forum/viewtopic ... 46&t=40279
Merci ! J'en ai profité pour corriger le lien postimg.cc vers mon image d'illustration.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Misez p'tit Optimisez n°57 : palindromes

Message par Schraf »

Enoncé de l'exercice : http://www.silicium.org/forum/viewtopic ... 46&t=37350
En partant d’un nombre entier par exemple: 78 on l’écrit à l’envers: 87 et on additionne: 78 + 87 = 165
Puis on recommence :
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884
Pour faire plaisir à @Gege (en fait je suis incapable de résoudre ce problème en une seule ligne !!), je vous propose une version en APL classique :
Palindrome
Palindrome
palidrome.jpg (82.63 Kio) Vu 12816 fois

Code : Tout sélectionner

      INC
Votre chaine
89
Iterations : 24
Palindrome 8 8 1 3 2 0 0 0 2 3 1 8 8

      INC
Votre chaine
1186060307891929990
Iterations : 261
Palindrome 4 4 5 6 2 6 6 5 8 7 8 9 7 6 4 3 7 6 2 2 4 3 7 8 4 8 9 7 6 6 5 3 8 7
      0 3 8 8 8 8 4 7 8 3 6 6 2 5 9 8 4 2 5 8 5 5 9 6 3 4 3 6 9 5 5 8 5 2 4 8 9
      5 2 6 6 3 8 7 4 8 8 8 8 3 0 7 8 3 5 6 6 7 9 8 4 8 7 3 4 2 2 6 7 3 4 6 7 9
      8 7 8 5 6 6 2 6 5 4 4
Pour "répondre" à la question :
Mais certains nombres résistent et ne semblent pas générer de palindrome: les nombres de Lychrel… trouvez le premier d’entre eux (le plus petit).
On peut modifier le programme de la façon suivante (au passage j'utilise des étiquettes au lieu des numéros de pas) :
196
196
196.jpg (43.08 Kio) Vu 12815 fois

Code : Tout sélectionner

INC
1 Iterations :  1
2 Iterations :  1
3 Iterations :  1
4 Iterations :  1
...
193 Iterations :  8
194 Iterations :  3
195 Iterations :  4
INTERRUPT
INC[5]RETENUES:N←(0,10|N)+(N≥10),0
On stoppe le programme pour 196 qui semble tourner indéfiniment (plus précisément, je l'ai laissé une 15aine de secondes et le nombre N avait déjà 27343 chiffres !)
Wikipédia : La liste des premiers nombres de Lychrel candidats sont : 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1 495, 1 497, 1 585, 1 587, 1 675, 1 677, 1 765, 1 767, 1 855, 1 857, 1 945, 1 947, 1 997…
De plus @zpalm nous dit :
NB: les nombres de moins de 20 digits qui génèrent un palindrome le font en 261 itérations maximum.
On peut alors modifier à nouveau légèrement le programme pour qu'il affiche uniquement ceux qui ne donnent pas de palindromes après 261 itérations :

Code : Tout sélectionner

 INC;S;N;C;I
 I←1
SUITE:C←0
 N←⍎¨⍕I
ADD:N←N+⌽N
RETENUES:N←(0,10|N)+(N≥10),0
 N←(⊃N=0)↓N
 →RETENUES×⍳∨/N≥10
 C←C+1
 →PASS×⍳C>261
 →ADD×⍳∨/N≠⌽N
 →SUIV
PASS:⎕←'Candidat : ',I
SUIV:I←I+1
 →SUITE

Code : Tout sélectionner

INC
Candidat :  196
Candidat :  295
Candidat :  394
Candidat :  493
Candidat :  592
Candidat :  689
Candidat :  691
Candidat :  788
Candidat :  790
Candidat :  879
Candidat :  887
Candidat :  978
Candidat :  986
Candidat :  1495
Candidat :  1497
Candidat :  1585
Candidat :  1587
Candidat :  1675
...
Candidat :  23704
Candidat :  23715
Candidat :  23717
Candidat :  23752
Candidat :  23754
...
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Misez P'tit, Optimisez - N°34 (Tout à 1 Euro!)

Message par Schraf »

Enoncé de l'exercice : http://www.silicium.org/forum/viewtopic ... 5&start=15
Combien y a t'il de façons différentes d'obtenir 1€ en utilisant les différentes pièces existantes: 1c, 2c, 5c, 10c, 20c, 50c et 1€ ?
L'algorithme de @Gilles59 étant vraiment sympa, voici une version (légèrement simplifiée) en APL :

Code : Tout sélectionner

mpo←{(⍺≤0)∨⍵<1:⍺=0 ⋄ (⍺∇ ⍵-1)+(⍺-⍵⊃100 50 20 10 5 2 1)∇ ⍵}
      100 mpo 7
4563
Autre idée, créer une matrice multi-dimensionnelle avec toutes les combinaisons possibles : Ci-dessous le premier 0 0 0 signifie ne prendre ni le 50, ni le 20, ni le 10. Le second terme 0 0 1 signifie prendre juste 10 et par exemple 2 5 10 pour prendre 2*50, 5*20 et 10*10

Code : Tout sélectionner

     100 {¯1+⍳⌊1+⍺÷r←⍵} 50 20 10
 0 0 0  0 0 1  0 0 2  0 0 3  0 0 4  0 0 5  0 0 6  0 0 7  0 0 8  0 0 9  0 0 10 
 0 1 0  0 1 1  0 1 2  0 1 3  0 1 4  0 1 5  0 1 6  0 1 7  0 1 8  0 1 9  0 1 10 
 0 2 0  0 2 1  0 2 2  0 2 3  0 2 4  0 2 5  0 2 6  0 2 7  0 2 8  0 2 9  0 2 10 
 0 3 0  0 3 1  0 3 2  0 3 3  0 3 4  0 3 5  0 3 6  0 3 7  0 3 8  0 3 9  0 3 10 
 0 4 0  0 4 1  0 4 2  0 4 3  0 4 4  0 4 5  0 4 6  0 4 7  0 4 8  0 4 9  0 4 10 
 0 5 0  0 5 1  0 5 2  0 5 3  0 5 4  0 5 5  0 5 6  0 5 7  0 5 8  0 5 9  0 5 10 
                                                                              
 1 0 0  1 0 1  1 0 2  1 0 3  1 0 4  1 0 5  1 0 6  1 0 7  1 0 8  1 0 9  1 0 10 
 1 1 0  1 1 1  1 1 2  1 1 3  1 1 4  1 1 5  1 1 6  1 1 7  1 1 8  1 1 9  1 1 10 
 1 2 0  1 2 1  1 2 2  1 2 3  1 2 4  1 2 5  1 2 6  1 2 7  1 2 8  1 2 9  1 2 10 
 1 3 0  1 3 1  1 3 2  1 3 3  1 3 4  1 3 5  1 3 6  1 3 7  1 3 8  1 3 9  1 3 10 
 1 4 0  1 4 1  1 4 2  1 4 3  1 4 4  1 4 5  1 4 6  1 4 7  1 4 8  1 4 9  1 4 10 
 1 5 0  1 5 1  1 5 2  1 5 3  1 5 4  1 5 5  1 5 6  1 5 7  1 5 8  1 5 9  1 5 10 
                                                                              
 2 0 0  2 0 1  2 0 2  2 0 3  2 0 4  2 0 5  2 0 6  2 0 7  2 0 8  2 0 9  2 0 10 
 2 1 0  2 1 1  2 1 2  2 1 3  2 1 4  2 1 5  2 1 6  2 1 7  2 1 8  2 1 9  2 1 10 
 2 2 0  2 2 1  2 2 2  2 2 3  2 2 4  2 2 5  2 2 6  2 2 7  2 2 8  2 2 9  2 2 10 
 2 3 0  2 3 1  2 3 2  2 3 3  2 3 4  2 3 5  2 3 6  2 3 7  2 3 8  2 3 9  2 3 10 
 2 4 0  2 4 1  2 4 2  2 4 3  2 4 4  2 4 5  2 4 6  2 4 7  2 4 8  2 4 9  2 4 10 
 2 5 0  2 5 1  2 5 2  2 5 3  2 5 4  2 5 5  2 5 6  2 5 7  2 5 8  2 5 9  2 5 10
Ensuite on calcule les montants dans chaque case (produit scalaire), par exemple 50 20 10 +.× 2 5 10 = 100 + 100 + 100 = 300

Code : Tout sélectionner

     100 {{r+.×⍵}¨¯1+⍳⌊1+⍺÷r←⍵}50 20 10
  0  10  20  30  40  50  60  70  80  90 100
 20  30  40  50  60  70  80  90 100 110 120
 40  50  60  70  80  90 100 110 120 130 140
 60  70  80  90 100 110 120 130 140 150 160
 80  90 100 110 120 130 140 150 160 170 180
100 110 120 130 140 150 160 170 180 190 200
                                           
 50  60  70  80  90 100 110 120 130 140 150
 70  80  90 100 110 120 130 140 150 160 170
 90 100 110 120 130 140 150 160 170 180 190
110 120 130 140 150 160 170 180 190 200 210
130 140 150 160 170 180 190 200 210 220 230
150 160 170 180 190 200 210 220 230 240 250
                                           
100 110 120 130 140 150 160 170 180 190 200
120 130 140 150 160 170 180 190 200 210 220
140 150 160 170 180 190 200 210 220 230 240
160 170 180 190 200 210 220 230 240 250 260
180 190 200 210 220 230 240 250 260 270 280
200 210 220 230 240 250 260 270 280 290 300
Et il suffit de compter combien sont égaux à 100 :

Code : Tout sélectionner

     100 {+/,⍺={r+.×⍵}¨¯1+⍳⌊1+⍺÷r←⍵}50 20 10
10
Ça c'est la théorie puisqu'en pratique on dépasse les capacités du logiciel...

Code : Tout sélectionner

     100 {+/,⍺={r+.×⍵}¨¯1+⍳⌊1+⍺÷r←⍵}50 20 10 5 2
196    ⍝ Ca passe avec 5 pièces
     100 {+/,⍺={r+.×⍵}¨¯1+⍳⌊1+⍺÷r←⍵}50 20 10 5 2 1
WS FULL  ⍝ Oups !
Mais comme l'algo passe avec 5 pièces, on peut compter le nombre de façons d'obtenir 100 centimes, 99c, 98c...,0c avec ces 5 pièces, le reste étant en pièces de 1c. Il faut donc faire la somme de ce que l'on obtient avec l'algorithme pour tous les nombres entre 0 et 100 :

Code : Tout sélectionner

algo←{+/⍺=,{r+.×⍵}¨¯1+⍳⌊1+⍺÷r←⍵}
     +/{⍵ algo p}¨0,⍳100 
4562
Je ne comprends pas d'où vient la différence avec 4563... mais on n'est pas loin du compte :oops:
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Misez p'tit Optimisez n°90 : Bibi or not Bibi

Message par Schraf »

Enoncé de l'exercice : http://www.silicium.org/forum/viewtopic ... 46&t=44253
En Bibi on ne dit plus « cent dix-neuf plus cent trente-sept égale deux cent cinquante-six » mais plus poétiquement « bibi plus koka égale hahoho ».
Voici une version qui utilise doublement les conversions de bases d'APL :

Code : Tout sélectionner

      bibi←{,/(⍉1+4 4⊤16⊥(⍣¯1)⍵),.⊃'HBKD' 'OAEI'}¨
      bibi 119 137 256
┌──────┬──────┬────────┐
│┌────┐│┌────┐│┌──────┐│
││BIBI│││KOKA│││HAHOHO││
│└────┘│└────┘│└──────┘│
└──────┴──────┴────────┘
Version alternative plus courte :

Code : Tout sélectionner

      bibi←{,/(,'HBKD'∘.,'OAEI')[1+16⊥(⍣¯1)⍵]}¨
Explications
On convertit le nombre en base 16 :

Code : Tout sélectionner

      16⊥(⍣¯1)137
8 9
Ensuite chaque chiffre est converti en base 4 sur 2 chiffres (8 = 2 0 en base 4 et 9 = 2 1) :

Code : Tout sélectionner

      4 4 ⊤ 8 9
2 2
0 1
On ajoute 1 (pour avoir la position dans la chaine) et on transpose la matrice :

Code : Tout sélectionner

     ⍉1+ 4 4 ⊤ 8 9
3 1
3 2
Reste plus qu'à aller prendre ⊃ les éléments dans les 2 chaines 'HBKD' et 'OAEI' et faire la concaténation (,) des 2 caractères.

Code : Tout sélectionner

      (⍉1+4 4⊤8 9),.⊃'HBKD' 'OAEI'
 KO  KA 
Puis concaténation de l'ensemble avec ,/. Le ¨ après l'accolade est pour pouvoir appliquer la fonction à une liste de nombres.

Code : Tout sélectionner

      bibi ⍳15  ⍝ bibi 1, bibi 2 ... bibi 15 mais pb avec bibi 0
  HA  HE  HI  BO  BA  BE  BI  KO  KA  KE  KI  DO  DA  DE  DI 
      bibi 584623705671
  KOKOHADEBOKADODEBOBI   
Pour la version alternative

Code : Tout sélectionner

      'HBKD'∘.,'OAEI'
 HO  HA  HE  HI 
 BO  BA  BE  BI 
 KO  KA  KE  KI 
 DO  DA  DE  DI 
Donc c'est presque fini, il suffit de le mettre en ligne et de récupérer les substitutions des nombres de 0 (HO) à 15 (DI)

Mais toutes ces versions ne suivent pas la consigne qui était de ne pas utiliser les fonctions de changements de base ! :roll:
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Misez p'tit Optimisez n°84 : la comète de Goldbach

Message par Schraf »

Enoncé de l'exercice : http://www.silicium.org/forum/viewtopic ... 46&t=43183

Version brutale

Goldbach
Goldbach
Goldbach.jpg (31.92 Kio) Vu 12764 fois

Code : Tout sélectionner

]OUTPUT.Plot -type=Dial GOLD 2000
Graph1
Graph1
Graph1.jpg (102.87 Kio) Vu 12764 fois

Code : Tout sélectionner

 ]OUTPUT.Plot -type=Scatter GOLD 2000
Graph2
Graph2
Graph2.jpg (58.15 Kio) Vu 12764 fois
Explications

On génère la table d'addition des nombres premiers inférieurs à N (ci-dessous N=20) : 2+2=4, 2+3=5, 2+7=9...

Code : Tout sélectionner

      {p∘.+p←(~r∊r∘.×r)/r←1↓⍳⍵}20
 4  5  7  9 13 15 19 21
 5  6  8 10 14 16 20 22
 7  8 10 12 16 18 22 24
 9 10 12 14 18 20 24 26
13 14 16 18 22 24 28 30
15 16 18 20 24 26 30 32
19 20 22 24 28 30 34 36
21 22 24 26 30 32 36 38
On compte alors combien sont égaux à 2, 4... en divisant le résultat par 2 (car la matrice est symétrique) et on les ajoute dans un vecteur pour la représentation graphique finale.

Code : Tout sélectionner

Y←Y,⌈(I+.=∘,P)÷2
Version légèrement optimisée

On cherche la liste P des nombres premiers jusqu'à N. Pour chaque entier pair I entre 2 et N, on regarde combien vérifient (I-P)∊P ce qui signifie que I est la somme de 2 nombres premiers.

Code : Tout sélectionner

 G←GOLD N;P;I;Y;X
 P←{p←(~r∊r∘.×r)/r←1↓⍳⍵}N
 X←I←2
 Y←0
LOOP:Y←Y,(⌈+/(I-P)∊P)÷2
 X←X,I←I+2
 →LOOP×⍳I≤N
 G←(2×Y)X
Graph3
Graph3
Graph3.jpg (62.54 Kio) Vu 12757 fois
Version 3
Cette fois on ne cherche plus la liste complète des nombres premiers mais on vérifie à chaque tour de boucle si P est premier et si I - P est également premier (donc 2 calculs). On n'est donc encore assez loin d'arriver à l'optimisation de @zpalm qui lui fait l'inverse en cumulant les nombres premiers petit à petit dans une liste ce qui permet de savoir quels nombres pairs on peut atteindre.
T←{2<+/0=(⍳⍵)|⍵} permet de savoir si un nombre est composé (donc s'il y a plus de 2 diviseurs)

Code : Tout sélectionner

 G←GOLD N;P;I;Y;X;T;J
 T←{2<+/0=(⍳⍵)|⍵}
 J←⌊N÷2
 X←I←2
 Y←J⍴0
LBL1:P←2
LBL2:→LBL3×⍳(T P)  ⍝ Si P est composé on passe au suivant
 →LBL3×⍳P≥I   ⍝ Si P est supérieur à I on passe au suivant
 →LBL3×⍳(T I-P) ⍝ Si I-P est composé on passe au suivant
 J←I÷2
 Y[J]←Y[J]+1
LBL3:P←P+1
 →LBL2×⍳(P≤I÷2)
 X←X,I←I+2
 →LBL1×⍳(I≤N)
 G←(Y)X
Graph4
Graph4
Graph4.jpg (71.88 Kio) Vu 12757 fois
Version 4 (traduction de l'algoritme de @zpalm)

Code : Tout sélectionner

 G←GOLD N;P;I;Y;X;T;J;L
 T←{2<+/0=(⍳⍵)|⍵}
 X←⍳N
 Y←N⍴0
 L←⍬  ⍝ Liste vide
LBL1:P←3
LBL2:→LBL3×⍳(T P)
 L←L,P
 J←(J≤N)/J←(P+L)÷2  ⍝ On ne garde que les sommes de 2 nombres premiers qui sont ≤N
 Y[J]←Y[J]+1  ⍝ Incrémentation de ces valeurs
LBL3:P←P+2
 →LBL2×⍳(P≤2×N)
 G←(N↑Y)X  ⍝ N premières valeur du vecteur Y

Code : Tout sélectionner

]OUTPUT.Plot -type=Scatter GOLD 10000
Graph5
Graph5
Graph5.jpg (79.96 Kio) Vu 12756 fois
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Vidéo : MCM/70 running a game of Horse in APL

Message par Schraf »

Vidéos sympas (à passer à la vitesse x2 quand même !) :

1 minute pour réaliser 255 divisions : https://youtu.be/AaQdzKnOxJE

Code : Tout sélectionner

0.7÷⍳255
0.7 0.35 0.2333333333 0.175 0.14 0.1166666667 0.1 0.0875 0.07777777778 0.07 0.06363636364
      0.05833333333 0.05384615385 0.05...
Course de chiffres : https://youtu.be/YitUfJySYz4

En savoir plus sur le MCM/70 : https://fr.qwe.wiki/wiki/MCM/70
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Misez p'tit, optimisez n°62: Les boules

Message par Schraf »

Enoncé de l'exercice : http://www.silicium.org/forum/viewtopic ... 46&t=39063

Quand on regarde les réponses, plusieurs sont partis sur des simulations de lois plutôt que sur la simulation d'un tirage de boules. Effectivement, s'il y a N boules Noires et B boules Blanches, les probabilités d'obtenir à l'étape suivante une boule N ou R sont respectivement N / (N+R) et R / (N+R). On peut alors simuler une loi de Bernoulli (pile ou face) ayant une probabilité de succès p = N / (N+R). C'est ce que l'on retrouve par exemple dans le programme de @caloubugs :

Code : Tout sélectionner

IF RANDOM<A/(A+B) THEN A+1►A ELSE B+1►B END;
Mais dans ce cas là il y a déjà eu une analyse de l'expérience et finalement il faut s'y connaitre en probas ! Une autre solution est de modéliser l'expérience sans a priori (c'est-à-dire ici répéter X fois "tirer une des boules et ajouter une nouvelle boule de la même couleur"). On aura ainsi un résultat à cette expérience (par exemple NBNNBNNBNN si X=8), ces résultats pouvant être très différents les uns des autres. Quand vous lancez une pièce équilibrée 10 fois, il est possible d'obtenir PPP...P 10 fois et la fois suivante FFF..F 10 fois mais en répétant cette même expérience "lancer 10 fois une pièce", la loi des grands nombres nous dit qu'en moyenne vous aurez autant de Pile que de Face.

C'est la remarque de @badaze qui met le doigt sur la distinction entre simuler un vrai tirage (on doit donc mémoriser toutes les boules) et la simulation d'une loi. Il constate également les écarts qu'il peut y avoir d'une expérience à l'autre mais oublie que c'est la loi des grands nombres qui nous permet malgré tout de donner une réponse sur le long terme :
En fait je ne comprends pas vos solutions. Pour pouvoir simuler un sac contenant des billes il faut qu'à chaque tirage on puisse tirer une boule blanche ou noire. Donc la structure qui les contient doit les contenir de manière unitaire. Comme ce serait le cas avec un vrai sac.
Or de ce que je comprends, vous vous basez tous sur des probabilités alors que d'un tirage à l'autre il peut y avoir de sacrés écarts.
Or dans cet exercice, il n'est pas évident de savoir quelles proportions de N et de B il y aura en moyenne, en ayant répété des centaines de fois l'expérience.

Voici un code APL pour simuler un "vrai" tirage de boules

Code : Tout sélectionner

tirage←{+/(⍳2)∘.=({⍵,⍵[?⍴⍵]}⍣⍵)⍳2}
tirage 10
5 7
Ce qui signifie qu'en partant de 2 boules 1 2 (1 représente Noir et 2 Blanc) et en ajoutant 10 fois une boule avec les règles de l'exercice, on est arrivé à 5 boules Noires et 7 boules Blanches. Explication du code :

Code : Tout sélectionner

      u←1 2   ⍝ Au démarrage, 1 N et 1 B
      ?⍴u     ⍝ Choisir un nombre entre 1 et la taille de u
1             ⍝ il a choisi 1
      u[?⍴u]  ⍝ Quelle est la valeur de u qui est à la position ?⍴u =1
1
      u←u,u[?⍴u]  ⍝ Ajouter à u une boule identique
      u
1 2 1   ⍝ il y a maintenant 2 boules N et 1 boule B
      u←u,u[?⍴u] ⍝ On recommence
      u
1 2 1 2  
      u←u,u[?⍴u]
      u
1 2 1 2 1
      u←u,u[?⍴u]
      u
1 2 1 2 1 1
En sachant que ⍣ permet d'appliquer un même processus (fonction) plusieurs fois :

Code : Tout sélectionner

      {({⍵,⍵[?⍴⍵]}⍣⍵)⍳2} 10
1 2 2 2 2 2 2 2 1 2 1 1
signifie partir ⍳2 = 1 2 et répéter 10 fois "tirer une boule dans le sac et en ajouter une de la même couleur".
Il reste à compter le nombre de N et de B et on obtient le code {+/(⍳2)∘.=({⍵,⍵[?⍴⍵]}⍣⍵)⍳2} puisque :

Code : Tout sélectionner

      {(⍳2)∘.=({⍵,⍵[?⍴⍵]}⍣⍵)⍳2} 10
1 0 0 1 1 1 1 1 0 1 1 1
0 1 1 0 0 0 0 0 1 0 0 0
permet sur la 1ere ligne de compter le nombre de 1 et sur la seconde ligne le nombre de 2.

Cela répond à l'exercice qui était d'afficher le résultat d'une expérience, par exemple :

Code : Tout sélectionner

      tirage 1000
88 914   ⍝ A la fin de l'expérience il y avait 88 boules N et 914 boules B
      tirage 1000
370 632  ⍝ A la fin de l'expérience il y avait 370 boules N et 632 boules B
Mais cela ne nous dit pas combien, en moyenne, il y a de boules N et R dans le sac si on répète cette expérience de nombreuses fois (je passe sous silence la notion d'intervalle de confiance (voir message de @caloubugs)).

Code : Tout sélectionner

 simul←{(÷+/r)×r←⊃+/tirage¨⍺⍴⍵}
       200 simul 100
0.4778431373 0.5221568627
Ce programme répète 200 fois l'expérience où l'on décide d'ajouter 100 boules avec les règles de l'exercice. On obtient alors en moyenne 47,8% de boules N et 52,2% de boules B.

Code : Tout sélectionner

      1000 simul 1000
0.4918493014 0.5081506986
Répéter 1000 fois l'expérience en ajoutant 1000 boules, la proportion de N et B s'équilibre.

En modifiant légèrement simul, on peut représenter le % de Noires dans le sac en répétant 1, 2, ... 1000 fois l'expérience (qui consiste elle-même à ajouter 1000 boules)

Code : Tout sélectionner

simul←{{⊃⍵÷+/⍵}¨+\tirage¨⍺⍴⍵}
]OUTPUT.Plot -type=Line 1000 simul 1000
Boules noires
Boules noires
Noires.jpg (18.3 Kio) Vu 12725 fois

Remarque après discussion avec @C.Ret :

En analysant l'épreuve, on constate que cela revient à choisir aléatoirement un nombre de boules (entre 0 et N) d'une certaine couleur et à compléter le sac par des boules de l'autre couleur. Par exemple, si N=10 et en partant toujours d'une boule N et B, on choisira par exemple 7 boules Noires (et donc 10 - 7 = 3 boules blanches) pour arriver à l'événement "8 N et 4 B".

Dans ce cas les calculs sont immédiats (mais on ne voit plus l'évolution du contenu du sac pour arriver au résultat) :

Code : Tout sélectionner

      simul←{(⍵ + 2 - B), B← ?⍵+1}   ⍝ Nb aléatoire de Blanc entre 1 et ⍵+1 et complément ⍵+2-r pour les Noires
      simul 0
1 1
      simul 100
38 64
      simul 10000
2715 7287
Modifié en dernier par Schraf le 02 juin 2020 10:37, modifié 4 fois.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez en version APL

Message par gege »

Bonjour,
Oui mais il y a un problème dans le tirage aléatoire, le générateur est souvent imparfait.
Et combien de tirages faut-il pour avoir 4 décimales exactes ? Un milliard ? Mille milliards ?
Pour le savoir il faut modéliser par la loi...
Cercle vicieux...
Ça me rappelle le dogme des constructivistes.
On peut aller très (trop ?) loin.
Intéressant...
G.E.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Oui c'est pour ça que j'ai mis "vrai tirage" avec des guillemets, nos ordis sont bien loin d'être parfaits le domaine du hasard :cry:

Et utiliser rand() < N / (N+R) ou une loi uniforme sur {1,2,... N+R} c'est toujours utiliser un générateur pseudo-aléatoire.

J'avais tenté quelques explications :

- entre réalité et mathématiques : https://youtu.be/_73GVGDqgvQ
- les nombres aléatoires dans les calculatrices : https://youtu.be/O0PFO_adLns

D'ailleurs, ce serait amusant de rassembler des codes de générateurs de nombres aléatoires pour des machines (comme la Ti57) qui n'en avaient pas, certains ne sont pas très performants statistiquement mais nettement suffisants pour des jeux. J'en cite 2 dans la vidéo sur les calculatrices :

Tiré de la revue l'ordinateur de poche (en 4 pas seulement)

Code : Tout sélectionner

0.123456789 STO 1 (la graine)

RCL 1
2nd INV LOG (donc 10^ la valeur qui est en mémoire 1)
2nd INV Int (partie fractionnaire)
STO 1 (pour la prochaine étape)
En APL ça pourrait donner un truc comme :

Code : Tout sélectionner

      s←0.123456789{⍺{(1|10*⊢)(⍣⍵)⍺}¨⍳⍵}10000
      ]OUTPUT.Plot -type=Histogram s
On retrouve le fait que la répartition n'est pas uniforme (il y a moins de valeurs proches de 1)
OP
OP
OP.jpg (16.99 Kio) Vu 12688 fois

ou encore de la revue Jeux&Stratégie (9 pas avec également une graine à mettre en mémoire 1) :

Code : Tout sélectionner

2nd π
ln x
SUM 1 (ajout à la mémoire 1)
RCL 1
y^x
5
=  (mémoire 1 ^5)
2nd INV Int
STO 1
ln(π) s'écrit ⍟○1 en APL... :mrgreen:
Modifié en dernier par Schraf le 01 juin 2020 09:35, modifié 1 fois.
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: Misez p'tit, optimisez n°62: Les boules

Message par C.Ret »

Schraf a écrit : 31 mai 2020 15:26 [...]Quand on regarde les réponses, plusieurs sont partis sur des simulations de lois plutôt que sur la simulation d'un tirage de boules. Effectivement, s'il y a N boules Noires et B boules Blanches, les probabilités d'obtenir à l'étape suivante une boule N ou R sont respectivement N / (N+R) et R / (N+R). On peut alors simuler une loi de Bernoulli (pile ou face) ayant une probabilité de succès p = N / (N+R).
[...]Or dans cet exercice, il n'est pas évident de savoir quelles proportions de N et de B il y aura en moyenne, en ayant répété des centaines de fois l'expérience.
[...]
Je ne suis pas d'accord avec ces deux points.

1 - Pourquoi simuler la loi de tirage alors que le protocole est parfaitement défini. Il s'agit très précisément d'un tirage aléatoire avec remise. Ce n'est pas comme si l'on ne savait pas selon quelles règles précises la remise s'effectue. C'est un cas un peu différent du Tirage Aléatoire avec remise classique, c'est juste une variante de cela car l'on remet deux fois la boule de la couleur tirée au lieu d'une fois comme dans le cas scolaire.

Et c'est justement la Loi des Grands Nombres qui permet d'établir l'expression rigoureuse de ce type de tirages. Expression qui peut être validée par un très grands nombres de simulations. Et la validation sera d'autant mieux validée que le nombre de simulation sera grand et les tirages simulés proches d'un hasard parfait.

2 - Les proportions de boules blanches et noires sont parfaitement définies par le protocole à appliquer. Les proportions peuvent être établies pour tous les tirages et donc les proportions moyennes également au sens de la Loi des Grands Nombres justement.
J'avais d'ailleurs donné un tableau qui dénombrait systématiquement la composition des boules selon le résultat de chaque tirage :

Code : Tout sélectionner

   1           2                  3                     4                          5                           6 ... 
TIRAGES                                                                                                         /
                                                                                     oooooo* (120/720)
                                                                                   /                           \
                                                          ooooo* (24/120)
                                                        /                          \                           /
                                    oooo* (6/24)                                     ooooo** (24/720 + 96/720)
                                  /                     \                          /                           \
                 ooo* (2/6)                               oooo** (6/120 + 18/120)
               /                  \                     /                          \                           /
     oo* (1/2)                      ooo** (2/24 + 4/24)                              ooo**** (48/720 + 72/720)
   /           \                  /                     \                          /                           \
 o*              oo** (1/6 + 1/6)                         ooo*** (12/120 + 12/120)
   \           /                  \                     /                          \                           /
     o** (1/2)                      oo*** (4/24 + 2/24)                              oo***** (72/720 + 48/720) 
               \                  /                     \                          /                           \
                 o*** (2/6)                               oo**** (12/120 + 6/120)            
                                  \                     /                          \                           /
                                    o**** (6/24)                                     oo***** (96/720 + 48/720)
                                                        \                          /                           \
                                                          o***** (24/120)
                                                                                   \                           /
                                                                                     o****** (120/720)
                                                                                                               \               ...
MPO 61 - Tirages avec double remise.gif
MPO 61 - Tirages avec double remise.gif (42.85 Kio) Vu 12677 fois
Evidemment la connaissance des proportions des boules noires et blanches après chacun des tirages ne suffit pas à prévoir quelle sera le résultat expérimental d'un tirage, ni de deux tirages, ni de trois tirages consécutifs , etc...

C'est le principe même des probabilités où il ne faut pas confondre dénombrement (ici les proportions de boules noires et blanches) et les probabilités (fréquences d'obtention des tirages de puis le setup initial).
Modifié en dernier par C.Ret le 07 juin 2020 09:25, modifié 2 fois.
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
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: Misez p'tit Optimisez en version APL

Message par Schraf »

Oui, en faisant des calculs de dénombrements puis de probas on peut écrire un algorithme donnant un résultat équivalent à l'expérience initiale. J'avais bien lu ta réponse qui donnait :

Code : Tout sélectionner

1 " " AREAD T : B= RND (T+1) : PRINT B,2+T-B : END
Mais on peut aussi utiliser le hasard (méthodes de Monte-Carlo) pour trouver la réponse en ayant aucune connaissance a priori ou quand les calculs sont infaisables à la main.

Je pense par exemple à un problème comme "2 personnes se donnent RdV entre 12h et 13h, combien de minutes attendra en moyenne le premier qui arrive ?". Un élève de seconde peut avec un programme de 3-4 lignes en Python trouver un encadrement satisfaisant pour la réponse alors qu'il faut un BAC+1 pour trouver la réponse avec des intégrales doubles. Il y a tout de même une part de modélisation (ça veut dire quoi arriver entre 12h et 13h ?) mais on ne va pas jusqu'à résoudre le problème entièrement à la main comme tu as pu le faire pour ce MPO en utilisant un arbre.

Allez, on a raison chacun à 50% ? :D :D
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: Misez p'tit Optimisez en version APL

Message par C.Ret »

OUI, oui, je ne dis pas que tu ai tord ou que j'ai raison, bien au contraire.

Il n'y a pas de problème à retrouver les Lois de Distribution des probabilités en utilisant des méthodes basées sur la répétition de tirages aléatoires ou pseudo-aléatoires (Méthodes de Monte-Carlo et consœurs). C'est même en général un très bon exercice pratique pour la compréhension des concepts théoriques et phénomènes pratiques que les mathématiques de la statistique tentent de nous expliquer.

On peut donc effectivement retrouver par une simulation une loi de distribution (comme par exemple les Lois de Bernoulli) et comparer les résultats pratiques de cette simulation aux lois énoncées. Mais on ne peut pas simuler une loi de distribution.

Concernant le programme que j'avais publié, la fonction pseudo-aléatoire RND permet de simuler le résultat au bout des T tirages afin de répondre à la question. Cette fonction unique ne simule pas les tirages, uniquement permet de choisir aléatoirement l'une des compositions possibles à l'issue des T tirages. Comme après chaque tirage, les différentes compositions en boules blanches et noires sont équiprobables, il n'y a pas besoin de simuler le chemin qui conduit au contenu du sac après T tirages. Il y a juste à tirer au sort l'une des compositions possibles.
C'est plus courts, plus rapide et aussi plus juste car chaque tirage n'est pas parfaitement aléatoire ...

C'est comme tenter d'estimer ses chances de survivre dans une ville aux rues en quadrillage 5 x 5 en échappant au ZOMBI qui s'y trouve en tentant de rejoindre un abri situé à l'autre extrémité du quadrillage des rues. Nos chances de survie ne dépendent que de la position du ZOMBI et peuvent être calculées rapidement sans faire intervenir aucune simulation.

D'où ma proposition pour répondre en APL au problème MPO-61:
Dans un sac vous avez une boule blanche et une boule noire.
A: vous piochez une boule à l'aveugle et vous rajoutez dans ce sac une boule de la couleur de celle que vous venez de piocher.
Vous avez maintenant 3 boules dans le sac et vous recommencer la manip (A).

Le programme devra simuler un nombre de tirages variable et vous retourner à la fin le nombre de boules
blanches et noires contenues dans le sac.

Code : Tout sélectionner

      MPO61 ← {|(2+⍵) 0∘.-?(1+⍵)}
      MPO61  0
1  1                                          ⍝  Composition initiale
      MPO61  4
5  1                                          ⍝  Une composition possible après 4 tirages
      MPO61  4
3  3                                          ⍝  Une autre composition possible après 4 tirages
      MPO61  1000
189 813                                       ⍝  Une composition possible après 1000 tirages
Quand à ma proposition en APL d'un code donnant la proportion moyenne des boules blanches et noires au bout de T tirages :

Code : Tout sélectionner

     MPO61m ← { 0.5  0.5 }
      MPO61m 1000
.5 .5                                         ⍝  Proportion moyenne exacte (espérance) après 1000 tirages
En effet, quelque soit le résultat d'un tirage, on ajoute à chaque tirage une boule. Après T tirages le sac contient donc exactement (2+T) boules. Après T tirages il y a donc (T+1) compositions de sacs possibles contenant respectivement entre 1 et (2+T-1) boules noires et entre (2+T-1) et 1 boules blanches.
Si j'appelle N (respectivement B) le nombre de total de boules noires (respectivement blanches) contenue dans toutes les compositions de sacs possibles à l'issue des T tirages, on a N = 1 + 2 + 3 + ... + (T-1) + T + (T+1) = T x (T+2) / 2 qui est rigoureusement égal à B = (T+1) + T + (T-1) + ... + 3 + 2 +1.
Et donc la proportion moyenne de toutes les compositions possibles après T tirages (c'est à dire l'espérance) est très exactement et de façon immuable égale à 50% de boules noires ou blanches.

Je pense que tu ne simules pas assez fort, ton code renvoie

Code : Tout sélectionner

      1000 simul 1000
0.4918493014 0.5081506986
A partir de combien d'efforts tu obtiens quelque chose de plus proche du résultat espéré, ne serai ce qu'à .0001 près ?

Code : Tout sélectionner

      ########################################## simul 1000
0.49999 0.50001
Modifié en dernier par C.Ret le 07 juin 2020 09:33, modifié 4 fois.
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.
Répondre

Retourner vers « Emulateurs »