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

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 »

Ca peut donner quelque chose comme ça en Python :

Code : Tout sélectionner

from random import random
from math import log,e,ceil

def MPO108(n):
  laisser = int(n / e)					# Nb de secrétaires non retenues
  r = random() ** (1 / laisser)				# Qualité max de ces secrétaires
  best = laisser + ceil(log(random()) / log(r))		# Rang théorique de la meilleure secrétaire
  return min(n, best)					# mais on ne veut pas dépasser n
Le soucis est que l'on a que le rang de la secrétaire et pas son score, mais l'approche est quand même intéressante.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
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 »

Moi, cela me conviens parfaitement, je peux modifier mon code sans y ajouter de liste, boucle ou de tests; c'est magnifique : on plus, un petit OVER me permet de garder son score ( ou du moins la limite minimale de celui-ci hé hé ). En effet, la candidate sélectionnée est peut-être bien meilleure que la moyenne de l'échantillon d'estimation. La stratégie est de ne rien dire pour ne pas attirer les soupçons ou les regards, 8O
Mais là, on rejoint une des techniques de Badaze ... :oops:

Code : Tout sélectionner

« DUP 1 EXP / CEIL → n s
  « RAND s INV ^
    RAND LN OVER LN / FLOOR s + n MIN
    R→C »
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 - Une idée d'amélioration :

Lorsque l'on trouve une secrétaire > r (qualité max k premières), on peut lui attribuer une qualité r + (1 - r) * rand qui sera dans l'intervalle ]r, 1[.
Si l'on ne la trouve pas (tirage en dehors de l'intervalle 1 à n), on prend la dernière et on lui attribue une qualité r * rand qui sera dans ]0, r[.

Code : Tout sélectionner

from random import random
from math import log,e,ceil

def MPO108(n):
  laisser = int(n / e)
  print(laisser,"secrétaires non retenues")
  r = random() ** (1 / laisser)
  print("Qualité max =", r)
  best = laisser + ceil(log(random()) / log(r))
  return (best, r + (1 - r) * random()) if best <= n else (n, r * random())
  
  
> MPO108(100)
36 secrétaires non retenues
Qualité max = 0.9433585565757729
(40, 0.9669234997238311)		# 40e secrétaire meilleure que les 36 premières

> MPO108(100)
36 secrétaires non retenues
Qualité max = 0.9776947901984604
(100, 0.6646667556296614)		# Dernière secrétaire
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
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 : 30 avr. 2022 14:30Lorsque l'on trouve une secrétaire > r (qualité max k premières), on peut lui attribuer une qualité r + (1 - r) * rand qui sera dans l'intervalle ]r, 1[.
Si l'on ne la trouve pas (tirage en dehors de l'intervalle 1 à n), on prend la dernière et on lui attribue une qualité r * rand qui sera dans ]0, r[.
Bonne idée. Mais comment ne pas ajouter un test dans mon code...

Ah! Oui, une idée:

Code : Tout sélectionner

« DUP 1 EXP / CEIL                               // taille  échantillon
  RAND OVER INV ^                                // qualité échantillon
  RAND LN OVER LN / FLOOR ROT + ROT MIN          // position sélectionnée 
  LAST ≤ 3 PICK -                                // Ya quand même un test mais pas de IF THEN ou IFT  
  RAND NEG * ROT +                               // qualité candidat sélectionné :(
  R→C »                                          // couple résultat mis en forme
Voilà un bon code RPL des familles, bien plus lisible, à mon avis, que du Python !

Comment ça non ? Vous n'estes pas d'accord ? Bizarre...

Voici les résultats pour une vingtaines de recrutement basés sur l'audition de 100 candidats:
MPO108 Résultats d'une vingtaines de recrutements simulés.gif
MPO108 Résultats d'une vingtaines de recrutements simulés.gif (93.86 Kio) Vu 2213 fois
On sélectionne un râteaux sur presque la moitié des recrutements, cet algo ne va pas me permettre de faire carrière en conseil et aide à la décision :(
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 vois que tu aimes l'humour, trêve de plaisanteries, il n'y a rien de plus lisible que l'APL, chacun le sait 😅 !

Code : Tout sélectionner

MPO108 ← {r,⍵⌊l+⌈(⍟?0)÷⍟r←?0*÷l←⌈⍵÷*1}
      MPO108 100
0.5120112598 39
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 »

Je découvre aujourd'hui que le problème de la secrétaire s'appelle aussi le jeu de Googol

La vidéo (en anglais) : The Game of Googol
Répondre

Retourner vers « Tous les Pockets »