Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

pb d'algorithme en lycée

Posté par
Giromon
19-08-09 à 08:37

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 Moderateur
re : pb d'algorithme en lycée 19-08-09 à 08:50

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
pb d'algorithme en lycée 19-08-09 à 10:12

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 Moderateur
re : pb d'algorithme en lycée 19-08-09 à 10:17

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 Posteur d'énigmes
re : pb d'algorithme en lycée 19-08-09 à 10:17

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 Moderateur
re : pb d'algorithme en lycée 19-08-09 à 10:21

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 Moderateur
re : pb d'algorithme en lycée 19-08-09 à 10:22

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

Posté par
J-P Posteur d'énigmes
re : pb d'algorithme en lycée 19-08-09 à 10:24

  

Posté par
Giromon
pb d'algorithme en lycée 19-08-09 à 13:40

Merci à tous pour vos réponses

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !