| Página
concebida e mantida por Eng. Manuel Menezes de Sequeira (última actualização 2006/07/07) Copyright © 1996-2001 ISCTE |
 |
|||
Existem muitas soluções para este problema. Serão apresentadas duas. A primeira não recorre a quaisquer variáveis auxiliares nem afecta os valores da variáveis, limitando-se a considerar todos os casos possíveis. A segunda recorre a uma variável auxiliar de modo a simplificar os testes e afecta os valores das variáveis.
A segunda solução pode considerar-se melhor que a primeira porque:
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito qual o maior e qual o mais pequeno de tres valores
lidos da entrada.
}
maior_menor_1
inicio
inteiro a, b, c, temp;
escrever linha;
escrever "Introduza tres valores: ";
ler para a, b, c;
(* No final "a" guardara' o menor dos valores e "b" guardara' o maior
dos valores. *)
se a > b:
(* Troca "a" com "b" de modo a que "a < b": *)
temp <- a;
a <- b;
b <- temp;
fim se;
(* Neste instante e' garantido que a <= b. *)
(* Se "c > b", entao "c" e' o maior e "a" o mais pequeno, caso contrario
temos "c <= b", logo "c" so' "ameaca" "a" (dai a comparacao subsequente
com "a"). *)
se c > b:
b <- c;
senao:
se c < a:
a <- c;
fim se;
fim se;
escrever "Menor: ", a, linha;
escrever "Maior: ", b, linha;
fim.
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito qual o maior e qual o mais pequeno de tres valores
lidos da entrada.
}
maior_menor_2
inicio
inteiro a, b, c;
escrever linha;
escrever "Introduza tres valores: ";
ler para a, b, c;
se a >= b:
se c >= a:
(* c e' o maior e b e' o menor. *)
escrever "Maior: ", c, linha, "Menor: ", b, linha;
senao:
(* a e' o maior. *)
escrever "Maior: ", a, linha;
se c <= b:
(* c e' o menor. *)
escrever "Menor: ", c, linha;
senao:
(* b e' o menor. *)
escrever "Menor: ", b, linha;
fim se;
fim se;
senao:
se c >= b:
(* c e' o maior e a e' o menor. *)
escrever "Maior: ", c, linha, "Menor: ", a, linha;
senao:
(* b e' o maior. *)
escrever "Maior: ", b, linha;
se c <= a:
(* c e' o menor. *)
escrever "Menor: ", c, linha;
senao:
(* a e' o menor. *)
escrever "Menor: ", a, linha;
fim se;
fim se;
fim se;
fim.
Neste caso procura-se o menor e o maior de vinte valores. Claro que seria possível declarar vinte variáveis e testar todas as possíveis combinações de maior e menor (20 x 19 = 380 !), mas o algoritmo tornar-se-ia demasiado extenso, quase incompreensível e, pior, se se pretendesse alterar de 20 para 30 o número de valores a comparar todo o algoritmo deveria ser alterado. Assim, a melhor solução neste caso é semelhante à pior solução na alínea anterior.
A ideia é ir actualizando duas variáveis, minimo
e maximo à medida que novos valores são lidos, um
pouco como se fez quando se somaram n valores [Aula 2,
exercício 4.a)]. Com que valor devem ser inicializados minimo
e maximo? Existem "elementos neutros" das
comparações a fazer? Existem conceptualmente apenas: +infinito
para o menor e -infinito para o maior. A solução então pode
ser inicializar com ... o primeiro valor lido, como aliás se
poderia ter feito no caso da soma.
A única desvantagem deste método é que não é possível saber o menor e o maior valor duma sequência de zero valores, mas isso provavelmente também não faria muito sentido.
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito qual o maior e qual o mais pequeno de vinte valores
lidos da entrada.
}
maior_menor_de_vinte
inicio
inteiro valor, minimo, maximo;
escrever linha;
escrever "Introduzir 20 valores:", linha;
(* Ler o primeiro valor: *)
ler para valor;
(* Inicializar "minimo" e "maximo" com o primeiro valor: *)
minimo <- valor;
maximo <- valor;
(* Repetir 19 vezes (20-1) porque um dos valores ja' foi lido: *)
repetir 19 vezes:
ler para valor;
se valor > maximo:
maximo <- valor;
senao:
se valor < minimo:
minimo <- valor;
fim se;
fim se;
fim repetir;
escrever "Maior: ", maximo, linha, "Menor: ", minimo, linha;
fim.
Apresentam-se três alternativas, sucessivamente refinadas. Quais as vantagens e desvantagens relativas? Cumprirão todas o enunciado? Não! Em rigor só a primeira alternativa cumpre o enunciado (que pede explicitamente para serem lidos 20 valores). As alternativas 2 e 3 são apresentadas para exemplificar soluçãos típicas para problemas em que é lícito "curto-circuitar" o ciclo terminando-o prematuramente.
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito se ocorreu o valor 7 alguma vez em 20 valores
lidos da entrada.
}
ocorre_7_1
inicio
inteiro valor;
logico ocorreu_sete;
escrever linha;
escrever "Introduzir 20 valores:", linha;
(* Inicializar "ocorreu_sete" com "falso": *)
ocorreu_sete <- falso;
repetir 20 vezes:
ler para valor;
se valor = 7:
ocorreu_sete <- verdadeiro;
fim se;
fim repetir;
escrever "O numero 7 ";
se nao ocorreu_sete:
escrever "nao ";
escrever "ocorreu.", linha;
fim.
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito se ocorreu o valor 7 alguma vez em 20 valores
lidos da entrada.
}
ocorre_7_2
inicio
inteiro valor, contador;
logico ocorreu_sete;
escrever linha;
escrever "Introduzir 20 valores:", linha;
(* Inicializar "contador" com zero: *)
contador <- 0;
(* Inicializar "ocorreu_sete" com "falso": *)
ocorreu_sete <- falso;
enquanto contador < 20 e nao ocorreu_sete:
ler para valor;
se valor = 7:
ocorreu_sete <- verdadeiro;
fim se;
contador <- contador + 1;
fim enquanto;
escrever "O numero 7 ";
se nao ocorreu_sete:
escrever "nao ";
escrever "ocorreu.", linha;
fim.
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito se ocorreu o valor 7 alguma vez em 20 valores
lidos da entrada.
}
ocorre_7_3
inicio
inteiro valor, contador;
escrever linha;
escrever "Introduzir 20 valores:", linha;
(* Inicializar "contador" com zero: *)
contador <- 0;
fazer:
ler para valor;
contador <- contador + 1;
enquanto contador < 20 e valor 7;
escrever "O numero 7 ";
se valor 7:
escrever "nao ";
escrever "ocorreu.", linha;
fim.
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito quantas vezes ocorreu o valor 7 em 20 valores
lidos da entrada.
}
quantos_7
inicio
inteiro valor, quantos;
escrever linha;
escrever "Introduzir 20 valores:", linha;
(* Inicializar "quantos" com o elemento neutro da adicao: *)
quantos <- 0;
repetir 20 vezes:
ler para valor;
se valor = 7:
quantos <- quantos + 1;
fim se;
fim repetir;
escrever "O numero 7 ocorreu ", quantos, "vezes.", linha;
fim.
A solução deste problema é um pouco mais subtil que a
solução da alínea b). Neste caso é necessário manter um
contador de ocorrências e verificar se o valor lido é igual ao maximo
corrente (se o for o número de ocorrências é incrementado).
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito qual o maior de vinte valores lidos da entrada
e quantas vezes ocorreu.
}
maior_de_vinte_e_ocorrencias
inicio
inteiro valor, maximo, contador;
escrever linha;
escrever "Introduzir 20 valores:", linha;
(* Ler o primeiro valor: *)
ler para valor;
(* Inicializar "maximo" com o primeiro valor: *)
maximo <- valor;
(* Inicializar "contador" com um (porque?): *)
contador <- 1;
(* Repetir 19 vezes (20-1) porque um dos valores ja' foi lido: *)
repetir 19 vezes:
ler para valor;
se valor > maximo:
maximo <- valor;
contador <- 1;
senao:
se valor = maximo:
contador <- contador + 1;
fim se;
fim se;
fim repetir;
escrever "Maior: ", maximo, linha, "Ocorrencias: ", contador, linha;
fim.
Neste caso a solução passa por utilizar uma acção cíclica
enquando (note-se que há uma solução alternativa
com fazer enquanto). Mas existe um
problema: se o primeiro valor lido for negativo que fazer?
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito qual o maior dos valores lidos da entrada
ate' ao primeiro negativo (exclusive') e quantas vezes ocorreu.
}
maior_e_ocorrencias_ate_negativo
inicio
inteiro valor, maximo, contador;
escrever linha;
escrever "Introduzir valores (terminar com negativo):", linha;
(* Ler primeiro valor: *)
ler para valor;
(* Se o primeiro valor lido e' negativo, a sequencia esta' vazia: *)
se valor < 0:
escrever "Nao se leu nenhum valor!", linha;
senao:
(* Porque^ esta atribuicao? *)
maximo <- valor;
(* Contador e' zero porque dentro do enquanto, e antes de ser lido
novo valor, o contador sera' incrementado
(ja' que maximo = valor): *)
contador <- 0;
(* Enquanto "valor" nao for negativo... *)
enquanto valor >= 0:
(* O valor e' o novo maximo? *)
se valor > maximo:
maximo <- valor;
contador <- 1;
senao:
(* O valor e' de novo o maximo? *)
se valor = maximo:
contador <- contador + 1;
fim se;
fim se;
(* Ler proximo valor: *)
ler para valor;
fim enquanto;
escrever "Maior: ", maximo, linha, "Ocorrencias: ", contador, linha;
fim se;
fim.
Notem-se os seguintes problemas:
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito se uma sequencia de valores lidos da entrada,
ate' ao primeiro zero (exclusive'), esta' por ordem crescente.
}
sequencia_crescente
inicio
inteiro valor, valor_anterior;
escrever linha;
escrever "Introduzir valores (terminar com zero):", linha;
(* Ler primeiro valor: *)
ler para valor;
(* Inicializar valor_anterior com valor, pois nao "estraga" o teste
de ordem... *)
valor_anterior <- valor;
(* Enquanto "valor" nao for zero... *)
enquanto valor <> 0 e valor >= valor_anterior:
valor_anterior <- valor;
(* Ler proximo valor: *)
ler para valor;
fim enquanto;
(*
* Aqui so' se chega se:
* 1. valor = 0 (e todos os valores (se e' que se leu algum!) estavam por
* ordem crescente!);
* 2. valor 0 e valor < valor_anterior (encontrou-se um valor fora de
* ordem).
* Por outro lado, se valor_anterior = 0 entao nao ouve valores lidos,
* pois de outro modo valor_anterior teria sido atribuido de valor,
* sendo forcosamente nao nulo.
*)
se valor_anterior = 0:
escrever "Nao se leu nenhum valor!", linha;
senao:
escrever "A sequencia ";
se valor <> 0:
escrever "nao ";
fim se;
escrever "estava por ordem crescente.", linha;
fim se;
fim.
Note-se que mais uma vez esta solução viola o enunciado, porque pára no primeiro valor que viole a condição de sequência crescente! Como se poderia corrigir o algoritmo?
{ (* Pressupostos: *)
}
{ (* Resultado a atingir: *)
Deve aparecer escrito se uma sequencia de valores lidos da entrada,
ate' ao primeiro zero (exclusive'), e' mono'tona.
}
sequencia_mono'tona
inicio
inteiro valor, valor_anterior;
logico constante, crescente;
escrever linha;
escrever "Introduzir valores (terminar com zero):", linha;
(* Inicializar "constante" ("crescente" nao precisa de ser inicializado
porque ainda nao tem significado!): *)
constante <- verdadeiro;
(* Ler primeiro valor: *)
ler para valor;
(* Inicializar valor_anterior com valor, pois nao "estraga" o teste
de ordem... *)
valor_anterior <- valor;
(* Enquanto "valor" nao for zero e for coerente com o estado... *)
enquanto valor <> 0 e
(constante ou
(valor >= valor_anterior e crescente) ou
(valor <= valor_anterior e nao crescente)):
se constante:
se valor > valor_anterior:
constante <- falso;
crescente <- verdadeiro;
senao:
se valor < valor_anterior:
constante <- falso;
crescente <- falso;
fim se;
fim se;
fim se;
valor_anterior <- valor;
(* Ler proximo valor: *)
ler para valor;
fim enquanto;
(*
* Aqui so' se chega se:
* 1. valor = 0 (e todos os valores (se e' que se leu algum!) estavam por
* ordem mono'tona!);
* 2. valor 0 e nao constante e nao (valor >= valor_anterior e
* crescente) e nao (valor <= valor_anterior e nao crescente), ou seja
* se se encontrou um valor fora de ordem.
* Por outro lado, se valor_anterior = 0 entao nao ouve valores lidos,
* pois de outro modo valor_anterior teria sido atribuido de valor,
* sendo forcosamente nao nulo.
*)
se valor_anterior = 0:
escrever "Nao se leu nenhum valor!", linha;
senao:
escrever "A sequencia ";
se valor <> 0:
escrever "nao ";
fim se;
escrever "e' monotona.", linha;
se valor = 0:
se constante:
escrever "E' constante.", linha;
senao:
se crescente:
escrever "E' crescente.", linha;
senao:
escrever "E' decrescente.", linha;
fim se;
fim se;
fim se;
fim se;
fim.
Note-se que mais uma vez esta solução viola o enunciado, porque pára no primeiro valor que viole a condição de sequência monótona! Como se poderia corrigir o algoritmo?
O problema fundamental a resolver é saber se um dado valor n é ou não primo. O método mais simples - e menos eficiente! - para resolver este problema é tentar dividir n por todos os valores de 2 a n - 1. Se o resto da divisão for nulo alguma vez, o número não é primo. Se o resto nunca for nulo, o número é primo:
{ (* Pressupostos: *)
n > 2
}
{ (* Resultado a atingir: *)
Deve aparecer escrita a seque^ncia dos primos de 2 a n, sendo n lido da
entrada.
}
primeiros_primos
inicio
inteiro n, valor, divisor;
escrever linha;
escrever "Primos ate': ";
ler para n;
(* E' escusado testar o 2, que sabemos ser primo... *)
escrever 2, linha;
para valor <- 3, n:
divisor <- 2;
enquanto divisor < valor e valor mod divisor 0:
divisor <- divisor + 1;
fim enquanto;
se divisor = valor:
escrever valor, linha;
fim se;
fim para;
fim.
Para além do método sugerido no texto, muitos outros há para acelerar a verificação de se um número é primo. Por exemplo, é claro que se n não é divisível por 2 também não o é por nenhum valor maior que n div 2. Aliás, em geral basta testar com divisores d tais que d^2 <= n!
Se existir algum mecanismo de guardar os números primos conhecidos, então ainda é possível tornar mais eficiente o algoritmo se se verificar que basta testar se n é divisível pelos primos d até d^2 <= n!
A solução seguinte é a mais óbvia, e porventura a menos eficiente:
{ (* Pressupostos: *)
a, b > 0
}
{ (* Resultado a atingir: *)
Deve aparecer escrito o mdc de a e b.
}
mdc_1
inicio
inteiro a, b, divisor;
escrever linha;
escrever "Mdc de: ";
ler para a, b;
(* Como o mdc nao pode ser maior que o menor dos valores "a" e "b"... *)
se a < b:
divisor <- a;
senao:
divisor <- b;
fim se;
(* Testar divisores desde o menor de "a" e "b" ate' 1: *)
enquanto divisor <> 1 e (a mod divisor <> 0 ou b mod divisor <> 0):
divisor <- divisor - 1;
fim enquanto;
escrever divisor, linha;
fim.
É fácil provar que se m é o mdc de a e b
(ambos positivos), m também é o mdc de b e a
mod b. Note-se que a demonstração abaixo
é válida mesmo quando a mod b =
0, embora nesse caso o mdc seja obviamente b.
Seja m o mdc de a e b. Então, existem c e d tais que:
a = m c
b = m d
Seja r = a mod b e q = a div b. Então a = b q + r.
Ou seja:
m c = m d q + r.
Donde:
r = m (c - d q)
Assim, provou-se que r = a mod b é divisível por m.
Falta apenas provar que m é não só divisor de b e r = a mod b, mas também o maior dos divisores de b e r.
Suponha-se que existe n > m divisor de b e r. Então existem x e y tais que:
b = n x
r = n y
Mas:
q n x + n y = q b + r = a
Por outro lado:
q n x + n y = n (q x + y)
Logo:
a = n (q x + y)
Ou seja, n não só divide b como também divide a! Logo m não é o mdc de a e b, o que é absurdo. Assim, não existe nenhum divisor de b e r maior do que m, ou seja m é o mdc de b e r.
Dados a e b, duas coisas podem acontecer:
mod b = 0 - neste caso o
mdc é o próprio b. mod b = d 0 -
neste caso o mdc de a e b é o mesmo
que o de b e d, tendo-se assim reduzido
o problema, pois d é menor que a e b.
Note-se que se a < b então a mod
b é a, mas b mod a
é menor que a! Assim, há vantagem em calcular o resto
da divisão inteira do valor maior pelo valor menor!
{ (* Pressupostos: *)
a, b > 0
}
{ (* Resultado a atingir: *)
Deve aparecer escrito o mdc de a e b.
}
mdc_2
(* Algoritmo de Euclides. *)
inicio
inteiro a, b, temp;
escrever linha;
escrever "Mdc de: ";
ler para a, b;
enquanto b <> 0;
temp <- b;
b <- a mod b;
a <- temp;
(* Ou seja, calculou-se "d = a mod b", e ficou "b" com o valor de "d"
e "a" com o valor de "b". Desta forma, a proxima divisao faz-se pelo
valor mais baixo ("d")! *)
fim enquanto;
(* Aqui "b" e' sempre zero, e "a" tem o valor antigo de "b", o tal que
conduziu ao resto zero, ou seja, o mdc! *)
escrever a, linha;
fim.
Faça o traçado com 123 (3 x 41) e 321 (3 x 107), cujo mdc é 3, e com 89 (89) e 144 (2^4 x 3^2), mdc 1, para se convencer de que o algoritmo funciona...
| Página
concebida e mantida por Eng. Manuel Menezes de Sequeira (última actualização 2006/07/07) Copyright © 1996-2001 ISCTE |
|
|||