ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I717 materiais7.910 seguidores
Pré-visualização50 páginas
8.16: Calcula MDC entre a e b pela definic¸a\u2dco (caso primo e´ \u131´mpar).
104 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
8.6 Exerc´\u131cios
1. Fazer um programa em Pascal que leia do teclado dois nu´meros inteiros posi-
tivos e que imprima na sa´\u131da um u´nico nu´mero inteiro que e´ a soma dos dois
primeiros. Entretanto, seu programa na\u2dco pode utilizar o operador de soma (+)
da linguagem Pascal para somar os dois inteiros lidos em uma u´nica operac¸a\u2dco.
Outrossim, o programa deve implementar a soma dos nu´meros d´\u131gito a d´\u131gito,
iniciando pelo menos significativo ate´ o mais significativo, considerando o \u201cvai
um\u201d, conforme costumamos fazer manualmente desde o ensino fundamental.
Exemplo 1 Exemplo 2
11 ("vai um") 1111 ("vai um")
40912 (primeiro nu´mero) 52986 (primeiro nu´mero)
1093 (segundo nu´mero) 1058021 (segundo nu´mero)
----- -------
42005 (soma) 1111007 (soma)
2. Um agricultor possui 1 (uma) espiga de milho. Cada espiga tem 150 gra\u2dcos, e cada
gra\u2dco pesa 1g (um grama). Escreva um programa em Pascal para determinar
quantos anos sera\u2dco necessa´rios para que o agricultor colha mais de cem toneladas
de milho (1T = 1000Kg, 1Kg = 1000g), sendo que:
\u2022 A cada ano ele planta todos os gra\u2dcos da colheita anterior
\u2022 Ha´ apenas uma colheita por ano
\u2022 10% (dez por cento) dos gra\u2dcos na\u2dco germina (morre sem produzir)
\u2022 Cada gra\u2dco que germina produz duas espigas de milho
Assuma que a quantidade de terra dispon´\u131vel e´ sempre suficiente para o plantio.
3. Modifique a questa\u2dco anterior acrescentando na simulac¸a\u2dco os seguintes fatos:
\u2022 Ha´ 8 (oito) CASAIS de pombas (16 pombas) que moram na propriedade
do agricultor.
\u2022 Cada pomba come 30 gra\u2dcos por dia, durante os 30 dias do ano em que as
espigas esta\u2dco formadas antes da colheita;
\u2022 A cada ano, cada casal gera 2 novos casais (4 pombas), que se alimentara\u2dco
e reproduzira\u2dco no ano seguinte;
\u2022 Uma pomba vive tres anos;
Ao final do programa, imprima tambe´m o nu´mero de pombas que vivem na
propriedade quando o agricultor colher mais de 100T de milho
8.6. EXERCI´CIOS 105
4. Considere um nu´mero inteiro com 9 d´\u131gitos. Suponha que o u´ltimo d´\u131gito seja
o \u201cd´\u131gito verificador\u201d do nu´mero formado pelos 8 primeiros. Fac¸a um programa
em Pascal que leia uma massa de dados terminada por 0 (zero) e que imprima os
nu´meros que na\u2dco sa\u2dco bem formados, isto e´, aqueles que na\u2dco satisfazem o d´\u131gito
verificador. Implemente o seguinte algoritmo para gerar o d´\u131gito verificador:
Conforme o esquema abaixo, cada d´\u131gito do nu´mero, comec¸ando da direita para
a esquerda (menos significativo para o mais significativo) e´ multiplicado, na
ordem, por 2, depois 1, depois 2, depois 1 e assim sucessivamente.
Nu´mero exemplo: 261533-4
+---+---+---+---+---+---+ +---+
| 2 | 6 | 1 | 5 | 3 | 3 | - | 4 |
+---+---+---+---+---+---+ +---+
| | | | | |
x1 x2 x1 x2 x1 x2
| | | | | |
=2 =12 =1 =10 =3 =6
+---+---+---+---+---+-> = (16 / 10) = 1, resto 6 => DV = (10 - 6) = 4
Ao inve´s de ser feita a somato´ria das multiplicac¸o\u2dces, sera´ feita a somato´ria
dos d´\u131gitos das multiplicac¸o\u2dces (se uma multiplicac¸a\u2dco der 12, por exemplo, sera´
somado 1 + 2 = 3).
A somato´ria sera´ dividida por 10 e se o resto (mo´dulo 10) for diferente de zero,
o d´\u131gito sera´ 10 menos este valor.
5. Escreva um programa Pascal que leia dois valores inteiros positivos A e B. Se
A for igual a B, devem ser lidos novos valores ate´ que sejam informados valores
distintos. Se A for menor que B, o programa deve calcular e escrever a soma dos
nu´meros \u131´mpares existentes entre A(inclusive) e B(inclusive). Se A for maior
que B, o programa deve calcular e escrever a me´dia aritme´tica dos mu´ltiplos de
3 existentes entre A(inclusive) e B(inclusive).
6. Fac¸a um programa em Pascal que dado uma seque\u2c6ncia de nu´meros inteiros
terminada por zero (0), determinar quantos segmentos de nu´meros iguais con-
secutivos compo\u2dcem essa seque\u2c6ncia.
Ex.: A seque\u2c6ncia 2,2,3,3,5,1,1,1 e´ formada por 4 segmentos de nu´meros iguais.
7. Fac¸a um programa em Pascal que imprima a seguinte seque\u2c6ncia de nu´meros: 1,
1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, . . .
8. Fac¸a um programa em Pascal que receba como entrada um dado inteiro N e
o imprima como um produto de primos. Exemplos: 45 = 3 × 3 × 5. 56 =
2× 2× 2× 7.
106 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
9. Fac¸a um programa em Pascal que, dado um nu´mero inteiro N , escreva o maior
divisor de N que e´ uma pote\u2c6ncia de um dos nu´meros primos fatorados. Ex:
N = 45 = 32.51 escreve 9 = 32
N = 145 = 52.71 escreve 25 = 52
N = 5616 = 24.33.13 escreve 27 = 33
Cap´\u131tulo 9
Func¸o\u2dces e procedimentos
Ate´ agora vimos as noc¸o\u2dces ba´sicas de algoritmos, fundamentalmente como funciona
o computador de verdade (modelo Von Neumann) e como isto pode ter uma repre-
sentac¸a\u2dco em um n´\u131vel mais alto, guardadas as limitac¸o\u2dces da ma´quina.
A maneira de se resolver problemas do ponto de vista algoritmico envolve a ela-
borac¸a\u2dco de construc¸o\u2dces com apenas quatro tipos de estruturas de controle de fluxo:
comandos de entrada e sa´\u131da, comandos de atribuic¸a\u2dco, comandos de repetic¸a\u2dco e co-
mandos de desvio condicional, ale´m do uso de expresso\u2dces lo´gicas e aritme´ticas. Para
a efetiva programac¸a\u2dco ainda e´ necessa´rio dominar a arte de escrever os algoritmos em
func¸a\u2dco das limitac¸o\u2dces dos compiladores.
O problema e´ que a` medida em que os problemas exigem co´digos com muitas
linhas, os programas gerados va\u2dco se tornando cada vez mais complexos tanto para
serem desenvolvidos quanto para serem mantidos em funcionamento. O exemplo do
final do cap´\u131tulo anterior da´ uma ideia dessa dificuldade.
Por isto, os programas devem ser constru´\u131dos de maneira a facilitar o trabalho
dos programadores e analistas. E´ preciso que os co´digos sejam elaborados com partes
bem definidas, em mo´dulos que contenham pedac¸os coerentes do problema geral que
se esta´ tentando modelar. As noc¸o\u2dces de func¸o\u2dces e procedimentos sa\u2dco o caminho para
se construir co´digos elegantes, robustos e de fa´cil manutenc¸a\u2dco.
9.1 Motivac¸a\u2dco
Os procedimentos e func¸o\u2dces sa\u2dco nada mais do que subprogramas, isto e´, pedac¸os de
programas dentro de programas. Mas, bem explorados, permitem a construc¸a\u2dco de
co´digos altamente elaborados. Existem tre\u2c6s motivac¸o\u2dces para se usar subprogramas:
\u2022 modularidade;
\u2022 reaproveitamento de co´digo;
\u2022 legibilidade do co´digo.
Vamos detalhar cada to´pico nos pro´ximos itens.
107
108 CAPI´TULO 9. FUNC¸O\u2dcES E PROCEDIMENTOS
9.1.1 Modularidade
A noc¸a\u2dco de modularidade e´ relacionada com a capacidade de se escrever programas
em pedac¸os de co´digo que executam operac¸o\u2dces bem definidas. Cada mo´dulo possui
varia´veis e estruturas pro´prias, independentes do restante do programa. A ideia e´ que
modificac¸o\u2dces em trechos de co´digo (necessa´rias para manutenc¸a\u2dco e continuidade de
desenvolvimento) na\u2dco causem reflexos no comportamento do resto do programa.
E´ fa´cil conceber um programa dividido em tre\u2c6s partes: entrada de dados, ca´lculos e
impressa\u2dco dos resultados. Uma entrada de dados textual poderia ser modificada para
outra em modo gra´fico sem que o pedac¸o que faz os ca´lculos perceba a modificac¸a\u2dco.
Idem para a sa´\u131da de dados. Mesmo nos ca´lculos, pode-se mudar toda uma estrutura
do programa e garantir que a entrada e sa´\u131da va\u2dco continuar a se comportar como
antes. Isto e´ tarefa a´rdua sem o uso de func¸o\u2dces e procedimentos.
E´ importante notar que a linguagem Pascal na\u2dco fornece todos os meios para se
implementar um programa totalmente modular, mas e´ o suficiente para os estudantes
em primeiro curso de computac¸a\u2dco perceberem a importa\u2c6ncia do conceito. Na verdade,
a evoluc¸a\u2dco destas ideias deu origem ao conceito de Programac¸a\u2dco Orientada a Objetos,
hoje na moda. Mas isto e´ tema para outras disciplinas.
9.1.2 Reaproveitamento de co´digo
Vez por outra nos deparamos com situac¸o\u2dces onde temos que escrever co´digos muito,
mas muito, parecidos em trechos diferentes do programa. As vezes a diferenc¸a de um
para outro e´ questa\u2dco