Rozwiąż problem sekretarza

13

Sekretarz Problem jest znanym problemem opisany jako sposób:

  1. Potrzebujesz nowej sekretarki
  2. Masz N kandydatów, z którymi możesz przesłuchać pojedynczo
  3. Jesteś w stanie ocenić każdego kandydata po rozmowie kwalifikacyjnej. Twój system punktacji nigdy nie da dwóm aplikantom tego samego wyniku
  4. Po przeprowadzeniu rozmowy z wnioskodawcą musisz natychmiast udzielić odpowiedzi „tak” lub „nie”
  5. Chcesz kandydata z najwyższym wynikiem

Rozwiązaniem jest przesłuchanie pierwszych floor(N/e)wnioskodawców, a następnie zaakceptowanie pierwszego wnioskodawcy, który uzyskał wyższy wynik niż wszyscy poprzedni wnioskodawcy. Jeśli żaden z wnioskodawców nie jest wyższy, zwróć ostatniego wnioskodawcę. Co ciekawe, daje to pierwszemu wnioskodawcy 1/eprocent czasu. eodnosi się do numeru Eulera . Aby uzyskać wartość e, możesz użyć wbudowanego loglub zakodować go z dokładnością do co najmniej 5 miejsc po przecinku.

Wejście:

Niepusta tablica unikalnych nieujemnych liczb całkowitych nie więcej niż 2^31-1.

Wynik:

Liczba całkowita reprezentująca wybranego kandydata. Aby wyjaśnić, algorytm jest następujący:

  1. Znajdź maksymalny element w pierwszych floor(N/e)elementach tablicy.
  2. Iteruj przez pozostałe elementy i zwróć pierwszy element, który jest wyższy niż maksimum znalezione w kroku 1.
  3. Jeśli żaden z elementów nie jest wyższy, zwróć ostatni element.

Powiedzmy, że twoja tablica była [2,7,4,3,9,20], więc N = 6i floor(N/e) = 2. Pierwsze 2 elementy tablicy to [2,7]. Maksymalna [2,7]to 7. Pozostałe elementy to [4,3,9,20]. Pierwszy element jest większy niż 7jest 9, więc wracamy 9.

Przypadki testowe:

[0]         => 0
[100]       => 100
[100, 45]   => 100
[0, 1]      => 0
[45, 100]   => 45
[1, 4, 5]   => 4
[1, 5, 4]   => 5
[5, 4, 1]   => 1
[5, 1, 4]   => 4
[4, 1, 5]   => 5
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
=> 98
[10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30]
=> 30

Twoim rozwiązaniem musi być O(n), gdzie njest długość tablicy. Jeśli twój język ma wbudowaną funkcję, która wyszukuje maksimum tablicy, możesz założyć, że funkcja bierze O(n)(i mam nadzieję, że tak).

Obowiązują standardowe luki, a to jest gra w , więc stwórz najkrótszą odpowiedź w swoim ulubionym języku!

Nathan Merrill
źródło
1
Czego enależy użyć?
obfity
2
@voidpigeon Zakładam, że to en.wikipedia.org/wiki/E_(mathematical_constant)
Klamka
1
Ach, teraz rozumiem, jak działa algorytm. Myślałem, że twój drugi akapit oznacza, że ​​nigdy nie rozmawiasz z kandydatami po głosowaniu (n / e).
Klamka
1
Pytałem konkretnie, ponieważ w niektórych językach krótsze jest definiowanie zmiennej z dokładnością do 5 miejsc po przecinku, niż faktyczne użycie wbudowanego e(np. Python, gdzie e=2.71828jest krótszy niż import math;math.E)
Mego
1
Uwaga: „1 / e procent czasu.” Byłoby naprawdę złe. Prawdopodobieństwo to 1 / e, czyli około 37% razy
edc65

Odpowiedzi:

4

Galaretka, 13 bajtów

