YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Portuguese, Brazilian subtitles

← 03x-02 Maximum Solution

03x-02 Maximum - Solução

Get Embed Code
3 Languages

Subtitles translated from English Showing Revision 2 created 03/04/2013 by Lucilia Figueiredo.

  1. Nosso objetivo aqui é encontrar o elemento da lista não vazia l que maximiza
  2. o valor retornado por f,
  3. e eu vou simplesmente chamar esta função findmax(f,l).
  4. Uma maneira de fazer isso é guardar o melhor valor encontrado até o momento
  5. e então caminhar ao longo da lista e verificar se você pode encontrar outro melhor.
  6. Vou usar 2 nomes de variáveis, bastante descritivos: best_element_sofar
  7. e best_f_value_sofar.
  8. Então, o que eu quero fazer é iterar sobre todos os possíveis elementos da lista,
  9. sem escapar além do final,
  10. e, para cada elemento, chamar a função passando este elemento como argumento.
  11. Se eu ainda não tenho nenhum valor, ou se o valor que obtive é melhor que
  12. o melhor valor que eu obtive até então, parabéns! --
  13. o elemento corrente é promovido a novo campeão!
  14. E eventualmente, quando terminamos,
  15. simplesmente retornamos o melhor elemento encontrado.
  16. Eu recomendo que você construa alguns pequenos casos de teste primeiro,
  17. de modo que possa ter uma idéia de como funciona, antes de partir para
  18. este teste maior.
  19. Bem, vamos ver se eu consegui escrever este programa Python sem erros.
  20. Isso não é muito óbvio.
  21. Oh! tem um erro!
  22. Ele retornou bet_element_sofar.
  23. O erro está aqui no final: a identação não casa corretamente --
  24. isso ocorre na linha 13.
  25. Vamos voltar lá atrás e... está correto --
  26. eu preciso de mais um espaço aqui.
  27. Eu não sei se você já tinha percebido isso.
  28. Por alguma razão, a tabulação não estava correta,
  29. mas agora já está. Vamos tentar de novo.
  30. Ah! Agora o programa retorna "quick", que é o que esperávamos.
  31. Este é o elemento da lista que tem maior comprimento.
  32. Vamos tentar outro teste.
  33. Tente [5, -6, 3, 2], e desta vez queremos encontrar o elemento com maior valor absoluto,
  34. que deve ser -6.
  35. E é isso! Wow!
  36. Parece que findmax funciona bem... mas de fato não:
  37. existe um erro na implementação.
  38. Nos teste que eu fiz até agora, os elementos estão em uma ordem aleatória.
  39. Mas queremos testar para todos os casos possíveis e, para algo que tem uma lista como entrada,
  40. os casos possíveis são lista ordenada, lista em ordem reversa e em ordem aleatória.
  41. Tentamos 2 testes, mas em ambos a lista era, de certa forma, aleatória.
  42. E quando você está testando programas que envolvem listas,
  43. deve tentar em ordem, em ordem reversa e aleatória.
  44. Então, vamos tentar isso para uma lista em ordem reversa e ver se obtemos a resposta correta.
  45. Deveria ser 4, e de fato é! Excelente.
  46. Agora vamos tentar em ordem e ver se obtemos a resposta correta.
  47. Deveria ser -4 -- oh! é -3! Essa não é a resposta correta. Hummm. O que devemos fazer?
  48. Existe um erro em nosso código em algum lugar, e podemos não saber onde.
  49. Uma das primeiras maneiras de descobrir o que está acontecendo é chamada de
  50. depuração usando comandos print.
  51. Então, o que eu vou fazer é modificar o meu programa de modo que, toda vez que eu entre nesse loop,
  52. eu imprima o valor de i, de modo a acompanhar melhor as coisas.
  53. Aqui, estamos tentando imprimir elt e o f_value.
  54. Vamos ver se eu consigo adicionar os comandos print de depuração sem cometer nenhum erro.
  55. Ok, parece bom.
  56. Então,começamos com i igual a 0 e o elemento aí é 1 e o f_value é 1, parece ok.
  57. Então, i é 1, elt é 2, f_value é 2 -- ok.
  58. Então, i é 2, elt é 3, f_value é 3.
  59. Bem, isso me convence de que estamos realmente chamando o valor absoluto,
  60. mas o que eu esperava ver era -4, e parece que eu nunca obtenho isso.
  61. Então, isso me sugere que i não cresce suficientemente.
  62. Bem, sabemos que i varia sobre cada elemento nesta faixa,
  63. portanto, vamos imprimir isso para entender melhor --
  64. range(len(l)-1).
  65. Então, agora, aqui no início, isso nos diz que i varia apenas na faixa 0, 1 e 2,
  66. mas de fato queremos tque seja 0, 1, 2, 3.
  67. E de fato podemos tornar isso ainda mais óbvio.
  68. Vamos usar uma lista ainda mais simples, para a qual o programa falha.
  69. Agora, a lista e os índices dos elementos são iguais.
  70. Queremos obter a resposta 3,
  71. mas se olhamos aqui,
  72. i varia apenas na faixa apenas 0,1,2 ; 0,0,0 ; 1,1,1 ; 2,2,2.
  73. 2 é o melhor e portanto retornamos isso.
  74. Então não estamos pegando o último elemento.
  75. Então existe alguma coisa errada aqui,
  76. e eu posso adivinhar que, como está faltando o último elemento,
  77. é este -1 -- não precisamos subtrair 1.
  78. Muitas pessoas tendem a subtrair 1, já que uma lista em Python começa de 0
  79. e não queremos ir além do fim da lista.
  80. Aqui, vamos simplesmente imprimir range(4) para nos convencer de que é 0,1,2,3.
  81. Yep, então range(4) é 0, 1, 2, 3.
  82. Agora i varia na faixa 0,1,2,3 e obtemos a resposta que esperávamos.
  83. Então, vamos voltar ao problema que nos foi dado:
  84. ["Barbara", "Kingsolver", "Wrote", "the", "Poisonwood", "Bible"]
  85. e esperamos obter ou "Kingsolver" ou "Poisonwood" como resposta,
  86. supondo que eu sei contar.
  87. "Barbara" é 7, "Kingsolver" é 10, "Wrote" é 5, "The" é 3, "Poisonwood" é 10.
  88. Obtemos "Kingsolver" afinal, que é uma resposta correta.
  89. Mas temos todos esses print de depuração, e se o problema não precisa disso,
  90. devemos removê-los antes de submeter a solução, para que isso não entre como parte da resposta
  91. e faça com que nosso programa fique errado.
  92. Agora simplesmente retornamos "Kingsolver".