So here, our goal is to find the element of the non-empty list "l" that maximizes
the return value of f.
and I'm just going to call this function findmax f of l.
Conceptually, one way to do this is to keep track of the best thing you've seen so far,
and then just walk over the list and notice if you ever see anything better.
I'm going to make 2 descriptive variable names--the best element I've seen so far
and the best f value I've seen so far,
and then what I want to do is iterate over all the possible elements in the list
without walking off the end,
and I'll pull out that element and call the function f on it.
If we either haven't seen anything good yet, or what we just saw is better than
the best thing we've seen previously, congratulations!
You, the current element, are promoted to the new champion,
and then eventually when we're done,
we just return the best element so far.
Now I personally recommend making small test cases at the beginning,
just so that we can get a feel for how it's going before we move to that big
Barbara Kingsolver thing.
Well, let's see if I managed to write this Python program without any mistakes.
This is actually not obvious.
Oh! There is a mistake.
It returned bestelementsofar.
Here's the error at the bottom--unindent does not match any outer indentation level.
This is on line 13.
Let's scroll back up and actually, I think, they are right.
I needed 1 more space there.
I don't know if you could see this before.
For some reason, it hadn't tabbed over the whole way, but now I've made it tab
over the whole way. So let's try again.
Ah! And now it returns "quick," which is what we expected.
That's the element of this list with the greatest length.
Let's try another test.
Try 5, -6, 3, and 2, and this time we want to find the element with the greatest absolute value.
That should be -6.
And it is! Wow!
Looks like findmax is really working out well, except that it's totally not.
There's actually a bug in this implementation.
So the test that I've been making--they're all in sort of random order.
You really want to try all the corner cases, and for something that takes a list as input,
corner cases to consider are in order, in reverse order, and random.
But we tried 2 tests, but they were both sort of in random order,
and when you're testing a program that involves lists,
you want to try in order, reverse order, and also random.
So let's try this on reverse order, and see if it gets the right answer.
Should be 4, and in fact, it is! Excellent.
Now let's try it on in order and see if it gets the right answer.
Should be -4--oh! It is -3. That's not the right answer. Hmm. What do we do?
There's a bug in our code somewhere, and we may not know where.
One of the first approaches to figuring out what's going on is called
print statement debugging.
So here what I'm doing is changing my program so that everytime we enter this loop,
we print out what the value of "i" is just to make sure that things are on track.
Here we're trying to print out the element and the f_value.
Let's go see if I can even add print debugging without something going wrong.
Alright, this looks pretty good.
So we start out when i is 0 and the element there is 1 and the f_value is 1. Looking good.
Then i is 1, the element is 2, f_value is 2. Good.
And then i is 2, the element is 3, the f_value is 3.
Well, this convinces me that we're actually calling the absolute value,
but the thing I was expecting to see was -4, and we never seem to get there.
So this suggests to me that i isn't getting high enough.
Well, we know that i is going over every element in this range,
so let's print that out to gain some understanding--
range(len(l)-1).
So now here at the beginning, it tells us that i is only ranging over 0, 1, and 2,
but we really want it to range over 0, 1, 2, 3,
and in fact, we can make this even super obvious.
Let's make an even simpler list that we're going to fail at.
Now the list and the element indices are the same.
We really want to get out the answer 3,
but if we look down here,
i only ranges over 0, 1, 2. 0, 0, 0. 1, 1, 1. 2, 2, 2.
2 is the best so we return it.
So we're not getting to this last element.
So there must be something wrong with this set,
and I'm guessing, since we're missing the last element,
that this -1--we don't really need to be subtracting 1.
Now many people are often tempted to subtract 1 because Python lists start at 0,
and you don't want to walk over the end.
You will just print out range 4 to satisfy ourselves that it's 0, 1, 2, 3.
Yep, so range(4)--0, 1, 2, 3.
Now i ranges over 0, 1, 2, 3, and now we're getting the answer we expect.
So now let's go back to the problem we were actually given,
["Barbara", "Kingsolver", "Wrote", "The", "Poisonwood", "Bible"],
and hopefully, will get either Kingsolver or Poisonwood out,
assuming I can count.
Barbara is 7. Kingsolver is 10. Wrote is 5. The is 3. Poisonwood is 10.
We end up with Kingsolver at the end of the day, which is a perfectly acceptable answer.
But we've got all of this print debugging, and if the problem doesn't call for that,
we should typically remove it before submitting, lest it be counted as part of our output
and cause us to get the problem wrong.
Now we just return Kingsolver.
ではfの戻り値を最大化する
空でないリストlの要素を探しましょう
この関数を“findmax(f,l)”と定義します
概念的には
“これまで出た中で最大のものを覚えておく”
また“リストをたどってよりよいものを探索する”
という方法をとります
変数名は “これまでで最高のもの”という意味の
“best_element_sofar”と
“最もよいfの値”という意味の
“best_f_value_sofar”です
ここではリスト内の要素を
最後まで繰り返し見ていきます
またここでは要素を取り出して
そこに関数fを呼び出します
適切な値が見つからない場合 または
戻り値がこれまでに見た最高のものより高ければ
おめでとうございます!
その要素は新しいチャンピオンに昇格しました!
そしてこれで完了です
これまでで最高の要素を返しました
個人的には最初に小さなテストケースを作ることを
おすすめします
例えば前回の文字列のような
大きなケースに移る前に
感触を確かめることができるからです
では私が間違えずにこのPythonプログラムを
書けたか見てみましょう
さあどうでしょうか
ああ! ここに間違いがあります
ここではbest_element_sofarと返していますが
インデントエラーがありました
“unindent does not match
any outer indentation level”とあります
これは13行目です
戻ってみましょう ああ間違っていますね
タブがもう1つ必要でした
皆さんは気づいていましたか?
何らかの理由でタブが正確に打てていませんでした
ここを直して再度トライしてみましょう
期待どおり“quick”と返されました
これがこのリストの最大の長さを持つ要素です
別のテストを試しましょう
5、-6、3、2です
今回は最大の絶対値を持つ要素を検索します
これは-6になるはずです
-6と出ました!
findmaxはうまくいっているようですが
実は違うのです
この実装にはバグがあります
私が作ったテストではリストは順不同です
インプットとしてリストをとる
コーナーケースを試してください
リストは正の順序か逆順か順不同のどれかです
これまで試した2つのテストは順不同でした
リストを含むプログラムをテストする時は
正の順序、逆順、順不同のすべてを試してください
では逆順で試して
正しい答えが出るか見てみましょう
4になるはずです
4になりました すばらしい
では正の順序で正しい答えが出るか見てみましょう
-4のはずですが-3です
これは正しい答えではありません どうしますか?
コードのどこかにバグがあり場所は不明です
これに最初に対処する方法の1つに
print文デバッグというものがあります
では毎回このループを入力する度にiの値が何かを
出力するようにこのプログラムを変更します
順調に進んでいるか確認するためです
ここでeltとf_valueを出力します
問題なくprint文デバッグを
追加できるか見てみましょう
大丈夫です とてもよさそうです
スタートはi=0でeltが1、
f_valueが1です よさそうです
そしてiが1、eltが2、f_valueは2です
いいですね
それからiが2、eltが-3、f_valueが3
ここまでで絶対値を呼び出していることを
確信できます
しかし私が探しているのは−4であり
このままではたどり着きそうにありません
これはiが十分に高い値に達していないことを
示しています
iはこの範囲の要素をすべてカバーしています
では理解を深めるために出力してみます
range(len(l)-1)
この最初の部分ではiが0、1、2しかカバーしません
しかし本当は0、1、2、3をカバーしたいのです
これをスッキリさせましょう
実はこのリストももっとシンプルにできます
これでリストと要素インデックスが
同じになりました
答えとして3を取得したいのですが ここを見ると
iの範囲は0、1、2だけです
下に続く行を確認すると
2がベストなのでそれを返します
この最後の要素は出てこないので
このセットは何かが間違っている可能性があります
最後の要素が欠けています
ここでは1を減算する必要はありません
Pythonのリストは0から始まるので
つい1を減算したくなりますが
“range(4)”とするだけで
0、1、2、3をカバーできるのです
見てください
range(4)=[0,1,2,3]ですね
そしてi ranges over[0,1,2,3]ですので
期待した答えが出ました
では文字列の問題に戻りましょう
“Barbara”、“Kingsolver”、“Wrote”、
“The”、“Poisonwood”、“Bible”です
これが信頼できればKingsolverかPoisonwoodの
どちらかが出るはずです
Barbaraが7、Kingsolverが10、Wroteは5
Theが3、Poisonwoodが10で
最後はKingsolverです
これは完璧に正しい答えです
しかしprint文デバッグを終え
問題のバグがもう現れない場合は
それが出力の一部であると誤解されないように
提出前にprint文を削除するべきです
今回はKingsolverのみが返されました
Nosso objetivo aqui é encontrar o elemento da lista não vazia l que maximiza
o valor retornado por f,
e eu vou simplesmente chamar esta função findmax(f,l).
Uma maneira de fazer isso é guardar o melhor valor encontrado até o momento
e então caminhar ao longo da lista e verificar se você pode encontrar outro melhor.
Vou usar 2 nomes de variáveis, bastante descritivos: best_element_sofar
e best_f_value_sofar.
Então, o que eu quero fazer é iterar sobre todos os possíveis elementos da lista,
sem escapar além do final,
e, para cada elemento, chamar a função passando este elemento como argumento.
Se eu ainda não tenho nenhum valor, ou se o valor que obtive é melhor que
o melhor valor que eu obtive até então, parabéns! --
o elemento corrente é promovido a novo campeão!
E eventualmente, quando terminamos,
simplesmente retornamos o melhor elemento encontrado.
Eu recomendo que você construa alguns pequenos casos de teste primeiro,
de modo que possa ter uma idéia de como funciona, antes de partir para
este teste maior.
Bem, vamos ver se eu consegui escrever este programa Python sem erros.
Isso não é muito óbvio.
Oh! tem um erro!
Ele retornou bet_element_sofar.
O erro está aqui no final: a identação não casa corretamente --
isso ocorre na linha 13.
Vamos voltar lá atrás e... está correto --
eu preciso de mais um espaço aqui.
Eu não sei se você já tinha percebido isso.
Por alguma razão, a tabulação não estava correta,
mas agora já está. Vamos tentar de novo.
Ah! Agora o programa retorna "quick", que é o que esperávamos.
Este é o elemento da lista que tem maior comprimento.
Vamos tentar outro teste.
Tente [5, -6, 3, 2], e desta vez queremos encontrar o elemento com maior valor absoluto,
que deve ser -6.
E é isso! Wow!
Parece que findmax funciona bem... mas de fato não:
existe um erro na implementação.
Nos teste que eu fiz até agora, os elementos estão em uma ordem aleatória.
Mas queremos testar para todos os casos possíveis e, para algo que tem uma lista como entrada,
os casos possíveis são lista ordenada, lista em ordem reversa e em ordem aleatória.
Tentamos 2 testes, mas em ambos a lista era, de certa forma, aleatória.
E quando você está testando programas que envolvem listas,
deve tentar em ordem, em ordem reversa e aleatória.
Então, vamos tentar isso para uma lista em ordem reversa e ver se obtemos a resposta correta.
Deveria ser 4, e de fato é! Excelente.
Agora vamos tentar em ordem e ver se obtemos a resposta correta.
Deveria ser -4 -- oh! é -3! Essa não é a resposta correta. Hummm. O que devemos fazer?
Existe um erro em nosso código em algum lugar, e podemos não saber onde.
Uma das primeiras maneiras de descobrir o que está acontecendo é chamada de
depuração usando comandos print.
Então, o que eu vou fazer é modificar o meu programa de modo que, toda vez que eu entre nesse loop,
eu imprima o valor de i, de modo a acompanhar melhor as coisas.
Aqui, estamos tentando imprimir elt e o f_value.
Vamos ver se eu consigo adicionar os comandos print de depuração sem cometer nenhum erro.
Ok, parece bom.
Então,começamos com i igual a 0 e o elemento aí é 1 e o f_value é 1, parece ok.
Então, i é 1, elt é 2, f_value é 2 -- ok.
Então, i é 2, elt é 3, f_value é 3.
Bem, isso me convence de que estamos realmente chamando o valor absoluto,
mas o que eu esperava ver era -4, e parece que eu nunca obtenho isso.
Então, isso me sugere que i não cresce suficientemente.
Bem, sabemos que i varia sobre cada elemento nesta faixa,
portanto, vamos imprimir isso para entender melhor --
range(len(l)-1).
Então, agora, aqui no início, isso nos diz que i varia apenas na faixa 0, 1 e 2,
mas de fato queremos tque seja 0, 1, 2, 3.
E de fato podemos tornar isso ainda mais óbvio.
Vamos usar uma lista ainda mais simples, para a qual o programa falha.
Agora, a lista e os índices dos elementos são iguais.
Queremos obter a resposta 3,
mas se olhamos aqui,
i varia apenas na faixa apenas 0,1,2 ; 0,0,0 ; 1,1,1 ; 2,2,2.
2 é o melhor e portanto retornamos isso.
Então não estamos pegando o último elemento.
Então existe alguma coisa errada aqui,
e eu posso adivinhar que, como está faltando o último elemento,
é este -1 -- não precisamos subtrair 1.
Muitas pessoas tendem a subtrair 1, já que uma lista em Python começa de 0
e não queremos ir além do fim da lista.
Aqui, vamos simplesmente imprimir range(4) para nos convencer de que é 0,1,2,3.
Yep, então range(4) é 0, 1, 2, 3.
Agora i varia na faixa 0,1,2,3 e obtemos a resposta que esperávamos.
Então, vamos voltar ao problema que nos foi dado:
["Barbara", "Kingsolver", "Wrote", "the", "Poisonwood", "Bible"]
e esperamos obter ou "Kingsolver" ou "Poisonwood" como resposta,
supondo que eu sei contar.
"Barbara" é 7, "Kingsolver" é 10, "Wrote" é 5, "The" é 3, "Poisonwood" é 10.
Obtemos "Kingsolver" afinal, que é uma resposta correta.
Mas temos todos esses print de depuração, e se o problema não precisa disso,
devemos removê-los antes de submeter a solução, para que isso não entre como parte da resposta
e faça com que nosso programa fique errado.
Agora simplesmente retornamos "Kingsolver".