Resolver o problema do secretário

13

O problema do secretário é um famoso problema descrito da seguinte maneira:

  1. Você precisa de uma nova secretária
  2. Você tem N candidatos que você pode entrevistar um de cada vez
  3. Você é capaz de pontuar cada candidato após a entrevista. Seu sistema de pontuação nunca dará a dois candidatos a mesma pontuação
  4. Depois de entrevistar um candidato, você deve dar um "sim" ou "não" imediato
  5. Você deseja que o candidato com a maior pontuação

A solução é entrevistar os primeiros floor(N/e)candidatos e, em seguida, aceitar o primeiro candidato com uma pontuação mais alta do que todos os candidatos anteriores. Se nenhum dos candidatos for superior, retorne o último candidato. Curiosamente, isso fornece o 1/epercentual mais alto de candidatos . erefere-se ao número de Euler . Para obter o valor de e, você pode usar um built-in,log ou codificá-lo com pelo menos 5 pontos decimais.

Entrada:

Uma matriz não vazia de números inteiros não negativos únicos, no máximo 2^31-1.

Resultado:

Um número inteiro representando o candidato escolhido. Para ser claro, o algoritmo é:

  1. Encontre o elemento máximo nos primeiros floor(N/e)elementos da matriz.
  2. Itere pelos elementos restantes e retorne o primeiro elemento que é maior que o máximo encontrado na etapa 1.
  3. Se nenhum dos elementos for maior, retorne o último elemento.

Por exemplo, diga que sua matriz era [2,7,4,3,9,20], então N = 6e floor(N/e) = 2. Os 2 primeiros elementos da matriz são [2,7]. O máximo de [2,7]é 7. Os elementos restantes são [4,3,9,20]. O primeiro elemento que é maior que 7é 9, então retornamos 9.

Casos de teste:

[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

Sua solução deve ser O(n), onde nestá o comprimento da matriz. Se seu idioma possui um valor interno que encontra o máximo de uma matriz, você pode assumir que a função aceita O(n)(e espero que sim).

Aplicam-se brechas padrão, e este é um , portanto, faça a resposta mais curta no seu idioma favorito!

Nathan Merrill
fonte
1
O que edeve ser usado?
22316 afuous
2
@voidpigeon eu presumo que é en.wikipedia.org/wiki/E_(mathematical_constant)
Doorknob
1
Ah, agora eu entendo como o algoritmo funciona. Eu pensei que seu segundo parágrafo significava que você nunca entrevista os candidatos depois da palavra (n / e).
Maçaneta
1
Perguntei especificamente porque em alguns idiomas, é mais curto para definir uma variável com 5 pontos decimais de precisão do que é realmente usar o builtin e(por exemplo, Python, onde e=2.71828é menor do que import math;math.E)
Mego
1
Nota: `1 / e por cento do tempo 'seria muito ruim. É um probabilty de 1 / e, que é aproximadamente 37% das vezes
edc65

Respostas:

4

Gelatina, 13 bytes

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

Definitivamente um algoritmo O (n) , espero que uma implementação O (n) . Experimente online!

Como funciona

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

CJam, 20 bytes

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

Funciona de maneira semelhante à sugestão de Dennis.

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
A Simmons
fonte
$W=não é executado em tempo linear.
22416 Dennis
Urgh, você está certo. Existe alguma maneira melhor de encontrar o máximo no CJam que você conhece?
A Simmons
1
:e>(por reduzir máxima)
Dennis
@Dennis Thanks!
A 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;}

Recuado:

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

Menos golfe

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

Teste

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

Ruby, 64 bytes

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}
úmido
fonte
2
@Doorknob Ele percorre os elementos do primeiro andar (N / e) uma vez para encontrar o máximo e depois percorre o restante da lista no pior caso, comparando cada elemento ao máximo. Existe apenas uma comparação por elemento em ambas as partes.
22316 afuous
Ah, está certo. Eu interpretei mal e pensei que você estava encontrando o máximo em cada iteração.
Maçaneta
1
Na verdade, acho que ainda é O (n) se você apenas faz a.findno segundo passo, embora obviamente seja muito menos eficiente.
histocrat 22/03
1
Você pode usar (0...c)para um intervalo que exclua c.
histocrat
@histocrat Sim, deve ser O (2n) que é O (n)
Não que Charles
1

PARI / GP , 70 bytes

Isso pode ter problemas nas versões mais antigas do gp, quando fornecido um singleton, mas funciona pelo menos a partir da revisão 18487.

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

JavaScript (ES6), 79 bytes

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

Funciona porque findIndexretorna -1com falha, mas a.slice(-1)[0]retorna o último elemento da matriz, conforme desejado.

Neil
fonte
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

O usuário digita a matriz como uma lista, entre colchetes e vírgulas. Python 2'sinput() comando é conveniente aqui.

Independentemente de encerrarmos o processo com antecedência, contratamos a última pessoa que foi entrevistada.

mathmandan
fonte
1

Perl 6, 43 bytes

Eu acho que isso é O (n)

{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}
Teclas de atalho
fonte
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])

Basicamente, o que o acima faz é que, primeiramente, é necessária uma matriz fornecida, "h" , desde que inclua mais de 5 itens (por enquanto ...), encontre o valor máximo no primeiro (comprimento da matriz (len (h )) / Número de Euler (com 5 casas decimais)) itens dessa matriz e, em seguida, retorna esse valor como "k". Além disso, "n" é o valor máximo no restante da matriz. Finalmente, o valor retornado da função é o valor máximo em uma matriz que contém "k" e "n".

Nota: A max()função do Python é a complexidade O (n).

Abaixo está uma versão mais legível e sem código de golfe do código acima que possui uma matriz aleatória e exclusiva de 10 itens, para confirmar que funciona:

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
fonte
Bem-vindo ao PPCG! Você pode separar suas importações por vírgula. Além disso, você não precisa gerar a matriz sozinho, para poder remover essa parte do código (basta ter a matriz como parâmetro da função)
Nathan Merrill
@ NathanMerrill Sim, eu estava pensando em fazer isso, mas depois pensei que você realmente não iria gostar, mas agora que sei que isso realmente não importa, editarei minha resposta. Além disso, obrigado pela dica sobre vírgula que separa minhas importações. Eu tinha esquecido totalmente disso!
R. Kap
Outras dicas: Você tem muitos espaços em branco desnecessários (após vírgulas, entre sinais de igual Você não precisa de uma declaração de impressão no final também..
Nathan Merrill
@NathanMerrill Obrigado pelas dicas! Vou manter isso em mente, pois faço mais golfe com código! :)
R. Kap