Algoritmo e Estrutura de Dados I

Aula 9 – Variáveis Compostas HomogêneasMárcia Marra

marsha@dcc.ufmg.br

2

Variáveis Compostas Homogêneas

• Correspondem a posições de memória, identificadas por um mesmo nome, individualizadas por índices e cujo conteúdo é do mesmo tipo.

• Exemplo:

60 70 90 60 55 91 99 47 47 86NOTA

1 2 3 4 5 6 7 8 9 10

3

Declaração de Variáveis Compostas Homogêneas

declare lista de identificadores [li:ls]tonde:

– declare: palavra chave– lista de identificadores: nomes associados às variáveis que se

deseja declarar– li: limite inferior do intervalo de variação dos índices– ls: limite superior do intervalo de variação dos índices– t: tipo dos componentes da variável (numérico,

literal, lógico)

• O limite superior não deve ser menor do que o limite inferior, ou seja, ls ≥ li

4

Alguns exemplos de declaração

• declare NOTA [1:10] numérico• declare VOOS [1:500] numérico• declare LIVROS [1:1000] numérico• declare GABARITO, RESPOSTAS [1:10] literal

• declare FREQUENCIA [0:10] numerico

5

Exemplo 1 – preenchimentoAlgoritmodeclare M[1:6] numéricodeclare I numéricoI ← 1repitase I > 6então interrompafim seM[I] ← 2I ← I + 1fim repitaescreva M[1], M[2] … M[6]

Fim Algoritmo

6

Exemplo 2• O algoritmo deve ler uma variável de 100

elementos e verificar se existem elementos iguais a 30. Se existirem, escrever as posições em que estão armazenados.

AlgoritmoDefina o tipo das variaveisleia NUMEROS[1] ... NUMEROS[100]Verifique se existem elementos iguais a 30

Fim Algoritmo

7

Refinamentos sucessivos do exemplo 2

Ref. Verifique se existem elementos iguais a 30I ← 1repita

se I > 100então interrompa

fim sese NUMEROS[I] = 30

então escreva Ifim seI ← I + 1

fim repitaFim Ref.Ref. Defina o tipo das variáveis

declare NUMEROS[1:100] numericodeclare I numerico

Fim Ref

8

Exemplo 2 – Algoritmo CompletoAlgoritmo

{ Declaracao do tipo das variaveis }declare NUMEROS[1:100] numericodeclare I numericoleia NUMEROS[1] ... NUMEROS[100]{ Verificacao da existencia de elementos iguais a 30 }I ← 1repita

se I > 100então interrompa

fim sese NUMEROS[I] = 30

então escreva Ifim seI ← I + 1

fim repitaFim Algoritmo

9

Exemplo 3• A diretoria do ICEx deseja saber se existem alunos

cursando, simultaneamente, Algoritmos e Estrutura de Dados I (AEDSI) e Cálculo Numérico (CN).

• Existem disponíveis na unidade de entrada os números de matrícula dos alunos de AEDSI (no máximo 150 alunos) e de CN (no máximo 220 alunos).

• Cada conjunto dos números de matrícula dos alunos de uma disciplina tem a matrícula fictícia 99999 no final.

• Formular um algoritmo que imprima o número de matrícula dos alunos que estão cursando estas disciplinas simultaneamente.

10

Exemplo 3 – Estrutura de Dados

• Este problema trata da verificação de ocorrência de um elemento de um conjunto em um outro conjunto.

...

1 2 3 4 5 ... 150 151

AEDS I

...

1 2 3 4 5 ... 220 221

CN

11

Exemplo 3 – Algoritmo em alto nível

AlgoritmoDeclare variaveisLeia matricula dos alunos que estao cursando AEDS ILeia matricula dos alunos que estao cursando CNVerifique a matricula simultanea em AEDS I e CN

Fim Algoritmo

12

Refinamentos sucessivos do algoritmo 3

Ref. Leia matricula dos alunos que estao cursando AEDSII ← 1repita

leia AEDSI [I] se AEDSI[I] = 9999

entao interrompafim seI ← I + 1

fim repitaFim Ref.Ref. Leia matricula dos alunos que estao cursando CN

I ← 1repita

leia CN [I] se CN[I] = 9999

entao interrompafim seI ← I + 1

fim repitaFim Ref.

13

Refinamentos sucessivos do algoritmo 3

Ref. Verifique a matricula simultanea em AEDSI e CNI ← 1repita

