Baixe o app para aproveitar ainda mais
Prévia do material em texto
Programação de Computadores Prof. Eduardo Chaves Faria Solução do 3o Exercício 1 – A subrotina “Determina” retorna verdadeiro em Ok caso o segundo parâmetro seja divisor do primeiro. Então, o algoritmo escreve os valores de 1 a 9 que são divisores de X ou divisores de Y. Por exemplo, no caso de X = 8 e Y = 6, a saída será igual a 1, 2, 3, 4, 6 e 8. 2 – Este problema teve como objetivo mostrar como a solução dada para classificação de três números torna-se inviável para uma quantidade maior de valores. Observe este algoritmo e imagine se fossem 10 ou 100 valores! Mais adiante, quando estudarmos as variáveis compostas (Cap.2 do livro ) veremos uma solução única para qualquer quantidade de valores. { Classifica cinco números quaisquer em ordem crescente } Algoritmo Defina o tipo das variáveis leia A, B, C, D, E se A > B e A > C e A > D e A > E então Primeiro ← A Ordena os números B, C, D e E senão se B > C e B > D e B > E então Primeiro ← B Ordena os números A, C, D e E senão se C > D e C > E então Primeiro ← C Ordena os números A, B, D e E Senão se D > E então Primeiro ← D Ordena os números A, B, C e E senão Primeiro ← E Ordena os números A, B, C e D Fim se fim se fim se fim se escreva Quinto, Quarto, Terceiro, Segundo, Primeiro fim algoritmo ref: Defina o tipo das variáveis declare A, B, C, D { números quaisquer } Primeiro, Segundo, Terceiro, Quarto, Quinto { números ordenados } numérico fim ref Observando os cinco refinamentos que faltam, concluímos que todos eles possuem uma única funcionalidade, ou seja, ordenar quatro números quaisquer. Assim, vamos criar uma subrotina que recebe quatro valores quaisquer e devolve estes quatro valores ordenados. { Classifica quatro números quaisquer } subrotina OrdenaQuatroValores ( X, Y, W, Z, Maior, SegundoMaior, TerceiroMaior, Menor ) declare X, Y, W, Z { entrada: números quaisquer } Maior, SegundoMaior, TerceiroMaior, Menor { saída: números ordenados } numérico se X > Y e X > W e X > Z então Maior ← X Ordena os números Y, W e Z senão se Y > W e Y > Z então Maior ← Y Ordena os números X, W e Z Senão se W > Z então Maior ← W Ordena os números X, Y e Z senão Maior ← Z Ordena os números X, Y e W Fim se fim se fim se fim subrotina Observando os quatro refinamentos que faltam, concluímos que todos eles possuem uma única funcionalidade, ou seja, ordenar três números quaisquer. Assim, vamos criar uma subrotina que recebe três valores quaisquer e devolve estes três valores ordenados. { Classifica três números quaisquer } subrotina OrdenaTresValores ( X, Y, Z, Maior, DoMeio, Menor ) declare X, Y, Z { entrada: números quaisquer } Maior, DoMeio, Menor { saída: números ordenados } numérico se X > Y e X > Z então Maior ← X Ordena os números Y e Z senão se Y > Z então Maior ← Y Ordena os números X e Z senão Maikor ← Z Ordena os números X e Y fim se fim se fim subrotina Observando os três refinamentos que faltam, concluímos que todos eles possuem uma única funcionalidade, ou seja, ordenar dois números quaisquer. Assim, vamos criar uma subrotina que recebe dois valores quaisquer e devolve estes dois valores ordenados. { Classifica dois números quaisquer } subrotina OrdenaDoisValores ( P, Q, Maximo, Minimo ) declare P, Q { entrada: números quaisquer } Maximo, Minimo { saída: números ordenados } numérico se P > Q então Maximo ← P Minimo ← Q senão Maximo ← Q Minimo ← P fim se fim subrotina Agora, substituímos cada frase dos refinamentos pela chamada da subrotina correspondente:: Ordena os números Y e Z → OrdenaDoisValores( Y, Z, DoMeio, Menor ) Ordena os números X e Z → OrdenaDoisValores( X, Z, DoMeio, Menor) Ordena os números Y e Z → OrdenaDoisValores( X, Y, DoMeio, Menor) Ordena os números Y, W e Z → OrdenaTresValores( Y, W, Z, SegundoMaior, TerceiroMaior, Menor ) Ordena os números X, W e Z → OrdenaTresValores( X, W, Z, SegundoMaior, TerceiroMaior, Menor ) Ordena os números X, Y e Z → OrdenaTresValores( X, Y, Z, SegundoMaior, TerceiroMaior, Menor ) Ordena os números X, Y e W → OrdenaTresValores( X, Y, W, SegundoMaior, TerceiroMaior, Menor ) Ordena os números B, C, D e E → OrdenaQuatroValores( B,C,D,E, Segundo, Terceiro, Quarto, Quinto ) Ordena os números A, C, D e E → OrdenaQuatroValores( A,C,D,E, Segundo, Terceiro, Quarto, Quinto ) Ordena os números A, B, D e E → OrdenaQuatroValores( A,B,D,E, Segundo, Terceiro, Quarto, Quinto ) Ordena os números A, B, C e E → OrdenaQuatroValores( A,B,C,E, Segundo, Terceiro, Quarto, Quinto ) Ordena os números A, B, C e D → OrdenaQuatroValores( A,B,C,D, Segundo, Terceiro, Quarto, Quinto ) 3 – { Números amigos compreendidos entre 1 e 1.000.000 } Algoritmo Declare X, Y { candidatos a números amigos } SomaDivX { soma dos divisores de X } SomaDivY { soma dos divisores de Y } numérico X ← 1 repita Y ← X + 1 { procura os amigos de X } repita CalculaSomaDivisores( X, SomaDivX ) CalculaSomaDivisores( Y, SomaDivY ) se SomaDivX = Y e X = SomaDivY então escreva X, Y fim se Y ← Y + 1 se Y > 1.000.000 então interrompa fim se fim repita X ← X + 1 se X > 999.999 então interrompa fim se fim repita fim algoritmo { determina a soma dos divisores próprios de um número} subrotina CalculaSomaDivisores( N, Soma ) declare N { entrada: número inteiro positivo } Soma { saída: soma dos divisores de N } D { possível divisor de N } numérico Soma ← 0 D ← 1 repita se D ≥ N então interrompa fim se se Resto( N,D ) = 0 então Soma ← Soma + D fim se D ← D + 1 fim repita fim função Observação: A solução apresentada não é nada eficiente. A subrotina CalculaSomaDivisores é chamada 2 x 1012 vezes, e tomando o no N médio igual a 500.000, o teste de um possível divisor dentro da subrotina é feito 1018 vezes. As seguintes modificações tornariam o algoritmo bem mais eficiente: - Alterar a subrotina para testar possíveis divisores até a raiz quadrada do número; - No programa, chamar a subrotina para calcular a soma dos divisores de X fora da repetição mais interna, pois dentro dela o valor de X não se altera. 4 – { determina e escreve os números abundantes contidos em um dado intervalo } Algoritmo declare A, B { números inteiros que definem o intervalo – fornecidos como entrada } K { número do intervalo candidato a abundante } numérico declare Abundante { sinaliza resultado da verificação } lógico leia A, B K ← A repita se K > B então interrompa fim se VerificaSeNumeroAbundante( K, Abundante } se Abundante então escreva K fim se K ← K + 1 fim repita fim algoritmo { Verifica se um dado número é Abundante } subrotina VerificaSeNumeroAbundante( N, Ok ) declare N { entrada: número candidato a abundante } D { possível divisor } SomaDiv { soma dos divisores } numérico Declare Ok { saída: sinaliza se N é ou não um número abundante } lógico SomaDiv ← 1 + N D ← 2 repita se D > N / 2 então interrompa fim se se Resto( N, D ) = 0 então SomaDiv ← SomaDiv + Dfim se D ← D + 1 fim repita se SomaDiv > 2 x N então Abundante ← verdadeiro senão Abundante ← falso fim se fim função 5 – { Contabiliza um voto de uma eleição presidencia com três canditados } subrotina ContabilizaVotoDoEleitor ( Voto, Cont1, Cont2, Cont3, Nulos ) declare Voto { entrada : Voto de um eleitor a ser contabilizado } Cont1 { entrada/saída : Contador de votos do candidato número 1 } Cont2 { entrada/saída : Contador de votos do candidato número 2 } Cont3 { entrada/saída : Contador de votos do candidato número 3 } Nulos { entrada/saída : Contador de votos nulos } numérico se Voto = 1 então Cont1 ← Cont1 + 1 senão se Voto = 2 então Cont2 ← Cont2 + 1 senão se Voto = 3 então Cont3 ← Cont3 + 1 senão Nulos ← Nulos + 1 fim se fim se fim se fim subrotina 6 – { Tabula o valor de Pi em função da precisão utilizada no cálculo } Algoritmo declare Ntermos { Número de termos utilizados no cálculo de pi para atingir a Precisão dada } Pi { Valor aproximado para pi } Precisao { Precisão para o cálculo do valor de pi } numérico Precisao ← 10−1 repita CalculaNumeroPi( Precisao, Pi, Ntermos ) escreva Precisao, Pi, Ntermos Precisao ← Precisao x 10−1 se Precisão < 10−10 então interrompa fim se fim repita fim algoritmo { Calcula o valor de pi com uma dada precisão e também retorna o número de termos utilizados da série } subrotina CalculaNumeroPi( Pecisao, ValorPi, NT ) declare Precisao { Entrada: valor da precisao para cálculo do número pi } ValorPi { Saída: valor do número pi com a precisão informada } NT { Saida: número de termos utilizados da série para atingir a precisão } S { Valor da série } N { Assume valores ímpares para cálculo do denominador da série} Sinal { Usado para alternar o sinal de cada termo da série} numérico ValorPi ← 4 NT ← 1 N ← 3 Sinal ← −1 repita se 4/N < Precisao então { quando o termo a ser acumulado é menor que a precisão } interrompa fim se ValorPi ← ValorPi + ( 4 / N x Sinal ) NT ← NT + 1 N ← N + 2 Sinal ← − Sinal fim repita fim subrotina 7 – { Calcula a raiz quadrada de um número com precisão de 10-2 } subrotina CalculaRaizQuadrada( Y, X ) declare Y { entrada: número do qual se deseja calcular a raiz quadrada } X { saída: raiz quadrada de Y } Xant { aproximação anterior da raiz quadrada } numérico X ← Y / 2 { 1ª aproximação } repita Xant ← X X ← (X2 + Y) / (2 x X) se Abs( Xant – X ) < 0,01 então interrompa fim se fim repita fim subrotina
Compartilhar