Slides_LTP-03
Contents
1. LOGQ4 Torre de Hanoi 4 pe as 15 passos 1 P1 T2 2 P2 T3 P1 T3 P3 T2 P1 T1 P2 T2 P1 T2 P4 T3 P1 T3 10 P2 T1 11 P1 T1 12 P3 T3 13 P1 T2 14 P2 T3 15 P1 T3 V O UI W Respostas problemas de l gica LOGQ4 Torre de Hanoi 5 pe as 31 passos P1 T3 P2 T2 P1 T2 P3 T3 P1 T1 P2 T3 P1 T3 P4 T2 P1 T2 10 P2 T1 11 P1 11 12 P3 12 13 P1 T3 14 P2 12 15 P1 T2 O N OUI R WN H 16 P5 T3 17 P1 T1 18 P2 T3 19 P1 T3 20 P3 T1 21 P1 T2 22 P2 T1 23 P1 T1 24 P4 T3 25 P1 T3 26 P2 T2 27 PL T2 28 P3 T3 29 P1 T1 30 P2 T3 31 P1 T32. GUIMAR ES A M LAGES N A C Algoritmos e estruturas de dados led Ed LTC 1994 ISBN 9788521603788 GRIFFITHS D BARRY P Head First Programming A learner s guide to programming using the Python language O Reilly 2009 406p http wwwusers rdc puc rio br rmano processo html Velloso F C Inform tica Conceitos B sicos 7ed Ed Campus 2004 ISBN 9788535215366 A Brain Friendly Guide Head First Inform tica lt Respostas problemas de l gica LOGQ1 Travessia do rio Resposta N gt gt SS gt Sl G ss Atravesse as galinhas Retorne sozinho Atravesse a raposa Retorne com as galinhas Atravesse o milho Retorne sozinho Atravesse as galinhas Respostas problemas de l gica 7a LOGQ2 Esfera de peso diferente Resposta 1 Escolha duas esferas 2 Coloque cada uma das esferas escolhidas num dos pratos da balan a 3 Se a balan a ficar equilibrada forne a como resposta a esfera n o escolhida caso contr rio forne a como resposta a esfera do prato que est num nivel mais baixo O Respostas problemas de l gica u i LOGQ3 Obter 4 litros Respostas 1 Encha o recipiente de 3 litros 4 3 1 1 A 3 B 0 2 Transfira o conte do do recipiente de 3 litros para o recipiente de 5 litros 2 A 0 B 3 3 Encha o recipiente de 3 litros 3 A 3 B 3 4 Com o conte do do recipiente de 3 l
3. executadas sequencialmente 1 Sintonize no videocassete o canal desejado 2 Insira uma fita no videocassete 3 Acione a tecla rec Algoritmo 1 0 Algoritmos primeira vista o conjunto de instru es anteriormente apresentadas como Algoritmo 1 0 constitui um algoritmo visto que as exig ncias estabelecidas para um algoritmo s o todas satisfeitas Entretanto observe que a execu o do suposto algoritmo requer a utiliza o de uma fita de videocassete De forma semelhante uma receita de bolo exige para sua execu o os ingredientes Isto significa que esses algoritmos necessitam de dados que dever o ser fornecidos durante suas execu es Estes dados constituem as entradas dos algoritmos Algoritmos Naturalmente um algoritmo desenvolvido para que ap s a execu o de suas instru es uma determinada tarefa seja realizada O resultado da realiza o desta tarefa conhecida como a Sa da do algoritmo e A sa da do Algoritmo 1 0 seria a grava o de um programa previamente escolhido e A sa da de uma receita de bolo seria o bolo e A sa da de da execu o de uma partitura musical seria o som da melodia Algoritmos Introduzidos os conceitos de entrada e sa da de um algoritmo podemos pensar de forma mais abrangente que um algoritmo um conjunto de a es que ao serem executadas em determinada ordem recebendo as entradas necess r
4. lt S Jo gt 2 gt Z 5 5 O amp N lt C 7E omnes S ae T cnica Programac o Aula 03 he Algoritmos Desenvolvendo o racioc nio l gico de programa o Exemplos de algoritmos Exerc cios Algoritmos Antes de escrever um programa para resolver um problema voc deve compreender minuciosamente o problema e adotar uma abordagem planejada cuidadosamente para resolv lo Ao escrever um programa voc tamb m deve compreender os blocos de constru o dispon veis e empregar t cnicas de constru o de programas comprovadas O Algoritmos o Qualquer problema computacional pode ser resolvido por meio da execucao de uma s rie de a es instru es em uma determinada ordem Um procedimento para realizar uma tarefa resolver um problema em termos de e 1 as a es a executar e 2 a ordem na qual estas a es sao executadas chamado ALGORITMO Algoritmos O exemplo abaixo demonstra a import ncia de se especificar corretamente a ordem das a es Considere o algoritmo de acordar e levantar se seguido por um executivo para ir trabalhar 1 Levante se da cama 2 Tire o pijama 3 Tome banho 4 Vista se 5 Tome caf 6 V para o trabalho Esta rotina leva o executivo ao trabalho e ele estar bem preparado para tomar decis es cr ticas Algoritmos Suponha que os mesmos passos sejam executados em uma or
5. todo A igual a B indu o Agora um exemplo num rico Ex 2 1 Todo n mero que apresenta o algarismo das unidades igual a 4 um n mero par 2 Logo 64 um n mero par Exemplos de racioc nios para resolu o de h a oroblemas Outra t cnica bastante utilizada se tentar raciocinar a partir de uma solu o conhecida de outra quest o Para compreender isto considere as duas seguintes quest es imagine uma rela o de n n meros os quais podem ser referenciados por a comi 1 2 n e queremos som los com a restri o de que s Sabemos efetuar somas de duas parcelas Exemplos de racioc nios para resolu o de gt a oroblemas Para resolver esta quest o podemos pensar em casos particulares e sen 2 basta somar os dois n meros se n 3 basta somar os dois primeiros e somar esta soma com o terceiro e Naturalmente este racioc nio pode ser reproduzido para n gt 3 Exemplos de racioc nios para resolu o de gt a oroblemas A quest o que a soma dos dois primeiros deve estar guardada para que se possa som la com o terceiro obtendo se a soma dos tr s primeiros esta soma deve ser guardada para que seja somada com o quarto e assim sucessivamente Para isto podemos estabelecer uma refer ncia soma atual a qual ser alterada quando a soma com o elemento seguinte for efetuada o At para somar os dois prim
6. a n o seja uma defini o completa a ci ncia do racioc nio a l gica esta ci ncia que estuda os princ pios e m todos usados para distinguir os racioc nios corretos dos incorretos Ao estudar esses m todos aprende se a raciocinar inclusive diante de situa es novas e a portanto resolver problemas cuja solu o n o se conhecia Desenvolvendo o racioc nio l gico de De um modo geral a l gica estuda m todos que permitem estabelecer se um argumento de que uma certa afirmativa pode ser inferida a partir de outras afirmativas ou n o correto Por exemplo a l gica estuda m todos que garantem que a assertiva Jo o racional pode ser inferida a partir das afirma es todo homem racional e Jo o um homem Desenvolvendo o racioc nio l gico de Queremos aprender a desenvolver algoritmos para resolver problemas Queremos aprender a dado um problema determinar um conjunto de instru es para um processador tal que fornecidas as entradas a execu o dessas instru es numa determinada ordem gere como sa da a solu o do problema Desenvolvendo o racioc nio l gico de Embora isto n o esteja consagrado ainda pela ci ncia nem seja considerado como uma parte da l gica o racioc nio que visa ao desenvolvimento de algoritmos chamado de l gica de programa o Desenvolvendo o racioc nio l gico de A seguir s o apresentados exemp
7. atedeira um forno um instrumento musical uma televis o e um ser humano que seja capaz de interagir com os tais equipamentos para que estes executem as instru es Algoritmos O conjunto de elementos que interagem para a execu o de um algoritmo geralmente chamado de processador enquanto que um algoritmo em execu o ser chamado de processo e No exemplo da partitura musical o processador o conjunto instrumentista instrumento e No caso de uma receita de cozinha o processador seria O conjunto constitu do das panelas do forno e da cozinheira O resultado do processo depende dos elementos que comp em o processador Algoritmos 0 processador deve ser capaz de executar as instru es do algoritmo e o processo dever parar em algum instante para que se tenha a realiza o da tarefa pretendida Para que estas duas condi es sejam satisfeitas necess rio que um algoritmo atenda s seguintes exig ncias 1 Ter fim 2 As instru es devem ser claras n o devendo conter ambiguidades nem qualquer coisa que impe a sua execu o pelo processador n o dar margem dupla interpreta o 3 N o pode haver dubiedade em rela o pr xima a o a ser realizada ap s a execu o de uma determinada instru o 4 Todas as instru es devem ser executadas num tempo finito Algoritmos Para exemplificar considere o seguinte conjunto de instru es que devem ser
8. dem ligeiramente distinta 1 Levante se da cama 2 Tire o pijama 3 Vista se 4 Tome banho 5 Tome caf 6 V para o trabalho Neste caso nosso executivo se apresentar encharcado no trabalho Existem elementos de programa o que permitem ao programador controlar a ordem da execu o das instru es a es de programa Estas ser o apresentadas na pr xima aula E Algoritmos Conforme foi visto os algoritmos est o presentes no nosso dia a dia n o necessariamente envolvendo aspectos computacionais Algoritmos Uma receita de bolo uma partitura musical o manual de utiliza o de um videocassete sao algoritmos As a es de uma receita de bolo s o do tipo leve ao forno previamente aquecido bata as claras at ficarem em ponto de neve etc e No caso de uma partitura musical existem a es que indicam que uma determinada nota musical deve ser executada por determinado tempo e O manual de utiliza o de um videocassete cont m a es do tipo selecione o canal desejado aperte a tecla rec etc Algoritmos A execu o de cada um destes algoritmos resulta na realiza o de alguma tarefa e a confec o de um bolo e a execu o de uma melodia ea grava o de um programa de televis o Al m disso a execu o de cada um deles requer a utiliza o de equipamentos constitu dos de componentes el tricos mec nicos e eletr nicos como uma b
9. eiros pode se pensar em somar a soma do primeiro com o segundo Exemplos de racioc nios para resoluc o de problemas Temos ent o o seguinte algoritmo e 1 Fa a 1 e 2 Fa a Soma a 3 Repita n 1 vezes as instru es 3 1 e 3 2 e 3 1 Substitua i pori 1 e 3 2 Substitua Soma por Soma a Exemplos de racioc nios para resolu o de gt a oroblemas Por exemplo se n 5 e a 8 a 4 a 9 a 13 e a 7 a execu o do algoritmo resultaria nas seguintes a es el 1 e 2 Soma 8 adet lFa ai 1 gt 03 2 1 Soma 8 4 12 2 Fa a Soma a 3 1 2 i 3 3 Repita n 1 vezes as instru es 3 1 e 3 2 3 2 2 Soma 12 9 21 3 1 Substitua i pori 1 e 3 1 3 i 14 3 2 Substitua Soma por Soma a e 3 2 3 Soma 21 13 34 93 1 4 1 5 e 3 2 4 Soma 34 7 41 Exemplos de racioc nios para resolu o de gt a oroblemas Como veremos ao longo do curso este algoritmo bastante utilizado em programa o sendo mais comum o primeiro termo da rela o ser somado dentro da repeti o Exemplos de racioc nios para resolu o de Y a oroblemas Neste caso para que o primeiro seja somado necess rio que a refer ncia Soma seja inicializada com O zero ficando assim o algoritmo 1 Fa a 0 2 Fa a Soma 0 3 Repita n vezes as instru es 3 1 e 3 2 3 1 Substitua
10. gum procedimento que permitisse ao processador verificar se a fita estaria ou n o rebobinada Isto pode ser feito pelo ser humano que faz parte do processador ou seja pela pessoa que est tentando gravar o programa Algoritmos Assim o Algoritmo 1 1 seria mais adequado se contivesse as seguintes instru es 1 Sintonize no videocassete o canal desejado 2 Apanhe uma fita verifique se ela est rebobinada e a insira no videocassete 3 Se a fita n o estiver rebobinada acione a tecla rr 4 Acione a tecla rec Algoritmo 1 2 Algoritmos O Algoritmo 1 0 pelo menos a maior parte dele definido pela pr pria constru o do videocassete e nos apresentado pelo manual de utiliza o do aparelho Ou seja O algoritmo est pronto e n o h necessidade de que se pense N o h necessidade de que se raciocine Basta que se disponha dos equipamentos necess rios e que se seja capaz de executar as instru es Aula 03 Algoritmos Desenvolvendo o racioc nio l gico de programa o Exemplos de algoritmos Exerc cios Desenvolvendo o racioc nio l gico de Estamos interessados em aprender a desenvolver algoritmos que resolvam problemas Nestes casos necess rio pensar Mais do que isto necess rio raciocinar E necess rio aprender a raciocinar Como aprender a raciocinar Desenvolvendo o racioc nio l gico de Embor
11. ias e compat veis com as instru es fornece sa das adequadas usando recursos e tempo de execu o finitos Algoritmos importante observar as sa das produzidas por alguns algoritmos tamb m s o sens veis s entradas Em alguns casos eventuais problemas podem ser evitados com instru es adicionais e instru es que permitem controlar o fluxo de execu o das a es do algoritmo Algoritmos No Algoritmo 1 0 pode se perceber um problema o que aconteceria se a fita que fosse inserida j tivesse sido totalmente utilizada e n o houvesse sido previamente rebobinada A grava o n o seria realizada e a sa da do algoritmo para aquela entrada n o ocorreria Algoritmos Seria necess ria ent o uma instru o que posicionasse a fita no seu in cio independente da posi o em que ela estivesse 1 Sintonize no videocassete o canal desejado 2 Insira uma fita no videocassete 3 Acione a tecla rr tecla para rebobinar a fita 4 Acione a tecla rec Algoritmo 1 1 O Algoritmos o evidente que a execu o da instru o 3 nem sempre resultar em alguma a o efetiva o que pode ocorrer se a fita estiver na sua posi o inicial Este problema resolvido precedendo a execu o da instru o por uma instru o condicional 3 Se a fita n o estiver rebobinada acione a tecla rr Algoritmos Teria de ser estabelecido al
12. itros complete o recipiente de 5 litros 4 A 1 B 5 5 Esvazie o recipiente de 5 litros 5 A 1 B 0 6 Transfira o conte do do recipiente de tr s litros para o recipiente de 5 litros 6 A 0 B 1 7 Encha o recipiente de 3 litros 7 A 3 B 1 8 Transfira o conte do do recipiente de 3 litros para o recipiente de 5 litros 8 A 0 B 4 Ou 4 5 1 Encha o recipiente de 5 litros Com o conte do do recipiente de 5 litros encha o de 3 litros A 3 B 2 Esvazie o recipiente de 3 litros A 0 B 2 1 A 0 2 3 Transfira o conte do do recipiente de 5 litros para o recipiente de 3 litros 4 A 2 B 0 5 6 B 5 Encha o recipiente de 5 litros A 2 B 5 Com o conte do do recipiente de 5 litros complete o recipiente de 3 litros A 3 B 4 Respostas problemas de l gica LOGQ4 Torre de Hanoi e Assumindo P1 P2 P3 P4 e P5 como as pe as onde os di metros de P5 gt P4 gt P3 gt P2 gt P1 e Considere tamb m T1 T2 e T3 como as torres 1 2 e 3 respectivamente e Por fim denotando o movimento da peca para a torre j como Pi Tj i 1 2 3 4 5 e j 1 2 3 temos as seguintes solu es com o menor n mero poss vel de passos Respostas problemas de l gica LOGQ4 Torre de Hanoi 3 pe as 7 passos P1 T2 P2 T3 P1 T3 P3 T2 P1 T1 P2 T2 P1 T2 Respostas problemas de l gica
13. lho gt y Problemas de l gica 2 LOGQO2 Disp e se de tr s esferas id nticas na forma sendo duas delas de mesmo peso e a terceira de peso maior A quest o descobrir qual a esfera de peso diferente realizando se apenas uma pesagem numa balan a de dois pratos T 0924 Problemas de l gica 3 LOGQO3 como obter exatamente 4 litros de gua dispondo de dois recipientes com capacidades de 3 litros e 5 litros O Problemas de l gica T 4 LOGQO4 Disp e se de tr s torres A B C dispostas nesta ordem onde inicialmente a torre A possui um certo n mero de pe as empilhadas de forma que uma pe a est sempre acima de outra com di metro maior que o seu O problema transportar todas as pe as da torre A para a torre C podendo se apenas mover uma pe a por vez de uma torre para outra e com a restri o de que a cada passo uma pe a n o pode ser colocada sobre outra de di metro menor o Resolver com 3 4 e 5 pe as Refer ncias BORLAND Turbo Pascal vers o 7 0 S L Borland International Inc 1992 DEITEL P DEITEL H M Java How to program 9th ed Ed Prentice Hall 2011 ISBN 978 0 13 257566 9 FARRER H BECKER C G FARIA E C MATOS H F et al Algoritmos estruturados 3ed Ed LTC 1999 ISBN 9788521611806 FARRER H BECKER C G FARIA E C MATOS H F et al Pascal estruturado 3ed Ed LTC 1999 ISBN 9788521611745
14. los de racioc nios l gicos tipicamente utilizados para resolu o de problemas Exemplos de racioc nios para resoluc o de problemas e Exaust o quando o n mero de alternativas poss veis para se atingir um objetivo pequeno analisa se todas elas uma a uma Exemplos de racioc nios para resoluc o de oroblemas geral gt espec fico Dedu o a dedu o consiste em se chegar a uma verdade particular e ou espec fica a partir de outra mais geral ou abrangente Portanto ao incluirmos um fato espec fico em outro mais geral estamos raciocinando por dedu o Ex 1 1 A sempre igual a B fato geral tamb m chamada de premissa maior 2 existe um X que igual a A caso particular ou premissa menor 3 logo este X igual a B conclus o Ex 2 1 Todo n mero mpar pode ser escrito como 2n 1 para qualquer n inteiro 2 325 um n mero mpar 3 logo 325 pode ser escrito como 2n 1 se n for igual a 162 Ou seja 2x 162 1 325 Exemplos de racioc nios para resolu o de gt a oroblemas n mero relevante de casos espec ficos geral e Indu o A indu o o racioc nio que ap s considerar um n mero suficiente de casos particulares conclui uma verdade geral observando casos particulares isolados procuramos neles um padr o Ex 1 1 Todos os A s observados s o iguais a B observa o de dados ou fatos isolados 2 Logo
15. pori 1 3 2 Substitua Soma por Soma a Aula 03 Algoritmos Desenvolvendo o racioc nio l gico de programa o he Exemplos de algoritmos Exerc cios Exemplos de Algoritmos Resolver problemas matem ticos e Algoritmo para determinar a m dia aritm tica de v rios n meros dados e Determinar as ra zes de uma equa o do segundo grau e Encontrar o m ximo divisor comum de dois n meros dados Exemplos de Algoritmos Resolver quest es gen ricas e Algoritmo para colocar em ordem alfab tica uma relac o de nomes de pessoas e Atualizar o saldo de uma conta banc ria na qual se fez um dep sito e Corrigir provas de um teste de m ltipla escolha e Cadastrar um novo usu rio de uma locadora etc Aula 03 Algoritmos Desenvolvendo o racioc nio l gico de programa o Exemplos de algoritmos he Exerc cios Problemas de l gica 1 LOGQO1 Um senhor est numa das margens de um rio com uma raposa uma d zia de galinhas e um saco de milho Ele pretende atravessar o rio com suas cargas num barco que s comporta o senhor e uma das cargas Escreva uma sequ ncia de a es necess rias para que ele consiga atravessar o rio sabendo que a Araposa n o pode ficar sozinha com as galinhas pois estas seriam comidas pela raposa b As galinhas n o podem ficar sozinhas com o milho c Araposa pode ficar sozinha com o mi
Download Pdf Manuals
Related Search
Slides_LTP 03