pb d'algorithme en lycée

Posté par Giromon Giromon

Voici un petit problème d'algorithmique que je me pose : je souhaite tirer au hasard deux nombres entiers distincts compris au sens large entre 1 et 25.
En notant Alea(1,25) le tirage d'un entier compris entre 1 et 25, je propose l'algorithme suivant :
Affecter Alea(1,25)dans A
Affecter le contenu de A dans B
Tant que A=B, affecter Alea(1,25)dans B, Fin de Tant que
Afficher A et B.
En pratique cet algorithme fonctionne mais il ne me semble pas satisfaisant car, en théorie, il se pourrait qu'il ne s'arrête jamais.Par exemple, si A =10, quand on choisit aléatoirement B entier entre 1 et 25 , on peut toujours tomber sur 10 infiniment même si c'est complètement improbable.

Avez-vous une autre idée d'algorithme pour traiter ce problème?

Edit jamo : forum modifié.

Posté par jamo jamo

Tout d'abord : BONJOUR

en effet, cet algorithme pourrait en théorie ne jamais s'arrêter, mais en pratique, je te rassure, il s'arrêtera assez vite.

Cela dit, on peut imaginer contourner le problème.
J'ai plusieurs idées en tête.
En voici une.

Au début, tu crées un tableau de 25 cellules, et tu y stockes les entiers de 1 à 25.

Une fois que tu tires le numéro 10, tu décales le contenu de toutes les cases au delà de 10.
Ainsi, le nombre 11 va dans la case 10, le nombre 12 dans la case 11, ... et le nombre 25 dans la case 24.

Ensuite, il te reste à tirer un nombre au hasard entre 1 et 24, et le tour est joué, puisque dans les 24 premières cellules du tableau, il ne manque plus que le nombre 10 !

Posté par Giromon Giromon

Merci Jamo,
Je viens de tester votre idée : elle fonctionne parfaitement et c'est mathématiquement correct.
Vous semblez dire que vous avez d'autres pistes pour traiter ce problème : pouvez-vous me donner d'autres indications sur des méthodes différentes?
A nouveau merci

Posté par jamo jamo

Par exemple, je me demandais si, en tombant à nouveau sur le même nombre, pourquoi ne pas prendre le nombre immédiatement au-dessus ou en-dessous ? (c'est-à-dire 9 ou 11 dans l'exemple où on tombe sur 10 au début)

Mais finalement, non, ce n'est pas bon, car cela modifie les probabilités pour ce nombre.

Posté par J-P J-P

Comme Jamo le dit, le risque de devoir boucler longtemps est quasi nul du moins avec 25 chiffres, le risque serait bien accru avec par exemple seulement 3 chiffres différents permis (1 à 3 au lieu de 1 à 25)

Et même là, il serait fort étonnant que cela doivent boucler bien longtemps (si évidemment la routine qui crée les nombres pseudo aléatoires est bien faite).

Ce que propose Jamo (décalage de ligne dans un tableau), revient au même, me semble-til que de :

- tirer un premier nombre entier au hasard entre 1 et 25 inclus, soit n ce nombre.
- tirer un second nombre entier au hasard entre 1 et 24 inclus, soit m ce nombre.
- Si m >= n alors le second nombre devient (m+1)

Vérifie.

Posté par jamo jamo

Sinon, on peut imaginer d'autres méthodes avec cette histoire de tableau, sans y décaler tous les nombres une fois le premier tiré.

Ainsi, au 2ème tirage, en ayant tiré le 10 au 1er tirage, on tire un nombre n entre 1 et 24 :
* si n est inférieur à 10, alors on prend le n-ième nombre du tableau ;
* si n est supérieur ou égal à n, alors o prend le (n+1)-ième nombre dans le tableau.

Posté par jamo jamo

J-P >> nous avons eu la même idée, je rédigeais pendant que tu postais ton message !

Posté par J-P J-P

Posté par Giromon Giromon

Merci à tous pour vos réponses