MPO 108 - Le problème de la secrétaire

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO 108 - Le problème de la secrétaire

Message par FLISZT »

Bonsoir,

Juste avant d'aller manger, voici une proposition que j'espère fonctionnelle……

N : nbr de secrétaires
V : qualité
SBR : routine appelée deux fois

Code : Tout sélectionner

«
	0
	
	« FOR I 				@ début routine SBR	
		{ ←V } RAND +			@ liste contenant V à laquelle on ajoute une valeur aléatoire
		« MAX » STREAM →NUM '←V' STO	@ la + gde qualité est stockée dans la var locale compilée V
	NEXT »					@ fin routine SBR
								
	→ N ←V SBR				@ les 3 var locales dont une compilée
	
		« 1 N 1 EXP / 			@ préparation des indices de la "boucle pour rien"
		DUP NEG 'N' STO+		@ la valeur maxi de la 1ère boucle est soustraite de N
		SBR EVAL			@ appel de la routine SBR
		1 N 				@ indices de la "boucle pour de vrai" 
		SBR EVAL			@ appel de la routine SBR

		"N= " N +			@ affichage des résultats
		"V= " ←V +
		»
»
Edit : Tandis que j'étais dans la cuisine :slime:, ça m'est venu d'un coup : mon programme ne respecte pas l'énoncé, en particulier la "boucle pour de vrai"… Je suis parti un peu "bille en tête" avec mon idée de routine dans ce programme 2ème mouture (la V1 était classique).
Mais comme j'aime bien cette idée, je vais faire une troisième version ! :)
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO 108 - Le problème de la secrétaire

Message par FLISZT »

