Diversos recursos computacionais são inventados todos os dias para facilitar a realização dos mais variados tipos de trabalho. Como por exemplo, um localizador de palavras em um texto. Quando pressionamos as teclas ctrl + F em um computador ou acessamos o recursos "localizar" (geralmente representado por uma lupa) em nossos celulares, o dispositivo realiza uma busca no site que estamos visitando e nos mostra em que local da página aquela palavra está. É um recurso que pode nos poupar bastante tempo![br][br]Entretanto, para realizar a busca, o dispositivo precisa comparar as palavras presentes no texto com a palavra desejada de alguma forma. Existem diversas formas diferentes que o dispositivo pode utilizar para buscar uma palavra. Algumas formas são mais rápidas outras são mais demoradas, tudo depende da quantidade de operações que a maquina terá que fazer. Um grande desafio da computação é tentar realizar uma tarefa utilizando a menor quantidade de operações possíveis.
O applet abaixo foi desenvolvido para explorar e pensar novas estratégias de busca. Para isso, ao clicar em reiniciar ele irá gerar um número aleatoriamente entre 0 e 99. Após isso, ao clicar em qualquer um dos 100 botões numerados de 00 até 99 ele te informará se o valor selecionado é maior, menor ou igual ao número sorteado. Além disso, ele fornece o número total de tentativas que você fez até encontrar o número.
Para um computador todas as letras e símbolos digitados se tornam números. Dessa forma, considere que uma lista com 100 palavras listadas em ordem alfabética é interpretada pelo computador como os números 0, 1, 2, ..., 99. Sendo 0 a primeira palavra da lista, 1 a segunda palavra e assim por adiante.[br]Assim, localizar uma palavra em ordem alfabética equivale a encontrar um número em ordem crescente (ordenado do menor para o maior) tal como no applet acima. [br]Utilizando esse texto e o applet explore as atividades propostas.
Marcos descreveu o seguinte procedimento para poder encontrar o número sorteado no applet:[br]Clique no botão correspondente ao primeiro número (00), se o valor for igual pare. Se o valor do botão for menor do que o valor sorteado clique no botão seguinte e repita o procedimento. [br][br]Exemplo 1: Supondo que o valor sorteado seja 19.[br]Então o botão 00 será testado, depois o botão 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18 e por fim o 19. Momento em que será exibida a mensagem: "Encontrou". Portanto, o valor sorteado será encontrado em 20 operações.[br][br]Exemplo 2: Supondo que o valor sorteado seja 3.[br]Serão testados os botões 00, 01, 02 e 03. O valor será encontrado em 4 operações[br][br]Explore o procedimento descrito por Marcos no applet e escreva qual é o número máximo de operações que podem ser necessárias utilizando esse procedimento para encontrar o valor sorteado? Escreva um comentário explicando o motivo da sua resposta.[br][br]Dica: Para descobrir o maior número de operações que podem ser realizadas pense numa situação em que seguindo o procedimento fielmente o valor sorteado será encontrado quando chegar ao último passo possível.
Janaína pensou no seguinte procedimento para encontrar o valor:[br]Considerando o botão atual como 00,[br]1 - testa-se o décimo botão após o atual (ou seja, botão 09); Se for igual pare. Se for maior que o valor sorteado, testa cada um dos 9 botões anteriores em ordem crescente. Se for menor, "salta" dez botões e teste-o (botão 19).[br]2 - Repita o procedimento (1) até encontrar o valor sorteado.[br][br]Exemplo 1: Supondo que o valor sorteado seja 30.[br]Será testado primeiramente o botão 09, em seguida o botão 19, após ele o botão 29 e o botão 39. Neste momento o applet informara que o valor testado é maior do que o valor sorteado. Então será testado o botão 30 e o valor sorteado será encontrado em 5 operações.[br][br]Exemplo 2: Supondo que o valor sorteado seja 13.[br]Serão testados os botões 09 e 19. Nesse momento o applet informará que o valor testado é maior do que o valor sorteado. Então serão testados os botões 10, 11, 12 e 13. Encontrando assim o valor sorteado em 6 operações.[br][br]Explore o procedimento descrito por Janaína no applet e escreva qual é o número máximo de operações que podem ser necessárias utilizando esse procedimento para encontrar o valor sorteado? Escreva um comentário explicando o motivo da sua resposta.
R2D2 pensou no seguinte procedimento para encontrar o valor:[br][br]Considere 02 como o número atual,[br][br]1 - testa-se o número primo atual; Se for este o valor sorteado pare, Se for menor, teste o próximo número primo. Se for maior, teste cada um dos valores que estão entre este número primo e o menor número primo mais próximo a ele, em ordem crescente.[br][br]Exemplo 1: Supondo que o valor sorteado seja 9.[br]Será testado primeiramente o botão 02, em seguida o botão 03, após ele o botão 07 e o botão 11. Neste momento o applet informara que o valor testado é maior do que o valor sorteado. Então serão testados os botões 08 e 09 e o valor sorteado será encontrado em 6 operações.[br][br]Exemplo 2: Supondo que o valor sorteado seja 97.[br]Serão testados os botões 02, 03, 05, 07, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 e 97. Sendo o valor sorteado encontrado em 25 operações. (Foram utilizados todos os números primos existentes entre 00 e 99)[br][br]Explore o procedimento descrito por R2D2 no applet e escreva qual é o número máximo de operações que podem ser necessárias utilizando esse procedimento para encontrar o valor sorteado? Escreva um comentário explicando o motivo da sua resposta.
Qual dos procedimentos descritos anteriormente permite encontrar de forma mais rápida o valor sorteado, considerando em cada um deles o caso em que serão necessários o maior número de operações possível.
Que tal tentar descrever o seu próprio procedimento para encontrar o valor sorteado?[br]Pense em um procedimento simples e teste-o no applet! Depois, verifique se ele encontra o valor sorteado em menos operações do que os procedimentos descritos por Marcos, Janaína e R2D2. [br]Não esqueça de descrever o seu procedimento como resposta dessa atividade!