Nesta tarefa, construiremos um visualizador ASCII para o algoritmo de busca binária. Dada uma lista ordenada, a busca binária é feita da seguinte forma:
Compara-se o valor do elemento procurado com o que está na posição central da lista.
Se for igual, indica-se esta posição.
Se for menor, o processo é repetido, considerando-se apenas os elementos da lista que estão à esquerda da posição central.
Se for maior, o processo é repetido, considerando-se apenas os elementos da lista que estão à direita da posição central.
Caso não haja mais elementos para percorrer, conclui-se que o elemento procurado não está na lista.
Suponha que temos a lista abaixo e estamos procurando o elemento 11.
+-----+-----+-----+-----+-----+-----+-----+
| 002 | 003 | 004 | 008 | 011 | 015 | 017 |
+-----+-----+-----+-----+-----+-----+-----+
Para ilustrar o processo, iremos marcar inicialmente o elemento central, cujo valor é 8. Como 8 é menor do que 11, prosseguiremos com os valores à direita da posição central, marcando o elemento 15. Finalmente, ficaremos apenas com o elemento 11, que é a chave procurada.
+-----+-----+-----+=====+-----+-----+-----+
| 002 | 003 | 004 ||008|| 011 | 015 | 017 |
+-----+-----+-----+=====+-----+-----+-----+
+-----+=====+-----+
| 011 ||015|| 017 |
+-----+=====+-----+
+=====+
||011||
+=====+Note que quando há um número par de elementos, temos duas chaves centrais. Nesta tarefa, iremos trabalhar sempre com a de menor índice nestes casos.
+-----+-----+-----+=====+-----+-----+-----+-----+
| 002 | 003 | 004 ||008|| 011 | 015 | 017 | 020 |
+-----+-----+-----+=====+-----+-----+-----+-----+
A primeira linha da entrada conterá um inteiro a ser procurado e a segunda linha uma lista de inteiros. Uma de suas tarefas será verificar se esta lista está ordenada. Veja o exemplo abaixo:
4
2 3 4 8 11 15 17
A primeira linha da saída conterá uma linha descrevendo o valor a ser procurado.
Elemento procurado: <elem>
Em seguida, a lista lida deverá ser representada, com inteiros com
três dígitos e a moldura formada por
caracteres +, | e - conforme
os exemplos dados.
+-----+-----+-----+-----+-----+-----+-----+
| 002 | 003 | 004 | 008 | 011 | 015 | 017 |
+-----+-----+-----+-----+-----+-----+-----+
Utilizaremos um número fixo de dígitos para facilitar a escrita e a comparação caso você prefira armazenar as strings e não inteiros (Veja as dicas).
Caso a lista não esteja ordenado, você deve emitir a
mensagem "Lista nao ordenada" e interromper
o processo.
Os passos dos algoritmos serão ilustrados como no exemplo da
primeira seção. A moldura do elemento central conterá
caracteres = na parte de cima e na parte de baixo. Nas
laterais, teremos duas barras, sem espaço em branco.
+=====+
||008||
+=====+
O visualizador irá mostrar apenas os elementos que estão participando da busca em cada passo. Observe os passos da busca do elemento 4 na lista fornecida.
Elemento procurado: 004
+-----+-----+-----+-----+-----+-----+-----+
| 002 | 003 | 004 | 008 | 011 | 015 | 017 |
+-----+-----+-----+-----+-----+-----+-----+
+-----+-----+-----+=====+-----+-----+-----+
| 002 | 003 | 004 ||008|| 011 | 015 | 017 |
+-----+-----+-----+=====+-----+-----+-----+
+-----+=====+-----+
| 002 ||003|| 004 |
+-----+=====+-----+
+=====+
||004||
+=====+Note que precisaremos escrever espaços em branco à esquerda, mas não haverá espaços em branco após o último elemento. Observe novamente a saída com fundo colorido:
Elemento procurado: 004
+-----+-----+-----+-----+-----+-----+-----+
| 002 | 003 | 004 | 008 | 011 | 015 | 017 |
+-----+-----+-----+-----+-----+-----+-----+
+-----+-----+-----+=====+-----+-----+-----+
| 002 | 003 | 004 ||008|| 011 | 015 | 017 |
+-----+-----+-----+=====+-----+-----+-----+
+-----+=====+-----+
| 002 ||003|| 004 |
+-----+=====+-----+
+=====+
||004||
+=====+A última parte da saída deverá indicar a posição do elemento, caso encontrado, com a string
"Encontrado na posicao: <pos>". Deve-se considerar
que a posição inicial da lista é 0 e a
escrita das posições não necessitará de
formatação extra. Para o exemplo acima, a parte final
será:
Encontrado na posicao: 2
Caso o elemento
não esteja na lista, a string final será "O elemento nao foi encontrado".
Para escrever um inteiro com um número fixo de casas decimais, você pode usar uma das opções abaixo:
>>>format(5, "03d")
'005'
>>> str(9).zfill(3)
'009'
>>> '20' < '100'
False
>>> '020' < '100'
True
Esta tarefa contém 13 testes abertos, exercitando vários caminhos de busca. Contém também um teste fechado em que uma chave está na lista e outro em que não está.
| arq01.in | arq01.res |
|---|---|
|
|
| arq02.in | arq02.res |
|
|
| arq03.in | arq03.res |
|
|
| arq04.in | arq04.res |
|
|
| arq05.in | arq05.res |
|
|
| arq06.in | arq06.res |
|
|
| arq07.in | arq07.res |
|
|
| arq08.in | arq08.res |
|
|
| arq09.in | arq09.res |
|
|
| arq10.in | arq10.res |
|
|
| arq11.in | arq11.res |
|
|
| arq12.in | arq12.res |
|
|
| arq13.in | arq13.res |
|
|
Veja aqui a
página de submissão da tarefa. O arquivo a ser
submetido deve se chamar lab13.py. No
link Arquivos
auxiliares há um
arquivo aux13.zip que
contém todos os arquivos de testes abertos e seus respectivos
resultados compactados.
O limite máximo será de 30 submissões. Serão considerados os resultados da última submissão.
O peso desta tarefa é 2.
O prazo final para submissão é 12/07/2020.
A nota desta tarefa é proporcional ao número de testes que executaram corretamente, desde que o código esteja coerente com o enunciado. A submissão de um código que não implementa o algoritmo requisitado, mas que exibe as saídas esperadas dos testes abertos a partir da comparação de trechos da entrada será considerada fraude e acarretará a atribuição de nota zero à média final da disciplina.