Löse das Sekretärsproblem

13

Das Sekretärsproblem ist ein berühmtes Problem, das folgendermaßen beschrieben wird:

  1. Du brauchst eine neue Sekretärin
  2. Sie haben N Bewerber, die Sie einzeln befragen können
  3. Sie können jeden Bewerber nach dem Vorstellungsgespräch bewerten. Ihr Punktesystem gibt niemals zwei Bewerbern die gleiche Punktzahl
  4. Nachdem Sie einen Bewerber interviewt haben, müssen Sie sofort "Ja" oder "Nein" sagen
  5. Sie möchten den Bewerber mit der höchsten Punktzahl

Die Lösung besteht darin, die ersten floor(N/e)Bewerber zu befragen und dann den ersten Bewerber zu akzeptieren, der eine höhere Punktzahl als alle vorherigen Bewerber aufweist. Wenn keiner der Bewerber höher ist, senden Sie den letzten Bewerber zurück. Interessanterweise hat der Top-Bewerber 1/ein dieser Zeit einen prozentualen Anteil. ebezieht sich auf Eulers Nummer . Um den Wert von zu erhalten e, können Sie einen eingebauten Wert verwenden logoder ihn mit mindestens 5 Dezimalstellen fest codieren .

Eingang:

Ein nicht leeres Array von eindeutigen nicht negativen ganzen Zahlen, nicht mehr als 2^31-1 .

Ausgabe:

Eine Ganzzahl, die den ausgewählten Kandidaten darstellt. Um klar zu sein, ist der Algorithmus:

  1. Finden Sie das maximale Element in den ersten floor(N/e)Elementen des Arrays.
  2. Durchlaufen Sie die verbleibenden Elemente und geben Sie das erste Element zurück, das höher als das in Schritt 1 festgelegte Maximum ist.
  3. Wenn keines der Elemente höher ist, geben Sie das letzte Element zurück.

Angenommen, Ihr Array war [2,7,4,3,9,20], so N = 6und floor(N/e) = 2. Die ersten beiden Elemente des Arrays sind [2,7]. Das Maximum von [2,7]ist 7. Die restlichen Elemente sind [4,3,9,20]. Das erste Element , das größer ist als 7ist 9, so geht es zurück 9.

Testfälle:

[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

Ihre Lösung muss sein O(n), wo nist die Länge des Arrays. Wenn Ihre Sprache über eine integrierte Funktion verfügt, die das Maximum eines Arrays ermittelt, können Sie davon ausgehen, dass die Funktion dauertO(n) (und hoffentlich auch) dauert.

Es gelten Standardlücken, und dies ist ein , also machen Sie die kürzeste Antwort in Ihrer Lieblingssprache!

Nathan Merrill
quelle
1
Was esoll verwendet werden?
ängstlich
2
@voidpigeon Ich nehme an, es ist en.wikipedia.org/wiki/E_(mathematical_constant)
Türknauf
1
Ah, jetzt verstehe ich, wie der Algorithmus funktioniert. Ich dachte, dass Ihr zweiter Absatz bedeutet, dass Sie die Kandidaten nach dem Wortlaut (n / e) überhaupt nicht interviewen.
Türklinke
1
Ich habe speziell gefragt, weil es in einigen Sprachen kürzer ist, eine Variable mit einer Genauigkeit von 5 Dezimalstellen zu definieren, als die eingebaute Variable e(z. B. Python, wobei Python e=2.71828kürzer ist als import math;math.E)
Mego
1
Hinweis: `1 / e Prozent der Zeit.` wäre wirklich schlecht. Es ist eine Wahrscheinlichkeit von 1 / e, das ist ungefähr 37% der Zeit
edc65

Antworten:

4

Gelee, 13 Bytes

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

Auf jeden Fall ein O (n) -Algorithmus, hoffentlich eine O (n) -Implementierung. Probieren Sie es online!

Wie es funktioniert

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
quelle
3

CJam, 20 Bytes

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

Funktioniert ähnlich wie Dennis 'Vorschlag.

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
Ein Simmons
quelle
$W=läuft nicht in linearer Zeit.
Dennis
Urgh, du hast recht. Gibt es eine bessere Möglichkeit, das Maximum in CJam zu finden, von dem Sie wissen, dass es das tut?
Ein Simmons
1
:e>(um Maximum reduzieren)
Dennis
@ Tennis Danke!
Ein Simmons
2

Java, 128 118 Bytes

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;}

