Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Programmation
- » Voisins, voisines, (code sur énigme freddy)
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- freddy
- 26-09-2011 11:26:20
Salut,
dans ma procédure, le traitement s'arrête automatiquement quand la boucle "do" atteint le nombre de 10.000 et écrit le dernier résultat dans le fichier de sortie.
C'est comme ça que je sais qu'elle n'a pas besoin d'aller au delà de 3.000 tirages aléatoires.
De la même manière, je savais d'avance que je n'avais pas besoin d'avoir plus de 10 positions à droite et à gauche de 14, à cause de la démonstration fournie par ailleurs, dans la rubrique "énigme, ...".
- totomm
- 26-09-2011 09:35:41
Bonjour,
Note : Pour être entièrement valable vous devriez écrire :
if (test =1 AND i<10000) then i=10000 else message d'erreur
afin d'être averti si 10000 était insuffisant...
Un de mes fils m'a regardé en riant et m'a dit : "ça ne te ressemble pas, ce message d'erreur sortira à chaque passage !"
Au temps pour moi !
Mieux vaut se fier à l'examen des données ou ajouter un message d'avertissement (if i=9999 then...) avant "if test=1 then..."
Je reconnais volontiers que mon intervention cette fois est du genre "mouche du coche" (cette fois seulement :-)
Cordialement
- totomm
- 25-09-2011 18:51:19
Bonsoir,
J'ai écrit un programme qui mémorise toutes les répartitions possibles à l'étape n en fonction de toutes les répartitions de l'étape (n-1), qui ne garde qu'un exemplaire d'une répartition obtenue plsieurs fois, et qui compte.
(Note : Les configurations symétriques sont conservées). Le fichier des configurations est donc énorme !
Voici quelques lignes de résultats sur le nombre de configurations (pour 2N coquillages) :
N = 10 , Etape = 0 , nbconfigs = 1
N = 10 , Etape = 1 , nbconfigs = 1
N = 10 , Etape = 2 , nbconfigs = 1
N = 10 , Etape = 3 , nbconfigs = 3
N = 10 , Etape = 4 , nbconfigs = 4
N = 10 , Etape = 5 , nbconfigs = 4
N = 10 , Etape = 6 , nbconfigs = 6
N = 10 , Etape = 7 , nbconfigs = 10
N = 10 , Etape = 8 , nbconfigs = 13
N = 10 , Etape = 9 , nbconfigs = 19
N = 10 , Etape = 10 , nbconfigs = 24
......
N = 10 , Etape = 162 , nbconfigs = 32104
N = 10 , Etape = 163 , nbconfigs = 32161
N = 10 , Etape = 164 , nbconfigs = 32203
N = 10 , Etape = 165 , nbconfigs = 32266
N = 10 , Etape = 166 , nbconfigs = 32264
N = 10 , Etape = 167 , nbconfigs = 32251
....
N = 10 , Etape = 377 , nbconfigs = 22
N = 10 , Etape = 378 , nbconfigs = 15
N = 10 , Etape = 379 , nbconfigs = 11
N = 10 , Etape = 380 , nbconfigs = 7
N = 10 , Etape = 381 , nbconfigs = 5
N = 10 , Etape = 382 , nbconfigs = 3
N = 10 , Etape = 383 , nbconfigs = 2
N = 10 , Etape = 384 , nbconfigs = 1
N = 10 , Etape = 385 , nbconfigs = 1
Cordialement
- freddy
- 25-09-2011 16:40:29
Bonjour,
freddy a écrit :statistiquement, il faut environ 2.750 tirages pour arriver à l'étape 385 numérotée par le compteur cpt
Cette valeur de 2.750 est statistiquement tirée de i. D'après votre programme elle serait donc différente si vous preniez une autre valeur que 27 pour votre table et vos tirages. Si vous faisiez vos tirages comme yoshi, vous auriez toujours 385 au lieu de 2750.
Le nombre de répartitions différentes des coquillages auxquelles on peut arriver (en tirant au hasard) à une étape donnée est au moins de l'ordre de 30.000 à chaque étape intermédiaire (entre étapes 150 et 190 par exemple).
i de 1 à 10000 est une bonne sécurité (étant vus les 2750) puisque votre condition d'arrêt est "aucune position n'a plus de 1 coquillage"
Note : Pour être entièrement valable vous devriez écrire :
if (test =1 AND i<10.000) then i=10000 else message d'erreur
afin d'être averti si 10.000 était insuffisant...Cordialement.
Salut,
si tu peux (et seulement si) me montrer comment tu arrives à 30.000, je me coucherais moins bête ce soir.
- totomm
- 25-09-2011 11:12:08
Bonjour,
statistiquement, il faut environ 2750 tirages pour arriver à l'étape 385 numérotée par le compteur cpt
Cette valeur de 2750 est statistiquement tirée de i. D'après votre programme elle serait donc différente si vous preniez une autre valeur que 27 pour votre table et vos tirages. Si vous faisiez vos tirages come yoshi, vous auriez toujours 385 au lieu de 2750.
Le nombre de répartitions différentes des coquillages auquelles on peut arriver (en tirant au hasard) à une étape donnée est au moins de l'ordre de 30000 à chaque étape intermédiaire (entre étapes 150 et 190 par exemple).
i de 1 à 10000 est une bonne sécurité (étant vus les 2750) puisque votre condition d'arrêt est "aucune position n'a plus de 1 coquillage"
Note : Pour être entièrement valable vous devriez écrire :
if (test =1 AND i<10000) then i=10000 else message d'erreur
afin d'être averti si 10000 était insuffisant...
Cordialement.
- freddy
- 23-09-2011 21:28:57
Re,
deux remarques :
- statistiquement, il faut environ 2750 tirages pour arriver à l'étape 385 numérotée par le compteur cpt ; quelle que soit la manière de s'y prendre, c'est toujours le même résultat au bout de 385 étapes. C'est ce point que la démonstration doit établir. C'est ce point qui permet de déduire la réponse à l'étape 384. Et il faut établir pourquoi, malgré le choix aléatoire du joueur concerné.
- ce n'est pas du VBA, mais de la programmation sous SAS.
Le serveur dédié est tellement puissant (il permet de traiter des fichiers de très grosses tailles) que les calculs prennent un temps machine infinitésimal, même si je prévois au maximum 10.000 tirages pour m'assurer que ça s'arrête toujours à l'étape 385.
Bb
- totomm
- 23-09-2011 20:11:02
Bonsoir,
@yoshi : Fred m'avait prévenu de mettre "Code=Python" pour avoir la couleur...
Cordialement
- totomm
- 23-09-2011 20:04:46
Bonsoir,
Comparaisons entre le programme VBA de freddy, celui de yoshi et celui de totomm :
Dans le programme "VBA" de freddy, il y a 27 positions et non 21 et pas de rebouclage en cercle, sans doute pour avoir une marge de 3 positions à chaque extrémité.
Le tirage au hasard est fait sur les 27 positions, et réitéré si la position tirée n'a pas au moins 2 coquillages
alors que yoshi tire au hasard sur les seules personnes ayant au moins 2 coquillages. On comprend alors pourquoi les itérations du programme nécessitent chez freddy i de 1 à 10000 et non i de 1 à 384
Comme aucune contrainte n'était données sur la loi à suivre pour les tirages, totomm fixe les tirages successifs(choisis par lui pour démontrer pourquoi 384) tout autant valables que les tirages variables.
Yoshi a pris 384 comme condition d'arrêt (voir l'énoncé de l'énigme), alors que freddy et totomm testent s'il n'y a plus que des 1 (ou des 0) dans chaque position.
Donc maintenant : Prochaine étape annoncée par freddy....
Cordialement
- freddy
- 23-09-2011 12:00:06
Salut,
puisque nous en sommes à échanger nos codes, voici le mien :
DEFINITION DES VARIABLES ET SORTIES
data A (keep =cpt i table1-table27);array table(27);cpt=0;
INITIALISATION DU VECTEUR TABLE
do p= 1 to 27;
table(p)=0;
end;
table(14)=20;
output; ( écrit le résultat dans le fichier de données A)REALISATION
do i= 1 to 10000; génére autant de tirages aléatoires selon une loi uniforme que nécessaires
alea=int(ranuni(-1)*27)+1;
if table(alea) >=2 then do;
cpt=cpt+1;
table(alea-1)=table(alea-1)+1;
table(alea)=table(alea)-2;
table(alea+1)=table(alea+1)+1;
output;
end;if i >= 10 then do;
test=0;
do p=1 to 27;
test=max(0,table(p),test);
end;
if test =1 then i=10000; pour sortir de la boucle en vérifiant que le jeu est terminé
end;end;
Je pense que la mécanique est conforme à celle du jeu.
Et je vois bien ce qui se passe, mais je n'ai toujours pas démontré pourquoi je suis sûr que ça donnera toujours le même résultat.
Et je trouve fantastique qu'on puisse annoncer que ce sera toujours comme ça sans le démontrer !
Prochaine étape, la démonstration mathématique.
- totomm
- 22-09-2011 11:36:07
re Bonjour,
Par contre, une question de freddy me semble toujours pendante (j'espère ne pas avoir aussi des insuffisances en lecture)
J'ai répondu post #14 à cette question posée post #13 dans
Accueil Enigmes, casse-têtes, curiosités et autres bizarreries, Voisins / Voisines
Cordialement
- totomm
- 22-09-2011 11:26:57
Bonjour,
Dans Accueil Enigmes, casse-têtes, curiosités et autres bizarreries, Voisins / Voisines
...., A l'issue de 384 étapes, Virginie a deux coquillages de plus que Paul.
Combien ont ils respectivement ?
certainement 2 et 0, et ensuite chacun(e) aura 1 coquillage sauf un(e).
Peux tu le prouver ? C'est important de le prouver,…
Alors vous pouvez reprendre vos remarques mal venues…je n'ai fait qu'évoquer la preuve demandée !
.....dont je pensais bien que freddy aurait à coeur de la publier, car
Donc, dans tous les cas, on arrive à cette solution.
Je vais tâcher de le démontrer en langage mathématique
Cordialement
- freddy
- 21-09-2011 13:33:18
Salut,
je viens de prendre connaissance des deux derniers échanges.
En effet, la question est bien celle soulevée par le dernier échange : "combien de coquillages ont Paul et Virginie à l'issue de la 384ième étape, sachant que l'un a deux coquillages de plus que l'autre ? "
Aurais je fait une co(q)uille ?
- yoshi
- 21-09-2011 12:03:43
Bonjour,
Programme tout à fait OK. (...)
Ce programme est un algorithme "correct",(...)
C'est vrai que j'ai la triste manie de faire des erreurs non seulement mathématiques, mais aussi de programmation et donc de publier des codes incorrects : une certification extérieure était donc tout à fait indispensable ! Je dois combien ?
J'ai toujours fait attention et si j'en redouble maintenant, allez savoir pourquoi...
Pourquoi "correct" entre guillemets, du bout des lèvres, à prendre avec des pincettes ?
il n'est pas "complet" dans le domaine traité. (ce que yoshi signale bien à juste raison....)
Absolument indispensable aussi d'ajouter "à juste raison" :
1. Voir commentaire ci-dessus.
2. Pour bien enfoncer le clou sur la hiérarchie des codes
Ça commence à devenir lassant...
Mais ce programme ne permet, ni de démontrer que le résultat est indépendant de l'ordre dans lesquel les coquillages sont répartis, ni le pourquoi de 384 (ou (somme-1) des n/2 premiers carrés d'entiers), ni le fait que le bouclage circulaire est inutilisé quand on fixe initialement la position des n avec n/2 personnes de chaque coté.
Merci d'en avoir bien signalé les manques...
Cela dit
1. Je n'ai jamais prétendu le contraire : j'ai bien précisé au contraire que j'avais essayé de faire simple et didactique en respectant le cahier des charges déposé par freddy : à chaque tour, l'heureux distributeur de coquillages est choisi au "hasard".
Bon, le hasard et les langages de programmation... quoique Python ait évolué depuis ses débuts en la matière.
2. La complétude n'était pas mon propos. Il faut arrêter d'enfoncer les portes ouvertes (sauf s'il s'agit d'asseoir la supériorité d'un code sur l'autre. Vais-je encore oser publier mes insignifiances ?) : j'avais pensé avoir été clair là-dessus !
Quant à l'autre programme qui lui, apparemment, va faire partie des merveilles du monde qui fait tout et plus encore (même si je suis un peu déçu : il ne repeint pas la cuisine à ma place), n'ayant pas été capable, en deux lectures, de voir l'idée qui le sous-tendait, j'ai laissé courir... Voilà qui ajoute une pierre de plus à mon jardin... Ce n'est pas grave, j'ai encore de la place !
3. Freddy n'a pas demandé de montrer que le résultat est indépendant de l'ordre dans lesquel les coquillages sont répartis,
4. Freddy n'a pas demandé le pourquoi de 384,
5. Freddy n'a pas demandé de montrer que le bouclage circulaire est inutilisé quand on fixe initialement la position des n avec n/2 personnes de chaque coté.
Freddy avait dit :
Vingt et une personnes, dont Paul et Virginie, du club Med' de Peysey Nancroix, sont assises autour d'une table circulaire pour participer à un jeu "step by step".
Une étape consiste à choisir au hasard une personne qui a au moins deux coquillages ; celle-ci doit alors donner un coquillage à chacun de ses deux voisins (voisines).
Au départ du jeu, une personne a 20 coquillages, les autres n'ont rien.
A l'issue de 384 étapes, Virginie a deux coquillages de plus que Paul.
Combien ont ils respectivement ?
Moi, j'étudie seulement à chaque relance du programme, une situation due à un tirage (pseudo) aléatoire à chaque tour sur 384 tours.
Par contre, une question de freddy me semble toujours pendante (j'espère ne pas avoir aussi des insuffisances en lecture) :
position 6 heures, le gars qui en a 20.
Il est choisi au hasard 4 fois, il lui en reste donc 12, à sa droite il y en a 4 et à sa gauche autant.
Maintenant, comment poursuit-on ?
Où est passé le tirage aléatoire du petit problème ?
@+ (peut-être)
- totomm
- 21-09-2011 10:09:49
Bonjour,
Programme tout à fait OK. On peut même vérifier que la position du 2 final est bien celle initiale des n=20 !
(Je lui ai ajouté un affichage de chaque étape avec numéro de l"étape)
Mais ce programme ne permet, ni de démontrer que le résultat est indépendant de l'ordre dans lesquel les coquillages sont répartis, ni le pourquoi de 384 (ou (somme-1) des n/2 premiers carrés d'entiers), ni le fait que le bouclage circulaire est inutilisé quand on fixe initialement la position des n avec n/2 personnes de chaque coté.
Ce programme est un algorithme "correct", qui se "termine en un temps fini". il n'est pas "complet" dans le domaine traité. (ce que yoshi signale bien à juste raison....)
Mais je maintiens que vaut "démonstration" un algorithme possédant les 3 notions essentielles : "Correction, Terminaison et Complétude."
Cordialement.
Edit : télescopage avec la réponse précédente de freddy dont la démonstration - hors tout programme - sera tout à fait bienvenue.
- freddy
- 21-09-2011 09:51:07
Salut yoshi,
ok, je comprends bien la démarche, la procédure telle que tu l'expliques est claire pour moi.
Pour le pgm, je te fais confiance ; un jour peut être, j'essaierai d'apprendre à pitonner !!!
Donc, dans tous les cas, on arrive à cette solution.
Je vais tâcher de le démontrer en langage mathématique.
Bis bald !