Ex03 pc pascal solução

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