Eingerückt:

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
quelle
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)

Weniger golfen

(
 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
)

Prüfung

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
quelle
1

Ruby, 64 Bytes

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}
ängstlich
quelle
2
@Doorknob Durchläuft die Elemente des ersten Stockwerks (N / e) einmal, um das Maximum zu finden, und durchläuft dann im schlimmsten Fall den Rest der Liste, wobei jedes Element mit dem Maximum verglichen wird. In beiden Teilen gibt es nur einen Vergleich pro Element.
ängstlich
Ah, das stimmt. Ich habe falsch verstanden und dachte, Sie würden bei jeder Iteration das Maximum finden.
Türklinke
1
Tatsächlich denke ich, dass es immer noch O (n) ist, wenn Sie es nur a.findim zweiten Schritt tun , obwohl es offensichtlich viel weniger effizient ist.
Histokrat
1
Sie können (0...c)für einen Bereich verwenden, der c ausschließt.
Histokrat
@histocrat Ja, es sollte O (2n) sein, was O (n) ist
Nicht dass Charles
1

PARI / GP , 70 Bytes

Dies kann bei älteren Versionen von gp Probleme bereiten, wenn ein Singleton angegeben wird, funktioniert jedoch mindestens ab Revision 18487.

v->m=vecmax(v[1..t=#v\exp(1)]);for(i=t+1,#v,v[i]>m&&return(v[i]));v[#v]
Charles
quelle
1

JavaScript (ES6), 79 Byte

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

Funktioniert , weil findIndexkehrt -1bei einem Fehler, aber a.slice(-1)[0]kehrt das letzte Element der Anordnung , wie gewünscht.

Neil
quelle
1

Python 2, 87 Bytes

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

Der Benutzer gibt das Array als Liste mit eckigen Klammern und Kommas ein. Der input()Befehl von Python 2 ist hier praktisch.

Unabhängig davon, ob wir den Prozess vorzeitig beenden oder nicht, stellen wir die letzte Person ein, die interviewt wurde.

mathmandan
quelle
1

Perl 6, 43 Bytes

Ich denke das ist O (n)

{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}
Hotkeys
quelle
1

Python 3.5; 110 Bytes:

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])

Grundsätzlich bedeutet das oben Gesagte, dass zuerst ein bereitgestelltes Array benötigt wird, "h" , solange es mehr als 5 Elemente enthält (vorerst ...), und der Maximalwert im ersten (Länge des Arrays (len (h )) / Eulers Zahl (bis zu 5 Dezimalstellen)) dieses Arrays und gibt diesen Wert als "k" zurück. Außerdem ist "n" der Maximalwert im Rest des Arrays. Schließlich ist der von der Funktion zurückgegebene Wert der Maximalwert in einem Array, das sowohl "k" als auch "n" enthält.

Hinweis: Die max()Funktion von Python ist die Komplexität von O (n).

Unten finden Sie eine besser lesbare Nicht-Code-Golf- Version des obigen Codes, die ein zufälliges, eindeutiges Array mit 10 Elementen enthält, um zu bestätigen, dass es funktioniert:

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
quelle
Willkommen bei PPCG! Sie können Ihre Importe durch Kommas trennen. Außerdem müssen Sie das Array nicht selbst generieren, sodass Sie diesen Teil des Codes entfernen können (Sie müssen das Array einfach als Parameter für die Funktion haben)
Nathan Merrill
@ NathanMerrill Ja, ich habe darüber nachgedacht, aber dann dachte ich, dass es dir nicht wirklich gefällt, aber jetzt, wo ich weiß, dass das wirklich egal ist, werde ich meine Antwort bearbeiten. Vielen Dank auch für den Tipp zum Komma-Trennen meiner Importe. Das hatte ich total vergessen!
R. Kap
Weitere Tipps: Sie haben viele nicht benötigte Leerzeichen (nach Kommas, zwischen Gleichheitszeichen). Sie benötigen am Ende auch keine print-Anweisung.
Nathan Merrill
@ NathanMerrill Danke für die Tipps! Ich werde das im Hinterkopf behalten, wenn ich mehr Code-Golf spiele! :)
R. Kap