Baixe o app para aproveitar ainda mais
Prévia do material em texto
Algoritmos I Edezio 1 ◮Algoritmo Conjunto de regras e operac¸o˜es bem definidas e ordenadas, destinadas a` soluc¸a˜o de um problema, ou de uma classe de problemas, em um nu´mero finito de etapas. Exemplos: As receitas de culina´ria, os manuais de montagem ou de operac¸a˜o de ma´quinas, o algo- ritmo da prova dos nove, o algoritmo para extrac¸a˜o de um dente. ⊲ Programa Um programa e´ um Algoritmo escrito em uma linguagem computacional. Todos os trabalhos execu- tados pelo computador sa˜o feitos seguindo programas. Basicamente um computador so´ entende Linguagem Bina´ria, ou tambe´m chamada Linguagem de Ma´quina (linguagem que so´ admite dois s´ımbolos : zero e um). Todos os s´ımbolos nele introduzidos (letras, d´ıgitos e caracteres especiais, como v´ırgulas, aspas) sa˜o ”digeridos”pela Unidade de Entrada e, armazenados em forma de um co´digo constru´ıdo por conjunto de zeros e uns, constru´ıdo e digi- tados pelos pro´prios programadores! Cada s´ımbolo tem uma codificac¸a˜o pro´pria e existem diversas codificac¸o˜es padronizadas para cada s´ımbolo. O ASCII usa 8 bits para representar um caracter, logo ate´ 256 caracteres distintos podem ser representados usando o ASCII. CARACTER CO´DIGO ASCII espac¸o(ou branco) 0100 0000 ( 0100 1000 + 0100 1011 $ 0100 0100 A 1010 0001 B 1010 0010 C 1010 0011 0 0101 0000 1 0101 0001 2 0101 0010 ⊲ Linguagens de Programac¸a˜o Sa˜o Softwares que permitem o desenvolvimento de programas. Possuem um poder de criac¸a˜o ilimi- tado, desde jogos, editores de texto, sistemas empresariais ate´ sistemas operacionais. Existem va´rias linguagens de programac¸a˜o, cada uma com suas caracter´ısticas pro´prias. Exemplos: Pascal, Clipper, C, Visual Basic,Delphi e etc. ⊲Algoritmos em ”Portugol” Durante nosso curso iremos aprender a desenvolver nossos Algoritmos em uma pseudo-linguagem conhecida como ”Portugol”ou Portugueˆs Estruturado. Algoritmos I Edezio 2 ⊲Operadores Aritme´ticos + adic¸a˜o - subtrac¸a˜o * produto / divisa˜o ∧ potenciac¸a˜o ⊲Operadores Relacionais > maior que < menor que >= maior ou igual <= menor ou igual = igual <> diferente ⊲Linearizac¸a˜o de Expresso˜es Para a construc¸a˜o de Algoritmos todas as expresso˜es aritme´ticas devem ser linearizadas, ou seja, colocadas em linhas. Exemplo: x = A2 − 5B + C 2 (B + 3) 7 ⇒ x← (A ∧ 2− 5 ∗B + C/2)/((B + 3)/7) ⊲Operadores Especiais (MOD e DIV) MOD: retorna o resto da divisa˜o entre 2 nu´meros inteiros. DIV: retorna o valor inteiro que resulta da divisa˜o entre 2 nu´meros inteiros. Prioridade Operadores 1o pareˆnteses mais internos 2o pot rad 3o * / div mod 4o + - ⊲Constantes : um dado e´ constante se seu valor e´ constante desde o in´ıcio ate´ o fim da execuc¸a˜o do algoritmo. ⊲Varia´vel : um dado e´ classificado como varia´vel quando pode ser alterado durante a execuc¸a˜o do algoritmo em que e´ utilizada. Algoritmos I Edezio 3 ⊲Identificadores Sa˜o os nomes dados a varia´veis, constantes, tipo de dados e programas. Regras Para construc¸a˜o de Identificadores: • Na˜o podem ter nomes de palavras reservadas (comandos da linguagem); • Devem possuir como 1o caractere uma letra ou Underscore ( ); • Ter como demais caracteres letras, nu´meros ou Underscore; • Ter no ma´ximo 127 caracteres; • Na˜o possuir espac¸os em branco; • A escolha de letras maiu´sculas ou minu´sculas e´ indiferente. Exemplos: NOME, nota, a1, c, N1, NOMEPAI, IDADE FILHO, PI, A2. ⊲Tipos de Dados Todas as Varia´veis devem assumir um determinado tipo de informac¸a˜o. Inteiro admite somente nu´meros inteiros. Real admite nu´meros reais (com ou sem casas decimais). Caracter admite caracteres alfanume´ricos. Lo´gico admite somente valores lo´gicos(verdadeiro/falso). ⊲Instruc¸o˜es de Entrada e Sa´ıda • Leia: comando de entrada que permite a leitura de Varia´veis de Entrada. Leia(< identificador1, identificador2, . . . , identificadorN >) Exemplo: Leia(a,b,c) Observac¸a˜o: a varia´vel ou varia´veis utilizadas na entrada de dados devem ter sido declaradas anteriormente. • Escreva: comando de sa´ıda que exibe uma informac¸a˜o na tela do monitor. Escreva(”Algum texto para facilitar o entendimento da ac¸a˜o desejada”) Escreva(< identificador1, identificador2, . . . , identificadorN >) Exemplos: Escreva(NOME) Escreva(”Digite o nome do aluno:”) Escreva(”O nome do aluno e´:”,NOME) ⊲Sinal de Atribuic¸a˜o: • Varia´vel: para atribuir valores a varia´veis devemos usar o sinal ”← ”. • Constantes: as constantes sa˜o eternamente iguais a determinados valores, portanto usamos o sinal de ” = ”. Algoritmos I Edezio 4 Exemplo: A← 2 ∗B PI = 3, 14 ⊲Corpo Geral de um Algoritmo ALGORITMO ′′identificador′′ CONST < identificador >=< dado > V AR < identificador >:< tipo > I´NICIO < comando1 > < comando2 > ... < comandoN > FIM ⊲Comenta´rios Podemos inserir em um Algoritmo comenta´rios para aumentar a compreensa˜o do mesmo, para isso basta que o texto fique entre chaves ′′{}′′ ou apo´s duas barras (visualg) ′′//′′. Exemplo: Segue um Algoritmo que leˆ o nome e as 2 notas de um aluno. Em seguida o Algoritmo calcula e escreve a me´dia obtida. ALGORITMO ”MEDIA FINAL” VAR NOTA1, NOTA2, MEDIA: Real NOME : caracter INICIO LEIA (NOME) LEIA (NOTA1, NOTA2) MEDIA ← (NOTA1 +NOTA2)/2 ESCREVA (NOME, MEDIA) FIM Este algoritmo pode ser mais refinado acrescentando mais informac¸o˜es e comenta´rios: Algoritmos I Edezio 5 ALGORITMO ”MEDIA FINAL” //Este algoritmo calcula a me´dia final de um aluno VAR NOTA1, NOTA2, MEDIA: Real NOME : caracter INICIO ESCREVA (′′Nome do aluno:′′) LEIA(NOME) ESCREVA (′′Digite a primeira nota:′′) LEIA(NOTA1) ESCREVA(′′Digite a segunda nota:′′) LEIA(NOTA2) MEDIA ← (NOTA1 +NOTA2)/2 ESCREVA (NOME, MEDIA) FIM ⊲Operadores Lo´gicos Utilizaremos treˆs operadores ba´sicos para a formac¸a˜o de novas proposic¸o˜es lo´gicas compostas a partir de outras proposic¸o˜es lo´gicas simples. Operador Func¸a˜o ∼ (na˜o) negac¸a˜o ∧ (e) conjunc¸a˜o ∨ (ou) disjunc¸a˜o ⊲Tabela Verdade A B ∼ A ∼ B A∧ B A∨B V V F F V V V F F V F V F V V F F V F F V V F F ⊲Estruturas de Selec¸a˜o Uma estrutura de selec¸a˜o permite a escolha de um grupo de ac¸o˜es a ser executado quando determi- nadas condic¸o˜es, representadas por expresso˜es lo´gicas ou relacionais, sa˜o ou na˜o satisfeitas. Selec¸a˜o Simples: se < condic¸a˜o > enta˜o < comando1 > < comando2 > < comando3 > ... < comandoN > fim-se Algoritmos I Edezio 6 Selec¸a˜o Composta: se < condic¸a˜o > enta˜o < comando1 > < comando2 > < comando3 > ... < comandoN > sena˜o < comando1′ > < comando2′ > < comando3′ > ... < comandoN ′ > fim-se Exemplo: Elaborar um algoritmo que leia um nu´mero e determine se e´ maior que zero ou na˜o. ALGORITMO”Exemplo1” VAR N: inteiro Inicio LEIA(N) SE N > 0 enta˜o ESCREVA(N,”e´ maior que zero.”) SENA˜O ESCREVA(N,”na˜o e´ maior que zero.”) FIM-SE Fim ⊲Estruturas de Repetic¸a˜o A estrutura de repetic¸a˜o permite que uma sequ¨eˆncia de comandos seja executada repetidamente enquanto uma determinada condic¸a˜o seja satisfeita. A esses trechos do algoritmo que sa˜o repetidos damos o nome de lac¸os de repetic¸a˜o. O nu´mero de repetic¸o˜es pode ser indeterminado, pore´m necessariamente finito. Repetic¸a˜o com Teste no In´ıcio (Pre´-teste) E´ usada para repetir N vezes uma ou mais instruc¸o˜es. Tendo como vantagem o fato de na˜o ser necessa´rio o conhecimento pre´vio do nu´mero de repetic¸o˜es. enquanto < condic¸a˜o > fac¸a < comando1 > < comando2 > < comando3 > ... < comandoN > fim-enquanto Algoritmos I Edezio 7 Exemplo 1: Elaborar um algoritmo que escreva os inteiros de 1 a 100. Algoritmo”Exemplo” Var N: inteiro In´ıcio N ← 1 enquanto N <= 100 fac¸a escreva(N) N ← N + 1 fim-enquanto Fim Quandoo nu´mero de repetic¸o˜es for previamente conhecido, devemos utilizar um contador para con- trolar o nu´mero de repetic¸o˜es do lac¸o. Um contador e´ uma varia´vel do tipo inteiro que deve receber inicialmente (antes do lac¸o) o valor 1 e dentro do lac¸o (no final dele) deve ser incrementada em 1, ou seja, adicionar o valor 1 ao conteu´do da pro´pria varia´vel. A condic¸a˜o para interromper o lac¸o sera´: contador ≤ nu´mero de repetic¸o˜es. Exemplo 2: Este algoritmo leˆ um conjunto 100 nu´meros inteiros e exibe a soma dos mesmos. Algoritmo ”Soma” Var NUM, SOMA, CONT: inteiro In´ıcio SOMA ← 0 CONT ← 1 enquanto CONT <= 100 fac¸a escreva(”Digite um nu´mero inteiro: ”) leia(NUM) SOMA← SOMA+NUM CONT ← CONT +1 fim-enquanto escreva(”A soma e´ ”, SOMA) Fim Repetic¸a˜o com Teste no Final (Po´s-teste) A estrutura de repetic¸a˜o condicional com po´s-teste permite que va´rias instruc¸o˜es sejam executadas repetidamente enquanto uma condic¸a˜o qualquer na˜o for verdadeira, sendo que primeiro sa˜o exe- cutadas as instruc¸o˜es e depois a e´ testada a condic¸a˜o. repita < comando1 > < comando2 > < comando3 > ... < comandoN > ate´ <condic¸a˜o> Algoritmos I Edezio 8 Exemplo 3: Reescrevendo o algoritmo, do exemplo 1, que escreve os inteiros de 1 a 100, ter´ıamos: Algoritmo”Exemplo1” Var N: inteiro In´ıcio N ← 1 repita escreva(N) N ← N + 1 ate´ N > 100 Fim Exemplo 4: Reescrevendo o algoritmo do exemplo 2, que leˆ um conjunto 100 nu´meros inteiros e exibe a soma dos mesmos, ter´ıamos: Algoritmo ”Soma” Var NUM, SOMA, CONT: inteiro In´ıcio SOMA ← 0 CONT ← 1 repita escreva(”Digite um nu´mero inteiro: ”) leia(NUM) SOMA← SOMA+NUM CONT ← CONT +1 ate´ CONT > 100 escreva(”A soma e´ ”, SOMA) Fim Observac¸a˜o: Um cuidado fundamental que o construtor do algoritmo deve ter e´ o de certificar-se que a condic¸a˜o para que sejam mantidas as iterac¸o˜es torne-se, em algum momento, falsa, para que o algoritmo na˜o entre em um lac¸o infinito Repetic¸a˜o com Varia´vel de Controle Na estrutura para ... fac¸a, a varia´vel de controle e´ inicializada com <valor inicial> e no in´ıcio de cada iterac¸a˜o, seu valor e´ comparado com <valor final>. Se o valor da varia´vel for menor ou igual a <valor final>, a lista de comandos e´ executada e apo´s ser executado o u´ltimo comando da lista, a varia´vel de controle e´ incrementada. Isto repete-se ate´ que o valor da varia´vel de controle seja maior que <valor final>, quando enta˜o e´ executado o comando imediatamente apo´s a palavra fimpara. A instruc¸a˜o passo e´ necessa´ria se o incremento for diferente de 1. Algoritmos I Edezio 9 para V de VI ate´ VF passo P fac¸a < comando1 > < comando2 > < comando3 > ... < comandoN > fimpara Em que: • V e´ a varia´vel de controle; • VI e´ o valor inicial da varia´vel V; • VF e´ o valor final da varia´vel V, ou seja, o valor ate´ o qual ela vai chegar; • P e´ o valor do incremento dado a` varia´vel V. Exemplo 5: Reescrevendo o algoritmo, do exemplo 1, que escreve os inteiros de 1 a 100, ter´ıamos: Algoritmo”Exemplo1” Var N: inteiro In´ıcio para N de 1 ate´ 100 fac¸a escreva(N) fimpara Fim Exemplo 6: Reescrevendo o algoritmo do exemplo 2, que leˆ um conjunto 100 nu´meros inteiros e exibe a soma dos mesmos, ter´ıamos: Algoritmo ”Soma” Var NUM, SOMA, N: inteiro In´ıcio SOMA ← 0 para N de 1 ate´ 100 fac¸a escreva(”Digite um nu´mero inteiro: ”) leia(NUM) SOMA← SOMA+NUM fimpara escreva(”A soma e´ ”, SOMA) Fim Algoritmos I Edezio 10 Exemplo 7: Elabore um algoritmo que escreva os nu´meros ı´mpares de 1 a 1000. Algoritmo ”Exemplo7” Var i: inteiro In´ıcio para i de 1 ate´ 1000 passo 2 fac¸a escreva(i, ”e´ ı´mpar”) fimpara Fim ⊲Arrays As varia´veis compostas homogeˆneas, mais conhecidas como arrays, correspondem a conjuntos de elementos de um mesmo tipo, representados por um u´nico nome. Os arrays podem variar quanto a sua dimensa˜o, isto e´, a quantidade de ı´ndices necessa´ria para a individualizac¸a˜o de cada elemento do conjunto. O array unidimensional tambe´m e´ conhecido por vetor, enquanto o array bidi- mensional e´ denominado de matriz. Exemplos: Vetor: V = 8 2 5 3 7 5 Matriz: M = 2 3 9 4 10 2 5 6 6 Cada elemento dos arrays podem ser referenciados atrave´s de ı´ndices. Exemplos: V [2] = 2, V [4] = 3, M [2, 1] = 4, M [3, 2] = 6, M [2, 3] = 2. Vetor Vetores sa˜o arrays que necessitam de apenas um ı´ndice para individualizar um elemento do conjunto. Para definirmos uma varia´vel do tipo vetor, utilizamos a seguinte sintaxe: Identificador: Vetor[´ındice inicial. . . ı´ndice final] de < tipo > O ı´ndice-inicial e o ı´ndice-final devem ser do mesmo tipo escalar (inteiro, caracter ou booleano). Exemplos: Var IDADE : vetor[1.. 20] de inteiros NOME : vetor[1..30] de caracteres QUANT : vetor[’A’..’Z’] de inteiros RECEITA, DESPESA : vetor[90..96] de reais VETOR : vetor[-5..5] de caracteres Para processarmos individualmente todos os componentes de um vetor, e´ aconselha´vel o uso da es- trutura PARA, para que possamos variar o ı´ndice do vetor. Exerc´ıcios: 1. Fazer um algoritmo que leia um vetor A contendo 30 nu´meros inteiros, calcule e exiba: Algoritmos I Edezio 11 a) o maior elemento; b) a posic¸a˜o (´ındice) do maior elemento Soluc¸a˜o: Algoritmo ”Maior” Var A : vetor[1..30] de inteiros I, POS, MAIOR : inteiro; In´ıcio \\leitura do vetor para I de 1 ate´ 30 fac¸a leia(A[I]) fimpara MAIOR ← A[1] POS ← 1 \\ comparac¸a˜o dos elementos com a varia´vel MAIOR para I de 2 ate´ 30 fac¸a se A[I] > MAIOR enta˜o MAIOR ← A[I] POS ← I fimse fimpara \\ exibic¸a˜o dos resultados escreva(MAIOR,POS) Fim 2. Fazer um algoritmo para ler 20 nu´meros, calcular a me´dia dos mesmos e exibir os nu´meros que estiverem acima da me´dia. Soluc¸a˜o: Algoritmo”Soma” Var NUM : vetor[1..N] de reais I,SOMA : inteiros MEDIA : real In´ıcio inicializac¸a˜o da varia´vel SOMA SOMA← 0 \\ leitura e soma dos nu´meros para I de 1 ate´ 20 fac¸a leia(NUM[I]) SOMA ← SOMA + NUM[I] fimpara \\ ca´lculo da me´dia MEDIA ← SOMA / 20 \\exibic¸a˜o dos nu´meros maiores que a me´dia para I de 1 ate´ 20 fac¸a se NUM[I] > MEDIA enta˜o Algoritmos I Edezio 12 escreva(NUM[I]) fimse fimpara Fim 3. Fazer um programa que: a) leia um vetor VET de 100 nu´meros inteiros; b) leia um valor inteiro NUM; c) determine e exiba a posic¸a˜o de NUM dentro de VET. Caso NUM na˜o seja encontrado dentro de VET, exiba o valor 0 (zero). Soluc¸a˜o: Algoritmo”Posic¸a˜o” Var VET : vetor[1..N] de inteiros NUM,I,POS : inteiros In´ıcio \\ leitura dos dados para I de 1 ate´ 100 fac¸a leia(VET[I]) fimpara leia(NUM) \\ determinac¸a˜o da posic¸a˜o POS ← 0 para I de 1 ate´ 100 fac¸a se VET[I] = NUM enta˜o POS ← I fimpara \\ exibic¸a˜o do resultado escreva(POS) Fim ⊲Matriz Matrizes sa˜o arrays que necessitam de dois ı´ndices para individualizar um elemento do conjunto. O primeiro ı´ndice representa as linhas e o segundo as colunas. Para definirmos uma varia´vel do tipo matriz, utilizamos a seguinte sintaxe: Identificador: matriz[´ındice1-inicial..´ındice1-final, ı´ndice2-inicial..´ındice2-final] de < tipo > O ı´ndice1-inicial e o ı´ndice1-final devem ser do mesmo tipo escalar (inteiro, caracter ou booleano). O ı´ndice2-inicial tambe´m deve ser do mesmo tipo escalar do ı´ndice2-final. Algoritmos I Edezio 13 Exemplos: var M1 : matriz[1..4,80..90] de reais M2 : matriz[’A’..’E’,0..10] de cadeias M3 : matriz[-3..3,1..3] de caracteres Exerc´ıcios: 1. Fazer um algoritmo para ler uma matriz 3 x 5 de nu´meros inteiros e escreveˆ-la apo´s ter multi- plicado cada elemento por 2. Soluc¸a˜o: Algoritmo”Multiplicac¸a˜o” var M : matriz[1..3,1..5] de inteiros I,J : inteiros In´ıcio \\ leiturada matriz para I de 1 ate´ 3 fac¸a para J de 1 ate´ 5 fac¸a escreva(’Elemento da linha ’,I,’ coluna ’,J,’ : ’) leia(M[I,J]) fimpara fimpara \\ ca´lculo da multiplicac¸a˜o para I de 1 ate´ 3 fac¸a para J de 1 ate´ 5 fac¸a M[I,J] ←M [I, J ] ∗ 2 fimpara fimpara \\ exibic¸a˜o da matriz resultante escreva(’Resultado:’) para I de 1 ate´ 3 fac¸a para J de 1 ate´ 5 fac¸a escreva(M[I,J],’ ’) fimpara fimpara Fim 2. Dada uma matriz de 4 x 5 elementos inteiros, calcular a soma de cada linha, de cada coluna e de todos os seus elementos. Obs: utilize um vetor para armazenar o resultado da soma de cada linha e outro para a soma de cada coluna. Soluc¸a˜o: Algoritmo”Soma” var M : matriz[1..4,1..5] de inteiros Algoritmos I Edezio 14 L : vetor[1..4] de inteiros C : vetor[1..5] de inteiros I,J,SOMA : inteiros In´ıcio \\ leitura da matriz para I de 1 ate´ 4 fac¸a para J de 1 ate´ 5 fac¸a (’Elemento da linha’,I,’coluna’,J,’:’) leia(M[I,J]) fimpara fimpara \\ ca´lculo da soma dos elementos de cada linha para I de 1 ate´ 4 fac¸a L[I] ← 0 para J de1 ate´ 5 fac¸a L[I] ← L[I] + M[I,J] fimpara fimpara \\ ca´lculo da soma dos elementos de cada coluna para J de 1 ate´ 5 fac¸a C[J] ← 0 para I de 1 ate´ 4 fac¸a C[J] ← C[J] + M[I,J] fimpara fimpara \\ ca´lculo da soma de todos os elementos da matriz SOMA ← 0 para I de 1 ate´ 4 fac¸a para J de 1 ate´ 5 fac¸a SOMA ← SOMA + M[I,J] fimpara fimpara \\ exibic¸a˜o dos resultados para I de 1 ate´ 4 fac¸a escreva(’Soma da Linha’,I,’:’, L[I]) fimpara para J de 1 ate´ 5 fac¸a escreva(’Soma da Coluna’,J,’:’, C[J]) fimpara escreva(’Soma da Matriz:’, SOMA) Fim
Compartilhar