se AEDSI[I] = 9999entao interrompa

fim seJ ← 1repita

se CN[J] = 9999 ou AEDSI[I] = CN[J]entao interrompa

fim seJ ← J + 1

fim repitase AEDSI[I] = CN [J]

entao escreva AEDS[I]fim seI ← I + 1

fim repitaFim Ref.

14

Refinamentos sucessivos do exemplo 3

Ref. Declare as variaveisdeclare AEDSI[1:151],

CN [1:221]numérico

declare I, J numéricoFim Ref.

15

Exemplo 3 completo (1/2)Algoritmo

declare AEDSI[1:151], CN [1:221] numéricodeclare I, J numéricoI ← 1repitaleia AEDSI [I] se AEDSI[I] = 9999entao interrompafim seI ← I + 1fim repitaI ← 1repitaleia CN [I] se CN[I] = 9999entao interrompafim seI ← I + 1fim repita

16

Exemplo 3 completo (2/2)I ← 1

repitase AEDSI[I] = 9999

entao interrompafim seJ ← 1repita

se CN[J] = 9999 ou AEDSI[I] = CN[J]entao interrompa

fim seJ ← J + 1

fim repitase AEDSI[I] = CN [J]

entao escreva AEDS[I]fim seI ← I + 1

fim repitaFim Algoritmo

17

Exemplo 4• Escrever um algoritmo que faça reserva de passagens

aéreas de uma companhia.• Além da leitura do número de vôos e quantidade de

lugares disponíveis, ler vários pedidos de reserva, constituídos do número da carteira de identidade do cliente e do número do vôo desejado.

• Para cada cliente, verificar se há disponibilidade no vôo desejado. – Em caso afirmativo, imprimir o número da identidade do cliente e o

número do vôo, atualizando o número de lugares dosponíveis. – Caso contrário, avisar ao cliente da inexistência de lugares.

• Indicando o fim dos pedidos de reserva, existe um passageiro cujo número da carteira de identidade é 9999. Considerar fixo e igual a 37 o número de vôos da companhia.

18

Exemplo 4 – Estrutura de Dados

Número dos

Vôos

Lugares

Disponíveis

19

Exemplo 4 – alto nívelAlgoritmoleia VOOS[1] ... VOOS[37], LDISP[1] ... LDISP[37]repita

leia CLIENTE, NVOOse CLIENTE = 9999

entao interrompafim seVerifique a existencia de vooVerifique a existencia de lugar

fim repitaFim Algoritmo

20

Refinamentos sucessivos do Exemplo 4

Ref. Verifique a existência de vooI ← 0repita

I ← I + 1se I = 37 ou VOOS[I] = NVOO

entao interrompafim se

fim repitase VOOS[I] = NVOO

entao APONT ← Isenao escreva “VOO INEXISTENTE”

APONT ← 0fim se

Fim ref.

21

Refinamentos sucessivos do Exemplo 4

Ref. Verifique a existência de lugarse APONT ≠ 0entao se LDISP[APONT] > 0

entao escreva CLIENTE, NVOOsenao escreva NVOO, “LOTADO”

fim seFim se

Fim RefRef. Atualize o número de lugares disponiveisLDISP[APONT] ← LDISP[APONT] -1

Fim Ref.

22

Refinamentos sucessivos do Exemplo 4

Ref. Declare as variaveisdeclare VOOS, {numero dos voos}

LDISP[1:37] {lugares disponiveis} numéricodeclare APONT, CLIENTE, I, NVOO numerico

Fim Ref.

23

Algoritmodeclare VOOS, {numero dos voos} LDISP[1:37] {lugares disponiveis}declare APONT, CLIENTE, I, NVOO numericoleia VOOS[1]...VOOS[37],LDISP[1]...LDISP[37]repitaleia CLIENTE, NVOOse CLIENTE = 9999entao interrompafim seI ← 0repita I ← I + 1 se I = 37 ou VOOS[I] = NVOOentao interrompa fim sefim repitase VOOS[I] = NVOO entao APONT ← I senao escreva “VOO INEXISTENTE” APONT ← 0fim sese APONT ≠ 0 entao se LDISP[APONT] > 0 entao escreva CLIENTE, NVOO LDISP[APONT] ← LDISP[APONT] -1 senao escreva NVOO, “LOTADO” fim se Fim seFim Repita

Fim Algoritmo