Nombre d’occurrence d'un nombre aléatoire unique

Bonjour,

Sujet

Vous décidez à présent de vous lancez dans le business des jeux d’argents et d’organiser une grande loterie.
Vous devez réaliser un programme qui invite l’utilisateur à saisir le nombre de tickets mis en jeu, le nombre de lots (nécessairement inférieur ou égal au nombre de tickets) et les numéros desdits tickets. Il faut ensuite afficher les numéros des tickets gagnants (ils doivent être tirés aléatoirement) pour chaque lot avec cette contrainte : un ticket ne peut gagner qu’une seule fois 2. Bien entendu, vous compartimenterez votre programme et vous veillerez à libérer correctement la mémoire allouée dynamiquement.

Mon code

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

printf("\n[Loterie]\n\n"); printf("Nombre de tickets mis en jeu : "); unsigned int nbTickets, nbLots; scanf("%d", &nbTickets); printf("Nombre de lots : "); scanf("%d", &nbLots); if (nbLots >= nbTickets) return printf("Nombre de lots >= Nombre de tickets !\n"); int *tableau = (int*)malloc(nbTickets * sizeof(int)); if (tableau == NULL) { printf("Plus de memoire !\n"); exit(0); } printf("Tickets : \n"); for (i = 0; i < nbTickets; i++) scanf("%d", &tableau[i]); printf("\n[Tickets gagnants]\n"); srand(time(NULL)); unsigned int m; unsigned int* tableauLots = (unsigned int*)malloc(nbLots * sizeof(unsigned int)); if (tableauLots == NULL) { printf("Plus de memoire !\n"); exit(0); } for (i = 0; i < nbLots; i++) { m = (rand() % nbLots) + 1; tableauLots[i] = tableau[m]; //if ( (OccurenceLotsGagnants(tableauLots, tableau[m])) > 1) m = (rand() % nbLots) + 1; printf("Lot %d : %d\n", i, tableau[m]); } free(tableau);

---

La fonction OccurenceLotsGagnant

Code:

---

1 2 3 4 5 6 7 8 9 10 11

unsigned int OccurenceLotsGagnant(unsigned int *tab, unsigned int x) { if (*tab == x) { return 1 + OccurenceLotsGagnant(tab + 1, x); } else { return OccurenceLotsGagnant(tab + 1, x); } }

---

Question

Comment faire en sorte que si l’élément apparaît plus d'une fois, refaire un random etc jusqu’à la dernière valeur ?

Code:

---

if ( (OccurenceLotsGagnants(tableauLots, tableau[m])) > 1) m = (rand() % nbLots) + 1;

---

Merci

Je ne comprends pas bien la fonction récursive OcurrenceLotGagnant.

Ligne 28, il faut effectuer un tirage parmi nbTickets (c'est un ticket que l'on tire) pour l'associer au i-ème lot.
Et en effet si ce ticket est déjà associé à un parmi la liste des lots précédement tirés, il faut recommencer au autre tirage aléatoire.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

for ( i = 0 ; i < nbLots ; ++i ) { int j; int m; do { m = rand() % nbTickets; for ( j = 0 ; j < i ; ++j ) { if ( tableauLots[j] == tableau[m] ) break; // déjà gagné } while ( j < i ); // a été vus avant, tableauLots[i] = tableau[m]; printf( "Lot %d : %d\n" , 1+i , tableau[m] ); }

---

Bonjour,

Citation:

---

Envoyé par FoolBar

Code:

---

1 2 3 4 5 6 7 8 9 10 11

unsigned int OccurenceLotsGagnant(unsigned int *tab, unsigned int x) { if (*tab == x) { return 1 + OccurenceLotsGagnant(tab + 1, x); } else { return OccurenceLotsGagnant(tab + 1, x); } }

---

---

Cette fonction a un comportement indéterminé, car elle s'appelle récursivement à l'infini.
Visiblement, tu veux compter le nombre de x dans le tableau.
Pour cela, ta fonction a aussi besoin de prendre en paramètre la taille du tableau :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

unsigned int CountInTable(const unsigned int *tab, unsigned size, unsigned int element) { if (size > 0) { if (tab[0] == element) return 1 + CountInTable(tab + 1, size - 1, element); else return CountInTable(tab + 1, size - 1, element); } else { return 0; } }

---

Cela dit, de mon point de vue, une implémentation itérative serait plus lisible :

Code:

---

1 2 3 4 5 6 7 8

unsigned int CountInTable(const unsigned int *tab, unsigned size, unsigned int element) { unsigned int result = 0; for (int k = 0; k < size; ++k) if (tab[k] == element) ++result; return result; }

---

Citation:

---

Envoyé par FoolBar

Comment faire en sorte que si l’élément apparaît plus d'une fois, refaire un random etc jusqu’à la dernière valeur ?

---

Parmi tes nbTickets tickets, tu veux en sélectionner aléatoirement nbLots, dans un ordre aléatoire.
Voici un algorithme alternatif qui permet de ne générer que nbLots nombres aléatoires :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Notation : l'élément numéro n d'un tableau est le n+1-ième élément du tableau.   Soit nbTicketsRestants un entier initialisé à nbTickets. Soit tabIndicesTicketsRestants un tableau de nbTickets booléens initialisés à VRAI. Pour indiceLot allant de 0 à nbLots-1. Soit k un entier aléatoire entre 0 et nbTicketsRestants-1 inclus, choisi avec une probabilité uniforme. Soit indiceTicketAAffecter l'indice du k+1-ième élément VRAI de tabIndicesTicketsRestants. Affecter le ticket numéro indiceTicketAAffecter au lot numéro indiceLot. Dans le tableau tabIndicesTicketsRestants, mettre à FAUX l'élément numéro indiceTicketAAffecter. Décrémenter nbTicketsRestants. FinPour

---

Edit 2017-09-17-12h10 : ajout de deux const.

Bonjour

Citation:

---

Envoyé par Pyramidev

Cette fonction a un comportement indéterminé, car elle s'appelle récursivement à l'infini.

---

Pas du tout, très déterminé au contraire. A un moment on aura un truc style "max depth recursion" et ça plante :mrgreen:

Citation:

---

Envoyé par Pyramidev

Cela dit, de mon point de vue, une implémentation itérative serait plus lisible

---

Du mien aussi. Il faut toujours privilégier l'itératif quand c'est possible. Souvent plus lisible effectivement mais surtout beaucoup moins gourmand en ressources. Un peu plus de travail d'algo à effectuer en contrepartie mais ça vaut le coup.

Citation:

---

Envoyé par Pyramidev

Voici un algorithme alternatif qui permet de ne générer que nbLots nombres aléatoires :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Notation : l'élément numéro n d'un tableau est le n+1-ième élément du tableau.   Soit nbTicketsRestants un entier initialisé à nbTickets. Soit tabIndicesTicketsRestants un tableau de nbTickets booléens initialisés à VRAI. Pour indiceLot allant de 0 à nbLots-1. Soit k un entier aléatoire entre 0 et nbTicketsRestants-1 inclus, choisi avec une probabilité uniforme. Soit indiceTicketAAffecter l'indice du k+1-ième élément VRAI de tabIndicesTicketsRestants. Affecter le ticket numéro indiceTicketAAffecter au lot numéro indiceLot. Dans le tableau tabIndicesTicketsRestants, mettre à FAUX l'élément numéro indiceTicketAAffecter. Décrémenter nbTicketsRestants. FinPour

---

---

Mouais. Ca fonctionne bien évidemment, mais je ne suis pas certain de l'honnêteté du tirage. Parce que la population décroit à chaque tirage. S'il y a par exemple 5 lots à tirer sur 10 tickets, alors
- le premier ticket gagnant aura 1 chance sur 10 d'être choisi
- le second ticket aura 1 chance sur 9
- le 3° aura 1 chance sur 8
- le 4° aura 1 chance sur 7
- le 5° aura 1 chance sur 6

Pour essayer d'uniformiser les chances de chacun, moi je remettrais les tickets tirés dans le panier. Mais si un même ticket est tiré 2 fois alors je ne lui affecte pas de lot. Et bien entendu donc je tire des tickets tant qu'il reste des lots à affecter...

Citation:

---

Envoyé par Sve@r

Pas du tout, très déterminé au contraire. A un moment on aura un truc style "max depth recursion" et ça plante :mrgreen:

---

Dans cette page, on peut lire :

Citation:

---

Infinite loop without side-effects

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <stdio.h>   int fermat() { const int MAX = 1000; int a=1,b=1,c=1; // Endless loop with no side effects is UB while (1) { if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1; a++; if (a>MAX) { a=1; b++; } if (b>MAX) { b=1; c++; } if (c>MAX) { c=1;} } return 0; }   int main(void) { if (fermat()) puts("Fermat's Last Theorem has been disproved."); else puts("Fermat's Last Theorem has not been disproved."); }

---

Possible output:

Code:

---

Fermat's Last Theorem has been disproved.

---

---

La fonction fermat s'exécute à l'infinie, sans avoir de side effect. Le compilateur fait comme si ce n'était pas le cas, constate que le seul retour possible est 0 et simplifie la fonction ainsi :

Code:

---

1 2 3

int fermat() { return 0; }

---

Dans la norme du C, je n'ai pas réussi à trouver un passage correspondant au cas d'une fonction qui s'exécute à l'infinie sans avoir de side effect.

Du côté du C++, dans N4659 (draft de C++17), le passage est le suivant :

Citation:

---

4.7.2 Forward progress
1 The implementation may assume that any thread will eventually do one of the following:
(1.1) — terminate,
(1.2) — make a call to a library I/O function,
(1.3) — perform an access through a volatile glvalue, or
(1.4) — perform a synchronization operation or an atomic operation.

---

Citation:

---

Envoyé par Sve@r

Mouais. Ca fonctionne bien évidemment, mais je ne suis pas certain de l'honnêteté du tirage. Parce que la population décroit à chaque tirage. S'il y a par exemple 5 lots à tirer sur 10 tickets, alors
- le premier ticket gagnant aura 1 chance sur 10 d'être choisi
- le second ticket aura 1 chance sur 9
- le 3° aura 1 chance sur 8
- le 4° aura 1 chance sur 7
- le 5° aura 1 chance sur 6

---

Le tirage est honnête.
Au premier tour, chaque ticket a 1 chance sur 10 d'être affecté au premier lot.
Donc chaque ticket a 9 chances sur 10 d'atteindre le deuxième tour.
Quand un ticket a atteint le deuxième tour, il a une chance sur 9 d'être affecté au deuxième lot.
Or, (9/10)*(1/9) == 1/10. Donc, au final, au départ, chaque ticket aura bien une chance sur 10 d'être affecté au deuxième lot.
Et ainsi de suite.

Citation:

---

Envoyé par Pyramidev

Dans cette page, on peut lire :

La fonction fermat s'exécute à l'infinie, sans avoir de side effect. Le compilateur fait comme si ce n'était pas le cas, constate que le seul retour possible est 0 et simplifie la fonction ainsi :

Code:

---

1 2 3

int fermat() { return 0; }

---

---

Mais comment le compilo sait-il que la boucle est infinie (et donc, que sa condition de sortie n'est jamais satisfaite)? Il teste exhaustivement le milliard de combinaisons?

Aucune idée pour le compilo , mais en général met un watchdog pour savoir si on tombe sur une boucle infini ou pas.

Erreur d'étourderie de ma part : Le compilo ne simplifie pas le code en :

Code:

---

1 2 3

int fermat() { return 0; }

---

mais en :

Code:

---

1 2 3

int fermat() { return 1; }

---

Désolé pour la confusion.

Le compilateur ne sait pas que la boucle est infinie, mais il voit while (1) et aucun break; Du coup, il en déduit que return 0;, qui est en dehors du while, ne sera jamais atteint.
La seule sortie possible de la fonction est return 1;, qui est à l'intérieur de la boucle while.
Or, le corps de cette boucle while n'a pas de side effect (ex : lecture et écriture dans flux) : elle ne fait que bidouiller des variables locales de la fonction. Le compilateur en déduit que, si le comportement est déterminé, alors l'instruction return 1; sera atteinte. Sinon, il fait ce qu'il veut. Du coup, dans les deux cas, il peut remplacer le code par :

Code:

---

1 2 3

int fermat() { return 1; }

---

Il n'a donc pas besoin de savoir si la boucle est finie ou infinie.

Citation:

---

Envoyé par Pyramidev

Le compilateur ne sait pas que la boucle est infinie, mais il voit while (1) et aucun break; Du coup, il en déduit que return 0;, qui est en dehors du while, ne sera jamais atteint.
La seule sortie possible de la fonction est return 1;, qui est à l'intérieur de la boucle while.
Or, le corps de cette boucle while n'a pas de side effect (ex : lecture et écriture dans flux) : elle ne fait que bidouiller des variables locales de la fonction. Le compilateur en déduit que, si le comportement est déterminé, alors l'instruction return 1; sera atteinte. Sinon, il fait ce qu'il veut. Du coup, dans les deux cas, il peut remplacer le code par :

Code:

---

1 2 3

int fermat() { return 1; }

---

Il n'a donc pas besoin de savoir si la boucle est finie ou infinie.

---

Certes... mais il y a une grosse différence entre

Code:

---

1 2 3 4 5 6

int fermat() { while (1) { if (condition_qui_ne_sera_peut_etre_jamais_atteinte_et_qui_reflete_alors_une_erreur_de_prog_qui_serait_alors_utile_d_etre_vue_et_corrigee_par_le_concepteur) return 1; } return 0; }

---

et

Code:

---

1 2 3

int fermat() { return 1; // Ok, je squeeze tout le code y compris l'erreur potentielle qui ne sera alors jamais remarquée... }

---

Non ???

@Sve@r: Je crois que j'ai compris le truc: L'idée, c'est que pour le compilateur, il est impossible de sortir de la fonction autrement qu'en retournant 1, parce que dans ceci:

Code:

---

1 2 3 4 5 6

int fermat() { while (1) { if (nimporte_quelle_condition) return 1; } return 0; }

---

il est physiquement impossible d'atteindre le return 0; (et d'ailleurs, un bon compilo se plaindra qu'il est "unreachable code" dès la compilation).

Ensuite, le manque prouvable d'effet de bord (et en C++, le manque de possibilité de lancement d'exception) signifie qu'on peut sauter le truc.
Régler une variable globale volatile dans la boucle empêcherait la suppression (mais ralentirait grandement la boucle) sur certaines implémentations, mais je ne suis pas sûr que le standard C (ou même C++) garantisse ce genre de truc (il offre beaucoup moins de garanties que la plupart des plate-formes concernant volatile).

Citation:

---

Envoyé par Médinoc

Régler une variable globale volatile dans la boucle empêcherait la suppression (mais ralentirait grandement la boucle) sur certaines implémentations, mais je ne suis pas sûr que le standard C (ou même C++) garantisse ce genre de truc

---

En C++, on a bien la garantie. N4659 (draft de C++17) :

Citation:

---

4.7.2 Forward progress
1 The implementation may assume that any thread will eventually do one of the following:
(1.1) — terminate,
(1.2) — make a call to a library I/O function,
(1.3) — perform an access through a volatile glvalue, or
(1.4) — perform a synchronization operation or an atomic operation.

---

Donc, si une boucle modifie une glvalue d'un type volatile, elle n'est pas obligée d'être finie.
En C, je ne sais pas.