L:Øe³ḣȯ-Ṁ<i1ị

Zdecydowanie algorytm O (n) , mam nadzieję, że implementacja O (n) . Wypróbuj online!

Jak to działa

L:Øe³ḣȯ-Ṁ<i1ị  Main link. Argument: A (list of scores)

L              Get the length of A.
 :Øe           Divide the length by e, flooring the result.
    ³ḣ         Retrieve the that many scores from the beginning of A.
      ȯ-       Logical OR; replace an empty list with -1.
        Ṁ      Compute the maximum of those scores.
         <     Compare each score in A with that maximum.
          i1   Find the first index of 1 (0 if not found).
            ị  Retrieve the element of A at that index (the last one if 0).
Dennis
źródło
3

CJam, 20 bajtów

q~___,1me/i<:e>f>1#=

Działa podobnie do sugestii Dennisa.

q~___                     Read array, duplicate three times
      ,                   Consume one to find the length
       1me/i              Push e then divide and take floor
            <             Take that many elements from the list
             :e>          Find maximum (Thanks to Dennis)
                f>        Label array elements larger than this as 1
                  1#      Find the first one (won't be in set of elements we've looked in)
                    =     Take that element from the final copy of the array. -1 gives us the last element as required
Simmons
źródło
$W=nie działa w czasie liniowym.
Dennis
Urgh, masz rację. Czy istnieje lepszy sposób na znalezienie maksimum w CJam, o którym wiesz?
A Simmons
1
:e>(redukuj maksymalnie)
Dennis
@Dennis Thanks!
A Simmons,
2

Java, 128 118 bajtów

a->{int c=(int)(a.length/Math.E),i=0,m=-1,t=0;for(;i<a.length;i++){t=a[i];if(i<c)m=t>m?t:m;if(t>m)return t;}return t;}

Zębaty:

static Function<Integer[], Integer> secretary2 = a -> {
    int c = (int) (a.length/Math.E),     // c = floor(N/E)
        i = 0, m = -1, t = 0;            // declare vars early to save bytes
    for (;i<a.length;i++) {              // for each element of input
        t = a[i];                        // cache element to save bytes
        if (i<c)                         // if before c
            m = t>m ? t : m;             // m = max(m, element)
        if (t>m)                         // if element > m
            return t;                    // return: we've found our best
    }                                    // if never found a good element
    return t;                            // return the last element
};
CAD97
źródło
2

JavaScript (ES6) 64