En cette heure tardive, j'ai renoncé à ma "belle idée"…
De plus, j'en suis à ma 3ème tentative pour ce post !
(notamment suite à une déconnexion sauvage, puis après un joli plantage, juste « ô joie » quand j'allais terminer) :)

Code : Tout sélectionner

«
	0 
	0
	0
	→ N Q R V 				@ N: nbr de secrétaires ; Q: qualité ; R: Rang
						@ V: valeur aléatoire MAX dans "boucle pour rien"
		«
		1 N 1 EXP / IP 			@ préparation des indices de la "boucle pour rien"
		DUP 'R' STO 			@ R contient le nombre de boucles "pour rien"
		R NEG 'N' STO+			@ préparation indice N ↔ "boucle pour de vrai"
		FOR I 				@ début "boucle pour rien"
			RAND { V }  +		@ valeur aléatoire ajoutée à la liste (liste de 2 élts au plus)
			« MAX » STREAM →NUM	@ détermination de la valeur maxi de cette liste…
			'V' STO			@ … et stockage valeur maxi dans V
		NEXT
		
		1 N				@ indices "boucle pour de vrai"
		FOR I 
			'R' INCR		@ incrémentation de R… 
			;			@ … et suppression de la valeur de R du niveau 1 de la pile
			RAND DUP V >		@ tirage valeur aléatoire et test si sup. à Q
			IF 
			THEN 'Q' STO		@ si oui, valeur stockée dans Q…
				N 'I' STO	@ … et sortie de la boucle en mettant le compteur I à la valeur N
			ELSE 
				DUP Q >  	@ sinon, test : « valeur aléatoire sup. à Q ? »
				IF 
				THEN 'Q' STO	@ si oui, valeur aléa. stockée dans var. Q
				ELSE ;		@ sinon, valeur aléa. suprimée de la pile	
				END		@ « ; » efface le niveau 1 de la pile …
			END			@ … mais sans "Too Few Arguments" si celle-ci est vide
		NEXT
						@ affichage résultat
		R "Rang" →TAG			@ Rang: …
		Q "Qualité" →TAG		@ Qualité: … 
		»
»	
Edit : correctionS… !
Schraf a écrit : 11 avr. 2022 13:33
On trouve par exemple que pour 20 secrétaires qui se présentent, il faudra en auditionner 7 avant de commencer à pouvoir dire "on vous recrute".
Avec 100 secrétaires, il faudra déjà en auditionner 37 (ou 36 si on utilise l'approximation avec un nombre bien connu que je ne dévoile pas).
Avec N=20, la première recrue semble être effectivement la huitième, au mieux, si j'en crois mon programme.

Avec N=100 et ce nbre mystérieux, je trouve 36,7879441171… soit, après avoir pris la partie entière, 36 boucles "pour rien".
Donc la première recrue sera la 37ème, au mieux.
Le nombre minimal de boucles sera fonction de la manière dont on fait ses arrondis.
(avec IP, avec FLOOR ou avec CEIL en RPL)
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
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: MPO 108 - Le problème de la secrétaire

Message par C.Ret »

Ah! Bien le petit code RPL !

Il ressemble furieusement à ce que je prépare pour mon HP-28S.

Mais, je suis en train de me demander sîl n'y a pas déjà dans celle-ci un jeu d'instructions aui vont me permettre de gagner en simplicité, concision et rapidité…

Je creuse un peu mon idée. Si celle-ci me conduit à une impasse, je vais plagier le code de FLISZT
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: MPO 108 - Le problème de la secrétaire

Message par Schraf »

@FLISZT : Pour N = 100 et en utilisant le nb mystérieux on arrive bien à 36 mais en prenant la vraie formule (celle de la vidéo avec calcul exact des probabilités), on obtient un maximum pour 37.

Code : Tout sélectionner

 Probabilités de recruter la meilleure secrétaire en laissant de côté :
...
35 : succes = 0.37070863451796543
36 : succes = 0.3710145955041931
37 : succes = 0.3710427787126428
38 : succes = 0.37080069165082236
...
Après, entre 37,101% et 37,104% ça ne changera pas grand chose !

Pour la "boucle pour rien", on peut donc (fin de la vidéo) la remplacer par :

Code : Tout sélectionner

«
 1 N 1 EXP / IP 	@ préparation des indices de la "boucle pour rien"
 DUP 'R' STO 		@ R contient le nombre de boucles "pour rien"
 1/x RAND SWAP 		@ On peut simuler max(RAND, RAND..., RAND) avec R fois RAND
 y^x 'V' STO		@ par RAND ^ (1 / R)
 ...
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO 108 - Le problème de la secrétaire

Message par FLISZT »

Si ma calculatrice ne me conte pas de carabistouiiles (non ça ne se mange pas :wink: ) :
1/e ≈ 0,367879441171…

@ Schraff : Donc il va bien falloir arrondir la valeur à un moment ou un autre.
Ou alors, je prends la valeur supérieure, à 10-² près, la plus proche (soit 0,37) et j'évite ce nombre mystérieux… dont certains disent qu'il pourrait rappeler une certaine voyelle ?! Pfff… sottises !! (ça, ça se mange :D )

@ C.Ret : il doit être tout à fait possible de faire mieux que ce programme basé, au départ, sur bien des oublis, par rapport aux termes de l'énoncé.
Pas exactement, faire puis réfléchir, mais un peu quand même…

L'idée de Schraff, de faire N tirages de valeurs aléatoires au préalable, me semble une très bonne piste que je ne vais pas tarder à suivre.

Sur une hp-28S, le plus simple a priori serait de mettre tout cela dans une liste, même si ça peut devenir très long s'il y a foule… ceci explique sûrement l'exigence des cabinets de recrutement ! Si en plus ils ont perdu le manuel de leur "28"… :lol:
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO 108 - Le problème de la secrétaire

Message par FLISZT »

Voici une nouvelle version très inspirée de la précédente et sensiblement plus rapide.
Il y a une seule boucle.

Au début, R contient le nombre de "boucles pour rien".
Une fois celles-ci terminées, R est incrémentée permettant ainsi de déterminer le rang de la recrue.

N est initalisée avec le nombre de secrétaires qui postulent, puis contient le nombre de "boucles pour de vrai" : N ← N - R
La valeur maximale du compteur de boucle I est la somme des variables R et N.

Code : Tout sélectionner

«
	0 
	0
	0
	→ N Q R V 					@ N: nbr de secrétaires ; Q: qualité ; R: Rang
							@ V: valeur aléatoire MAX obtenue dans "boucles pour rien"
	«
	N 1 EXP / IP 					@ int( N *1/e) = nbr de "boucles pour rien" stocké dans R
	DUP 'R' STO NEG 'N' STO+			@ N devient le nbr maximum de "boucles pour de vrai"
	1 R N +						@ indices de la boucle : 1 et (R+N)
	FOR I
		I R ≤					@ Si le compteur I est ≤ à R (boucles pour rien non-finies)
		IF					@ R contient le nombre de "boucles pour rien"
		THEN
			RAND V MAX			@ tirage d'une valeur aléatoire comparée à V… 
			'V' STO				@ … et MAX mis dans V
		ELSE 					@ I > R ⇒ fin des "boucles pour rien"
			'R' INCR ;			@ on compte 1 à 1 les "boucles pour de vrai"
			RAND DUP V > 			@ Si valeur aléatoire sup. à V… 
			IF
			THEN
				'Q' STO			@ … alors on stocke cette valeur dans Q…
				R N + 'I' STO		@ … et compteur I mis à (R+N) afin de sortir de la boucle
			ELSE				@ Sinon
				DUP Q >			@ comparaison de Q avec la valeur aléatoire sur la pile… 
				IF
				THEN
					'Q' STO		@ … si supérieure, valeur aléa. stockée dans Q… 
				ELSE
					;		@ … sinon, suppression de cette valeur aléa. de la pile
				END
			END
		END
	NEXT
							@ Affichage résultat
	R "Rang" →TAG					@ Rang: …
	Q "Qualité" →TAG				@ Qualité: … 
»
Que c'est long à mettre en page, si l'on veut que les commentaires soient exactement l'un en dessous de l'autre… 8O
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
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: MPO 108 - Le problème de la secrétaire

Message par C.Ret »

FLISZT a écrit : 15 avr. 2022 20:10Que c'est long à mettre en page, si l'on veut que les commentaires soient exactement l'un en dessous de l'autre… 8O
Le block-note est ton ami surtout avec une fonte fixe (comme Consolas ou Courier par exemple!
FLISZT a écrit : 15 avr. 2022 17:30 Sur une hp-28S, le plus simple a priori serait de mettre tout cela dans une liste, même si ça peut devenir très long s'il y a foule… ceci explique sûrement l'exigence des cabinets de recrutement ! Si en plus ils ont perdu le manuel de leur "28"… :lol:
Une liste, pour quoi faire ? Allons directement à l'essentiel:

Code : Tout sélectionner

« DUP  1  EXP  /  CEIL  → n s     @  Number of candidates and probe size
  « n  s  n  -  RAND  *  + CEIL   @  recruited candidate position
    RAND  s  INV  ^               @  max(RAND,… s …,RAND)
    R→C » »                       @  formate as ( ## , .score )
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.
OlidaBel
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 106
Enregistré le : 04 avr. 2021 16:09
Localisation : 50.693165,4.573478

Re: MPO 108 - Le problème de la secrétaire

Message par OlidaBel »

badaze a écrit : 10 avr. 2022 20:37 Moi. J’ai une autre méthode. :mrgreen:
La méthode Ti-nder ? :D :D
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8384
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: MPO 108 - Le problème de la secrétaire

Message par badaze »

OlidaBel a écrit : 16 avr. 2022 16:02
badaze a écrit : 10 avr. 2022 20:37 Moi. J’ai une autre méthode. :mrgreen:
La méthode Ti-nder ? :D :D
:mrgreen:
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO 108 - Le problème de la secrétaire

Message par FLISZT »

C.Ret a écrit : 15 avr. 2022 20:51 Le block-note est ton ami surtout avec une fonte fixe (comme Consolas ou Courier par exemple!
Merci pour le conseil. J'e n'ai pas "bloc-note" car mon laptop n'est pas sous WIN. J'ai bien Notepad++ (sous Wine), mais je ne l'utilise jamais.
(Je crois me souvenir qu''on peut l'adapter à nos calculatrice RPL de manière à avoir la coloration syntaxique ad hoc.)
Le pblm rencontré vient sans doute que je ne saisis pas les commentaires dans mon éditeur mais dans celui du forum.
À voir la prochaîne fois…
C.Ret a écrit : 15 avr. 2022 20:51 Une liste, pour quoi faire ? Allons directement à l'essentiel:

Code : Tout sélectionner

« DUP  1  EXP  /  CEIL  → n s     @  Number of candidates and probe size
  « n  s  n  -  RAND  *  + CEIL   @  recruited candidate position
    RAND  s  INV  ^               @  max(RAND,… s …,RAND)
    R→C » »                       @  formate as ( ## , .score )
C'est diablement court !
Faire sans liste ne me surprend pas puisque je l'ai fait.
Ce qui me surprend est qu'il n'y a pas de test (ni donc, a priori, de recherche de la note maxi des n premières secrétaires non retenues).
(?)
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
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: MPO 108 - Le problème de la secrétaire

Message par C.Ret »

FLISZT a écrit : 26 avr. 2022 20:00Ce qui me surprend est qu'il n'y a pas de test (ni donc, a priori, de recherche de la note maxi des n premières secrétaires non retenues).
C'est effectivement le plus surprenant: pas de test, ni de liste.

Mais je suis scrupuleusement la demande initiale:
Schraf a écrit : 10 avr. 2022 20:08 Pour ce MPO, vous aurez en valeur d'entrée uniquement le nombre N de secrétaires qui viennent postuler pour le poste.
C'est l'unique argument que prend mon programme.
Schraf a écrit : 10 avr. 2022 20:08 Leurs qualités seront des nombres entre 0 et 1 (exclus) tirés aléatoirement par la machine au moment de l'entretien (donc inutile de les mémoriser quelque part avant de lancer votre programme)
Donc, inutile de créer une liste ou de mettre quoique ce soit en mémoire.
Schraf a écrit : 10 avr. 2022 20:08La calculatrice affichera le numéro (entre 1 et N) de la secrétaire retenue ainsi que sa qualité.
C'est ce à quoi sert l'instruction R→C finale.

Sinon, "les n premières non retenues(sic)" sont dans mon code ce qui est quantifié par la variable locale s. Celle ci est déduite de la valeur d'entrée n c'est à dire le nombre N de secrétaires qui viennent postuler pour le poste. Le calcul exacte est « DUP 1 EXP / CEIL »

La note maximale des s premières secrétaires non retenues est déterminée sans test, comme le suggère Schraf à la fin de sa vidéo ; cette note maximale est calculée directement par la séquence : « RAND s INV ^ »

Quant au numéro d'ordre de l'heureuse candidate, il est tiré aléatoirement par la séquence « n s n - RAND * + CEIL ». Je conviens volontiers que cela puisse un peu surprendre. Au lieu de faire une boucle tirant (n-s) scores aléatoires, je ne tire qu'un seul nombre pseudo-aléatoire qui donnera le numéro d'ordre nécessairement aléatoire du score maximal. Ce qui me semble très sensé vu que l'exercice d'un MPO demande à en faire le moins possible afin de miser petit et optimiser !

J'aime le MPO, c'est un truc au poil pour un paresseux comme moi ...


Mais, je dois avouer que je ne suis pas arrivé à cette solution immédiatement. En fait, mes premiers codes ne tiraient pas aléatoirement les scores, je trouvais plus amusant de dérouler l'algorithme sur une série préétablie de tirages afin de voir comment mes codes se plantaient avec la plupart des exemples en choisissant un râteau ...
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: MPO 108 - Le problème de la secrétaire

Message par Schraf »

@C.Ret : Je ne suis pas sûr de bien comprendre ton :

Code : Tout sélectionner

n  s  n  -  RAND  *  + CEIL
On dirait que tu choisis au hasard la secrétaire parmi les restantes sans tenir compte du score max des "s" secrétaires auditionnées (pour rien).
Pour moi, on devrait commencer par le MAX des "s" secrétaires (en faisant comme toi un RAND s INV ^ par exemple) et ensuite chercher à simuler une variable aléatoire qui doit suivre une loi géométrique tronquée. Par contre, je ne sais pas si c'est possible à faire avec un seul RAND, pas sûr...
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO 108 - Le problème de la secrétaire

Message par FLISZT »

C.Ret a écrit : 27 avr. 2022 20:35 Sinon, "les n premières non retenues(sic)"
Pour être exacte, la citation aurait dû être :
FLISZT a écrit : 26 avr. 2022 20:00… des n premières secrétaires non retenues.
… pour autant que je puisse juger, il n'y a aucune trace du moindre sous-entendu dans la phrase que j'avais écrite.

(avec n fonction du nombre total de secrétaires à auditionner, je précise au cas où… )
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
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: MPO 108 - Le problème de la secrétaire

Message par C.Ret »

Schraf a écrit : 28 avr. 2022 17:35 On dirait que tu choisis au hasard la secrétaire parmi les restantes sans tenir compte du score max des "s" secrétaires auditionnées (pour rien).
Pour moi, on devrait commencer par le MAX des "s" secrétaires (en faisant comme toi un RAND s INV ^ par exemple) et ensuite chercher à simuler une variable aléatoire qui doit suivre une loi géométrique tronquée. Par contre, je ne sais pas si c'est possible à faire avec un seul RAND, pas sûr...
Très juste, je considère que la "meilleure" secrétaire se trouve au hasard parmi celles restantes. Mais à y réfléchir, c'est très certainement faux.
En effet, si le score pendant l'échantillonnage de s premiers candidats est élevé, il y a plus de chance que le candidat sélectionné soit vers la fin du panel (voir carrément le dernier).
Et si au contraire, le score de l'échantillon est faible, le candidat sélectionné sera plus certainement parmi les premiers auditionnés (même s'il reste des candidats meilleurs plus loin !).

Effectivement, j'ai vu que l'on pouvait simuler un tirage selon une loi normale à partir de deux tirages d'une loi uniforme (deux RAND donc).
Pour le moment, je n'ai pas trouvé comment faire de même pour une 'loi géométrique tronquée' ou une 'loi exponentielle discrète'. Par analogie avec la loi normale, il y a de grandes chances qu'il faille plusieurs variables aléatoires uniformément distribuées pour arriver à cette fin.

Pour le moment, je sèche...

... peut-être qu'Eric Schraf connais un moyen, un moyen simple adapté à un MPO ?
Sinon, la mort dans l'âme, il va me falloir me résigner à inclure une boucle dans mon code ... :(
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: MPO 108 - Le problème de la secrétaire

Message par Schraf »

@C.Ret : Comme tu as pu le voir sur Wikipédia, si X suit une loi exponentielle de paramètre 1 (X ↪ Exp(1)) alors Y = ⌈ θX ⌉ (où ⌈ ... ⌉ = CEIL) suit une loi géométrique de paramètre p = 1 - exp(1-1/θ).

Or pour simuler une loi exponentielle de paramètre λ on peut utiliser l'algorithme -ln(rand) / λ (où rand ↪ U(]0,1[)). Donc pour X ↪ Exp(1) on a juste à faire -ln(rand).

Dans notre cas, après avoir vu k secrétaires, on obtient une qualité r∈]0,1[ que l'on cherche à dépasser avec les futures auditions. En imaginant pour commencer qu'il y a une infinité de secrétaires potentielles, Y suit une loi géométrique G(1-r). C'est-à-dire que l'on tire un nombre aléatoire entre 0 et 1 jusqu'à obtenir une valeur > r, le résultat de l'expérience est alors le nombre de tirages qui ont été nécessaires, ce qui correspond au numéro ( + k secrétaires du début à ajouter) de la secrétaire choisie.

On veut donc que p = 1 - exp(1-1/θ) = 1 - r ce qui donne θ = -1 / ln(r)

Ainsi, pour un r fixé, Y peut être simuler par l'algorithme ⌈ ln(rand) / ln(r) ⌉

Et pour tronquer, il suffira de faire min(Nb_total_de_secretaires, ⌈ ln(rand) / ln(r) ⌉)

On voit aussi que plus r est petit, plus 1 / ln(r) est également petit et on aura rapidement une secrétaire, et si r est proche de 1, 1 / ln(r) sera grand d'où plus de difficultés à trouver la perle rare.
Répondre

Retourner vers « Tous les Pockets »