Entrevista com Fibonacci

O cálculo da série Fibonacci é uma tarefa algorítmica clássica, porque é frequentemente dada em entrevistas quando eles querem verificar se o candidato, em princípio, é pelo menos de alguma forma capaz em algoritmos. Suponha que você seja o mesmo candidato. Você recebeu a tarefa: em JavaScript, escreva uma função fib(n) que retorne o enésimo número de Fibonacci. Consideramos que o número zero de Fibonacci é zero. A validação do argumento não é necessária. Que opções você tem?

1. Para ser mais fácil, e as pessoas o alcançarão.

A solução mais simples é um ciclo banal.

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

Uma piada. Obviamente, você não precisa escrever assim - a menos que não seja entrevistado para a posição de ofuscador em tempo integral.

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

Você está ficando sem cupons variáveis? cypok

Ok, ok, para maior legibilidade, vamos escrever o seguinte:

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

Esta é uma opção clássica, simples e elegante. Mas talvez você queira demonstrar seu conhecimento de alguns outros conceitos? Por exemplo ...

2. Para entender a recursão, você deve entender a recursão

Por exemplo, sim, você pode demonstrar que pode fazer recursão. Por exemplo, assim:

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

Lembre-se desta opção. Não vale a pena fazer isso. Não deveria ser. Isso é impossível. Nunca. Isso é pior do que chutar filhotes e é comparável a um pequeno holocausto.

Você pode perguntar o porquê. Nesse caso, basta executar esse código e tentar calcular, digamos, o número de Cinqüenta Fibonacci. Eu acho que você sentirá um certo atraso. Uma piada. Acredito que se você executar esse código não em um supercomputador, simplesmente não esperará o resultado. Apesar do fato de que o código simples e não recursivo dos exemplos anteriores contará o quinquagésimo membro da sequência de Fibonacci mais rapidamente do que você tem tempo para dizer a palavra "cinquenta" ou qualquer sílaba.

Expressa na linguagem grosseira da notação O, essa solução possui uma complexidade temporal de O (e ⁿ ). Ou seja, o tempo de execução dessa função aumenta exponencialmente com o aumento de n. Ou seja, quando n aumenta, o tempo de execução aumenta. Grosso modo, se fib(45) teve que esperar uma hora, então fib(46) esperou duas horas, fib(47) - 4 horas e assim por diante. Eu mastigo com tantos detalhes que todo leitor, mesmo um compositor que primeiro tentou escrever scripts, conseguiu perceber o horror da situação.

Isso está correto, mas muito rude. Você pode obter uma estimativa mais precisa do número de chamadas para a função ~ (1 + sqrt (5)) fib (n) e a observação bonita “Para calcular o número de Fibonacci usando o método recursivo ingênuo, você precisa de 3,2 vezes mais chamadas para a função do que o próprio número de Fibonacci.” Taus

E temos outro método para calculá-lo. Você só precisa executar o método recursivo ingênuo, contar o número de chamadas de função e dividir por 3,2! Cerberuser

Se você precisar resolver recursivamente esse problema durante uma entrevista, é mais provável que isso seja uma armadilha. Uma recursão "correta" trabalhando em tempo linear pode ser, por exemplo, assim:

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

Resumindo: apesar do fato de os números de Fibonacci serem um exemplo clássico de recursão em livros didáticos, na realidade esse não é o caso mais conveniente para aplicar recursão. Mas você pode tentar mostrar um pouco mais de conhecimento.

3. Função memorial

Existe uma maneira mágica de transformar uma solução monstruosamente ineficaz do último parágrafo em uma solução potencialmente muito rápida (embora não sem problemas). O nome dele é memorização. E se você fala russo, lembramos dos resultados de chamadas anteriores, em vez de calculá-las novamente.