(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

Mniej golfa

(
 a, 
 l=a.length/Math.E, // limit for stage 1
 x // init at undefined
)=>(
  a.every(v => --l > 0 // checking for >0 no need to floor
          ? x>v?1:x=v // stage 1, find max in x, always return truthy
          : (z=v)<x ) // stage 2, set z to current value and exit early if z>x
  , z // at last z has the last seen value
)

Test

f=(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

console.log=x=>O.textContent+=x+'\n'

;[ 
 [0], [100], [0,1], [1,2,3],
 [100, 45],
 [45, 100],
 [1, 4, 5],
 [1, 5, 4],
 [5, 4, 1],
 [5, 1, 4],
 [4, 1, 5],   
 [10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30],
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
].forEach(t=>{
  var r=f(t)
  console.log(r+' : '+t)
})
<pre id=O></pre>

edc65
źródło
1

Rubinowy, 64 bajty

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}
obolały
źródło
2
@Doorknob Pętla przechodzi przez elementy pierwszego piętra (N / e), aby znaleźć maksimum, a następnie przechodzi przez resztę listy w najgorszym przypadku, porównując każdy element z maksimum. Istnieje tylko jedno porównanie na element w obu częściach.
obfity
Ach, właśnie tak. Źle odczytałem i pomyślałem, że znajdujesz maksimum w każdej iteracji.
Klamka
1
W rzeczywistości myślę, że nadal jest to O (n), jeśli wykonasz tylko a.finddrugi krok, chociaż oczywiście jest to o wiele mniej wydajne.
histokrat
1
Możesz użyć (0...c)dla zakresu wykluczającego c.
histokrata
@histocrat Tak, powinien to być O (2n), który jest O (n)
Nie to, że Charles
1

PARI / GP , 70 bajtów

Może to mieć problem ze starszymi wersjami gp, gdy ma się singleton, ale działa przynajmniej od wersji 18487.

v->m=vecmax(v[1..t=#v\exp(1)]);for(i=t+1,#v,v[i]>m&&return(v[i]));v[#v]
Charles
źródło
1

JavaScript (ES6), 79 bajtów

a=>(m=Math.max(...a.splice(0,a.length/Math.E)),a.slice(a.findIndex(x=>x>m))[0])

Działa, ponieważ findIndexzwraca -1w przypadku awarii, ale a.slice(-1)[0]zwraca ostatni element tablicy zgodnie z potrzebami.

Neil
źródło
1

Python 2, 87 bajtów

a=input()
t=int(len(a)/2.71828)
m=max(a[:t]+[-1])
for x in a[t:]:
 if x>m:break
print x

Użytkownik wprowadza tablicę jako listę z nawiasami kwadratowymi i przecinkami. input()Polecenie Pythona 2 jest tutaj wygodne.

Niezależnie od tego, czy zakończymy proces wcześniej, zatrudniamy ostatnią osobę, z którą przeprowadzono wywiad.

Mathmandan
źródło
1

Perl 6, 43 bajtów

Myślę, że to O (n)

{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}
Skróty klawiszowe
źródło
1

Python 3.5; 110 bajtów:

def Interview(h):k=max(h[0:int(len(h)/2.71828)-1]);n=max(h[int(len(h)/2.71828)-1:len(h)-1]);return max([k, n])

Zasadniczo powyższe działanie polega na tym, że najpierw pobiera podaną tablicę, „h”, o ile zawiera więcej niż 5 elementów (na razie ...), znajduje maksymalną wartość w pierwszej (długość tablicy (len (h )) / Liczba Eulera (do 5 miejsc po przecinku)) elementów tej tablicy, a następnie zwraca tę wartość jako „k”. Ponadto „n” jest wartością maksymalną w pozostałej części tablicy. Na koniec wartość zwracana z funkcji jest wartością maksymalną w tablicy zawierającej zarówno „k”, jak i „n”.

Uwaga: max()funkcją Pythona jest złożoność O (n).

Poniżej znajduje się bardziej czytelna, niekodująca wersja golfowa powyższego kodu, która ma losową, unikalną tablicę 10-elementową, aby potwierdzić, że działa:

import random, math

def Interview():
    k = max(h[0:int(len(h)/math.e)-1])
    n = max(h[int(len(h)/math.e)-1:len(h)-1])
    return max([k, n])

h = random.sample(range((2*31)-1), 10)

print(Interview(h))
R. Kap
źródło
Witamy w PPCG! Możesz rozdzielić importowane przecinki. Nie musisz też generować tablicy samodzielnie, więc możesz usunąć tę część kodu (po prostu ustaw tablicę jako parametr funkcji)
Nathan Merrill
@NathanMerrill Tak, myślałem o zrobieniu tego, ale pomyślałem, że to ci się nie spodoba, ale teraz, gdy wiem, że to naprawdę nie ma znaczenia, zmienię moją odpowiedź. Ponadto dziękuję za wskazówkę dotyczącą przecinka oddzielającego mój import. Zupełnie o tym zapomniałem!
R. Kap
Inne wskazówki: Masz wiele niepotrzebnych białych znaków (po przecinkach, między znakami równości. Na końcu nie potrzebujesz też drukowanego oświadczenia
Nathan Merrill,
@NathanMerrill Dzięki za wskazówki! Będę o tym pamiętać, gdy będę więcej grał w golfa! :)
R. Kap