Return to Video

22-24 Faster Fibonacci Solution

  • 0:00 - 0:03
    Portanto esta é uma maneira de definirmos a solução Fibonacci de forma iterativa
  • 0:04 - 0:08
    Vamos evitar toda a redundancia computacional controlando à maneira que avançamos
  • 0:08 - 0:11
    E vamos ter duas variáveis. E eu vou fazer isto de uma forma
  • 0:11 - 0:14
    ligeiramente estranha, e a razão para isso vai ficar clara em seguida
  • 0:14 - 0:15
    A forma como irei resolver dá-nos a resposta correcta
  • 0:15 - 0:19
    quando n é 0 e quando n é 1, sem necessitar de cases especiais
  • 0:19 - 0:23
    Em vez de controlarmos as últimas duas, eu vou controlar
  • 0:23 - 0:27
    a actual e da imaginária que se dará a seguir.
  • 0:27 - 0:30
    E nós sabemos que os primeiros números de Fibonacci
  • 0:30 - 0:34
    sao 0 e 1, por isso a variável current é 0
  • 0:34 - 0:37
    e a seguinte, que iremos chamar after é 1.
  • 0:37 - 0:40
    Portanto essa é aquela depois da que estamos actualmente a usar
  • 0:40 - 0:42
    e agora temos um loop,
  • 0:42 - 0:45
    por isso o nosso i irá de 0 a n.
  • 0:45 - 0:48
    Nós estamos à procura do número de Fibonacci n, o que significa
  • 0:48 - 0:51
    que queremos começar no 0. E o valor current
  • 0:51 - 0:55
    do valor de Fibonacci de 0 e a seguir o valor
  • 0:55 - 0:57
    de Fibonacci de 1, e à medida que o loop continua
  • 0:57 - 1:00
    iremos actualizar esses valores. E queremos actualizá-los
  • 1:00 - 1:04
    seguindo a regra recursiva, o que significa que o novo valor
  • 1:04 - 1:07
    da variável current, é o o valor actual da after. E o novo valor
  • 1:07 - 1:09
    da variável after, é a soma destas duas variáveis;
  • 1:09 - 1:12
    current mais after. Nós podemos fazer isto com uma
  • 1:12 - 1:16
    atribuição múltipla, não sendo preciso uma variável temporária.
  • 1:16 - 1:20
    Nós podemos atribuir a current e a after aos seus novos valores.
  • 1:20 - 1:23
    O novo valor de current, é o valor actual de after, e o novo valor
  • 1:23 - 1:29
    de after é o valor de current mais after. Então é aqui que
  • 1:29 - 1:32
    a atribuição múltipla entra. Se nós não usarmos
  • 1:32 - 1:34
    uma atribuição múltipla, teríamos de usar uma variável temporária
  • 1:34 - 1:36
    para guardar o valor de uma das variáveis enquanto faríamos as
  • 1:36 - 1:40
    atribuições. Mas com atribuições múltiplas, conseguimos obter
  • 1:40 - 1:42
    estes valores primeiro e depois fazer a atribuição dos mesmos às
  • 1:42 - 1:45
    duas variáveis do lado esquerdo. E isto é tudo o que precisamos. E
  • 1:45 - 1:48
    depois do loop, nós retornamos o valor de current,
  • 1:48 - 1:52
    que é o valor actual do número de Fibonacci se estivermos à procura do
  • 1:52 - 1:55
    número n de Fibonacci. Vamos tentar isto então. Portanto nós
  • 1:55 - 2:00
    deveríamos ser capazes de ver o Fibonacci de 0, e o resultado
  • 2:00 - 2:03
    deveria ser 0. E isso é o que obtemos e porque
  • 2:03 - 2:04
    esse é o valor de current. Quando o intervalo é de 0 a 0, n
  • 2:04 - 2:06
    nós não passamos pelo loop.
  • 2:06 - 2:10
    Agora obtermos o valor 1. Vamos verificar o Fibonacci de 1,
  • 2:10 - 2:17
    e compilamos, e obtermos 1, o que também é o
  • 2:17 - 2:21
    que esperávamos. E nós obtivemos isso porque entrámos no loop uma vez, atribuindo
  • 2:21 - 2:25
    o valor de after, que começou a 1 na current e é isso que retornamos
  • 2:25 - 2:29
    como o valor de current. E continuamos por assim adiante, vamos tentar o Fibonacci de 2.
  • 2:32 - 2:36
    Que também é 1, como esperávamos, e o Fibonacci de 3
  • 2:36 - 2:40
    deverá ser 1 mais 1, que nos dá 2 e assim por diante.
  • 2:43 - 2:46
    Okay, parece que isto funciona. Nós tentámos
  • 2:46 - 2:49
    alguns simples. Vamos tentar o Fibonacci de 33.
  • 2:49 - 2:53
    Estimamos no quiz anterior, que para obter o Fibonacci de 36,
  • 2:53 - 2:56
    precisaríamos do Fibonacci de 33
  • 2:56 - 3:01
    usando a definição recursiva anterior. Então por que
  • 3:01 - 3:02
    demorou tanto para o código executar?
  • 3:02 - 3:07
    Qual é então o valor do Fibonacci de 33? E é isso que é,
  • 3:07 - 3:10
    3 milhões e meio de calls.
  • 3:10 - 3:13
    Portanto, mesmo com um processador que fizesse um bilião de instruções,
  • 3:13 - 3:16
    por segundo, fazer 3,5 milhões de call recursivas demora
  • 3:16 - 3:19
    algum tempo. Cada call, é muito mais que apenas
  • 3:19 - 3:22
    uma instrução, são centenas de instruções. E isto toma
  • 3:22 - 3:25
    o tempo suficiente para que não consigamos ver o resultado.
  • 3:25 - 3:30
    E não foram apenas aquelas call do Fibonacci de 33 para o Fibonacci de 2,
  • 3:30 - 3:32
    tínhamos todas aquelas coisas a fazer para conseguir o Fibonacci de 36
  • 3:32 - 3:37
    Mas vamos la ver agora ,que temos a nossa definição
  • 3:37 - 3:41
    mais rápida de Fibonacci que não faz toda aquelas coisas em duplicado,
  • 3:41 - 3:45
    se conseguimos obter o Fibonacci de 36 e se dá-nos este valor,
  • 3:45 - 3:50
    indicando que existam 15 milhões de coelhos após 3 anos
  • 3:50 - 3:55
    usando o modelo de Fibonacci. Vamos tentar após 5 anos,
  • 3:55 - 4:01
    passando 60 meses, e pomos isto a começar
  • 4:01 - 4:03
    com um número enorme.
  • 4:03 - 4:07
    De forma a tentar relacionar isto, vamor olhar
  • 4:07 - 4:09
    para quanto tempo demoraria para a massa de todos
  • 4:09 - 4:12
    os coelhos que nasceram exceder a massa da Terra.
  • 4:14 - 4:23
    A massa da Terra é 5.9772 * 10 elevado a 24.
  • 4:23 - 4:28
    isto em kilogramas, e eu estou a usar a notação em tempo.
  • 4:28 - 4:32
    Isto dá-nos uma potência de... portanto isto é 10 elevado a 24, o que é
  • 4:32 - 4:36
    uma forma de escrever 5,9 * 10 elevado a 24 kilogramas
  • 4:36 - 4:40
    so para demonstrar a notação das potências,
  • 4:40 - 4:43
    isto é 2 elevado a 10, por isso vamos ver o resultado sendo
  • 4:43 - 4:45
    1,024. É o que obtemos multiplicando por 2
  • 4:45 - 4:48
    vezes 2 vezes 2... 10 vezes. Aqui estamos a multiplicar
  • 4:48 - 4:53
    10 por si mesmo durante 24 vezes, e esta é uma boa
  • 4:53 - 4:56
    estimativa da massa da Terra. Agora
  • 4:56 - 4:59
    para saber quantos meses demora para a massa dos coelhos
  • 4:59 - 5:01
    exceder a massa da Terra,
  • 5:01 - 5:03
    iremos necessitar de loop for. Nós iremos fazer um loop
  • 5:03 - 5:08
    dos números de Fibonacci até obtermos um número que exceda
  • 5:08 - 5:12
    a massa da Terra. E teremos também de decidir qual vai ser a massa dos coelhos, e
  • 5:12 - 5:15
    para isso vou assumir que um coelho pesa 2 kilogramas
  • 5:15 - 5:21
    E essa é uma boa estimativa para quão pesado um coelho é
  • 5:21 - 5:23
    Isso assumindo, claro, que um coelho bem alimentado
  • 5:23 - 5:25
    como os que temos hoje em dia, nao como os que se espalham tão
  • 5:25 - 5:29
    rápido no modelo de Fibonacci que não sugere que sejam.
  • 5:29 - 5:34
    Portanto iremos escrever um loop para quando a massa
  • 5:34 - 5:37
    dos coelhos exceda a da Terra.
  • 5:37 - 5:39
    Iremos começar com n igual a 1,
  • 5:39 - 5:45
    e iremos continuar até ao Fibonacci de n exceder a massa da Terra.
  • 5:45 - 5:52
    Portanto, enquanto tivermos o Fibonacci de n vezes a massa dos coelhos
  • 5:52 - 5:55
    o Fibonacci de n dár-nos-à o número de coelhos
  • 5:55 - 5:57
    no mês final, vezes a massa dos coelhos
  • 5:57 - 5:58
    e enquanto for menor
  • 5:58 - 6:01
    que a massa da Terra, a Terra estará a salvo para
  • 6:01 - 6:03
    os humanos, ou pelos menos restará
  • 6:03 - 6:06
    algum espaço para os humanos.
  • 6:06 - 6:08
    E todas as vezes que passa no loop
  • 6:08 - 6:11
    iremos incrementar o n em 1. Para que ao fim de cada loop
  • 6:11 - 6:12
    tenhamos o valor de n imprimido
  • 6:12 - 6:16
    veremos que é que obtermos, e vamos também imprimir
  • 6:16 - 6:19
    o valor do Fibonacci de n, para ver quão grande o Fibonacci
  • 6:19 - 6:24
    de n é. Vamos continuar no loop
  • 6:24 - 6:27
    até que o Fibonacci de n vezes a massa dos coelhos
  • 6:27 - 6:29
    seja menor que a massa da Terra.
  • 6:29 - 6:32
    E assim que o loop parar significa que excedemos a
  • 6:32 - 6:34
    massa e iremos ver qual o resultado.
  • 6:34 - 6:39
    Vamos tentar executar e ver qual o resultado.
  • 6:39 - 6:42
    O resultado de n é 119, portanto so irá levar 119 meses, ou
  • 6:42 - 6:45
    menos de 10 anos, até que a massa dos coelhos exceda
  • 6:45 - 6:49
    a da Terra. E este é o número de coelhos
  • 6:49 - 6:51
    que teríamos na altura. Um número assustador, deveríamos
  • 6:51 - 6:54
    ter muito medo de todos estes coelhos. A boa notícia
  • 6:54 - 6:58
    é que o modelo de Fibonacci, não é correcto. Ou seja,
  • 6:58 - 6:59
    uma abstracção matemática para a
  • 6:59 - 7:02
    reprodução de coelhos. Coelhos reais morrem em algum
  • 7:02 - 7:05
    ponto no tempo, e mesmo que haja tantos coelhos,
  • 7:05 - 7:07
    nós não temos comida suficiente, portanto eles não continuariam a crescer
  • 7:07 - 7:11
    como os números de Fibonacci e dominarem o planeta.
  • 7:11 - 7:14
    Portanto deveríamos ter medo se o modelo de Fibonacci fosse correcto.
  • 7:14 - 7:18
    Levaria apenas 10 anos até que os coelhos dominassem o planeta,
  • 7:18 - 7:22
    e pesariam mais do que a própria Terra. A boa notícia, é que não
  • 7:22 - 7:25
    é um modelo correcto de como os coelhos se reproduzem, e que
  • 7:25 - 7:27
    não vivem para sempre, e uma vez que existam muitos
  • 7:27 - 7:28
    coelhos, eles começam a ficar sem comida.
  • 7:28 - 7:32
    Por isso param de reproduzir e de sobreviverem.
タイトル:
22-24 Faster Fibonacci Solution
概説:

more » « less
Video Language:
English
Team:
Udacity
プロジェクト:
CS101 - Intro to Computer Science
Duration:
07:32

Portuguese subtitles

改訂 Compare revisions