Basicamente, não podemos mudar nada dentro dessa solução - basta adicionar uma função de empacotamento de memoize . Aqui, para maior clareza, uso sua versão simplificada para uma função com um único argumento.

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Voila! Agora, a função fib tem acesso ao objeto de cache através do fechamento. Se for chamado com um argumento que não foi encontrado anteriormente, o valor calculado será armazenado no cache . Com novas chamadas de função com o mesmo argumento, o valor não precisa ser recalculado, ele será simplesmente retirado do cache. O principal problema da função “velha” de fib velha era que os mesmos valores nela eram recalculados várias vezes. Por exemplo, para calcular fib(45) era necessário calcular f(44) uma vez, duas vezes f(43) , três vezes f(42) , cinco vezes f(41) e assim por diante.


Portanto, agora os valores anteriores serão calculados uma vez e quando forem solicitados novamente - apenas retirados do cache. Você pode imaginar com que rapidez podemos calcular o quadragésimo quinto número de Fibonacci? Sério, que horas você acha?

De fato - um pouco mais lento. Eu cometi deliberadamente um erro clássico, geralmente cometido ao memorizar funções recursivas. Quando fib(45) chamado “under the hood”, oldFib(45) é chamado, que chama oldFib(44) e oldFib(43) para suas necessidades ... Você sente o problema? A seguir, já existem chamadas para uma função regular e não memorizada. Obviamente, ao chamar fib(45) novamente, obtemos instantaneamente o resultado do cache - no entanto, a primeira chamada não acelerou nada. Para corrigir isso, você ainda precisa ficar oldFib embaixo da chave inglesa:

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Ótimo! Agora, a primeira chamada para fib(45) funcionará a uma velocidade comparável à versão com um loop. E desafios adicionais geralmente funcionam em tempo constante ... Opa! Mais uma vez enganado. Obter o valor da propriedade de um objeto por chave é uma operação rápida, mas ainda assim O (1) é apenas em média, no pior caso, pode se degradar em O (n). Para torná-lo muito bom, no nosso caso, podemos alterar o tipo de cache de um objeto para uma matriz.

Obviamente, não se deve esquecer que a memorização requer memória. E enquanto reduzimos a complexidade do tempo, a complexidade da memória aumenta de O (1) para O (n).

De que outra forma podemos nos exibir? Por exemplo, demonstrando seu profundo conhecimento de matemática

4. Sr. Binet

Existe uma ciência especial e maravilhosa sobre como transformar relacionamentos de recorrência em fórmulas explícitas. Aqui não entraremos em detalhes. Diremos apenas que, para números de Fibonacci, usando argumentos bastante simples, podemos derivar a seguinte fórmula, conhecida como fórmula de Binet:

$$

$$F_n = \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n - \ left (\ frac {1 - \ sqrt5} {2} \ right) ^ n} {\ sqrt5}$$

No entanto, é uma linguagem matemática, escrevemos em JavaScript:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

Vamos dirigir nos primeiros números. Ótimo, tudo parece funcionar. Aqui está 13, aqui está 21, aqui está 34, aqui está ... 54.9999999999999999?

Sim, é claro, esse resultado é lógico. A fórmula de Binet é matematicamente precisa, mas o computador opera com frações de precisão finita, e um erro pode se acumular durante as operações com elas, o que aconteceu neste caso. No entanto, podemos corrigi-lo. Sabendo que a subtração no numerador sempre será pequena em magnitude, podemos simplificar a fórmula para o seguinte estado:

$$

$$F_n = \ left \ lfloor \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n} {\ sqrt5} \ right \ rceil$$

Aqui, colchetes estranhos inacabados significam o número inteiro mais próximo, ou seja, arredondamento. Reescreva nosso código:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

Sim, isso é muito melhor. Podemos ver 55 e 89, e até o meu número favorito de Fibonacci é 144 (o que eu amo porque é igual a doze ao quadrado). Tudo ficará bem até o número 76. Que deve ser igual a 3416454622906707, e nossa função calculará 3416454622906706. Como o problema da precisão limitada de números fracionários não desapareceu, apenas o aprofundamos e esperamos que ele não surgisse. Como mostra este exemplo, eles esperavam em vão.

De fato, podemos fazer outra coisa para salvar esse método. Mas mais sobre isso abaixo. Enquanto isso - brincadeiras à parte. Vamos falar sobre o método duro, incondicional e brutal.

5. Siga o coelho branco.

Eles dizem que se você tiver um problema e a ideia lhe ocorreu que você pode resolvê-lo com expressões regulares, agora você tem dois problemas. Matrizes são expressões regulares, pelo contrário. Muitos problemas, se reformulados na linguagem das matrizes, são resolvidos simplesmente por eles mesmos.

Quanto aos números de Fibonacci, para eles na linguagem matricial, você pode escrever esta identidade óbvia:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} \ begin {pmatrix} F_ {n - 1} \\ F_n \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n +1} \ end {pmatrix}$$

Ou seja, se pegarmos um par de números consecutivos de Fibonacci e os multiplicarmos por uma matriz tão direta, obteremos o seguinte par. E a conclusão lógica segue disso: se pegarmos um par de zero e primeiro número de Fibonacci, isto é, zero e um, e os multiplicarmos por essa matriz até a enésima potência, obteremos um par de enésimo e en mais o primeiro Fibonacci. Ou seja, falando humanamente:

$$

$$\ begin {pmatrix} 0 e 1 \\ 1 & 1 \ end {pmatrix} ^ n \ begin {pmatrix} 0 \\ 1 \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n + 1} \ end {pmatrix}$$

Você pode simplificar isso um pouco mais abandonando vetores. De fato, todos os valores necessários estão contidos na própria matriz:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_ {n} \\ F_ {n} e F_ {n + 1 } \ end {pmatrix}$$

Ótimo, não é? Resta entender o que significa harmonia, se ele não é uma filarmônica. Quero dizer - por que essas dificuldades são inesperadas? E a resposta é simples - exponenciação rápida.

Quantas multiplicações elementares são necessárias para calcular, digamos, 2 ¹⁰ ? Uma pessoa normal dirá nove. Duas e duas - quatro. Duas vezes quatro - oito. Duas vezes oito são dezesseis. E assim por diante Uma pessoa astuta dirá isso quatro.

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

O programador dirá. que ele se lembra desse número de cor, e nada precisa ser multiplicado. No entanto, discutimos os problemas de memorização acima.

Portanto, uma rápida exponenciação também é aplicável às matrizes e, portanto, permite reduzir a complexidade do tempo assintótico de nossa função de O (n) para O (log n). E isso é muito legal - a menos que, é claro, essa complexidade seja realmente tão importante para nós. Vamos escrever o código:

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

Portanto, obtivemos o algoritmo mais rápido no oeste selvagem. E, ao contrário da maioria dos anteriores, pode ser demonstrado de maneira não irônica em uma entrevista. E em alguns lugares com capacidade matemática, isso é esperado de você.

PS

Prometi uma observação sobre como salvar um método baseado na fórmula Binet. A resposta está neste meu artigo. Lá, para as necessidades da economia nacional, escrevi uma classe especial, a raiz de cinco números racionais, que, sem perda de precisão, pode armazenar os resultados de operações aritméticas em números inteiros e uma raiz de cinco. Você pode fazer essa aula, complementá-la com o método de arredondamento e usá-la para procurar números de Fibonacci usando a fórmula Binet. E então injete óxido nitroso aplicando exponenciação rápida.

E o mais interessante: se você observar cuidadosamente quais números serão obtidos no processo, quais operações serão executadas, ficará claro que esse método é a mesma multiplicação de matrizes, somente sob uma fachada diferente. A única diferença é se armazenamos números em matrizes bidimensionais ou nos campos de um objeto de uma classe especial.

Isso é tudo. Se você acha que perdi outras maneiras interessantes de encontrar números que ninguém precisa, não deixe de escrever sobre isso nos comentários.

Também existe um método como duplicação rápida . Funciona como multiplicação de matrizes em O (log), mas com uma constante menor em assintóticos (e na prática). Resumidamente, então duas fórmulas são usadas lá, dependendo da qual se pode reverter rapidamente para índices duas vezes mais baixos recursivamente:

F _2n = F _n * (2 * F _{n + 1} - F _n )
F _{2n + 1} = F _n ² + F _{n + 1} ²

A implementação, a propósito, é bastante compacta.

Comparação da velocidade de diferentes métodos

just_maksim