Algoritmos e Estruturas de Dados I – Modularização. Profa . Mercedes Gonzales Márquez. Modularização. - PowerPoint PPT Presentation
Citation preview
PowerPoint Presentation1
Modularização
Sempre é possível dividir problemas grandes e complicados em
problemas menores e de solução mais simples. A decomposição de um
problema é fator determinante para a redução da sua
complexidade.
Um algoritmo que envolve um problema grande pode ser dividido em um
algoritmo principal e em diversos subalgoritmos ou módulos, tantos
quantos forem necessários ou convenientes.
2
Modularização
O algoritmo principal é aquele por onde começa a execução, e chama,
eventualmente, os demais subalgoritmos.
Subalgoritmo é um algoritmo que, geralmente, resolve um pequeno
problema, e que está subordinado a um outro algoritmo que
solicitará seu acionamento. É possível que um subalgoritmo chame
outro subalgoritmo.
3
Se alguma parte ainda permanecer complexa, sub-dividi-la
mais.
Analisar o resultado para garantir entendimento e coerência.
4
Dividir problemas grandes em vários problemas menores, de baixa
complexidade.
Número pequeno de variáveis
Poucos caminhos de controle (caminhos do início ao fim)
Utilizar soluções gerais para classes de problemas ao invés de
soluções específicas para problemas particulares.
Reusabilidade
5
Variáveis locais.
Evita a repetição, dentro de um mesmo algoritmo, de uma sequência
de ações em diferentes pontos.
6
Variáveis globais e locais
Todo módulo é constituído por um sequência de comandos que operam
sobre um conjunto de variáveis que podem ser globais ou
locais.
Variáveis globais : Podem ser usadas em módulos internos a outro
módulo do algoritmo onde foram declaradas.
Variáveis locais: Só podem ser usadas no módulo do algoritmo onde
foram declaradas. Elas não possuem significado fora deste
módulo.
7
Variáveis globais e locais
Uma variável local é criada (alocada na memória) no momento em que
o sub-algoritmo que a define é chamado.
Uma variável local é liberada da memória no momento em que o
sub-algoritmo que a define termina.
Uma variável local somente existe (só pode ser utilizada) dentro do
subalgoritmo que a define
8
Caso um mesmo identificador (nome de variável) seja declarado em
sub-algoritmos distintos, esses identificadores são considerados
distintos entre si (variáveis distintas)
O uso de variáveis locais minimiza a ocorrência de “efeitos
colaterais” : o programador pode definir e utilizar as variáveis
que desejar em um sub-algoritmo sem interferir com outros
sub-algoritmos
9
Algoritmo <nome>
Início
Conjunto de ações do algoritmo principal (incluidas as chamadas aos
módulos com seus correspondentes nomes)
Fim
Quando o nome de um módulo é encontrado, ocorre um desvio no
algoritmo principal ou (sub)algoritmo chamador para que os comandos
do módulo sejam executados. Ao término do módulo, a execução
retornará ao ponto subsequente ao da sua chamada.
10
Parâmetros
Parâmetros são canais pelos quais se estabelece uma comunicação
bidirecional entre um subalgoritmo e o algoritmo chamador
(algoritmo principal ou outro subalgoritmo).
Os dados são passados pelo algoritmo chamador através de argumentos
ou também chamados parâmetros reais, e são recepcionados por meio
de parâmetros formais.
11
Parâmetros
Parâmetros Formais: São os nomes simbólicos introduzidos no
cabeçalho dos subalgoritmos, usados na definição dos parâmetros do
mesmo. Dentro de um subalgoritmo trabalha-se com estes nomes da
mesma forma como se trabalha com variáveis locais ou globais.
Parâmetros Reais (ou argumentos):São aqueles que substituem os
parâmetros formais quando da chamada do subalgoritmo.
12
Por valor
O argumento ou parâmetro real é avaliado, gerando um valor que é
copiado para a variável declarada no módulo (parâmetro
formal)
Qualquer alteração do parâmetro formal não é "transmitida" para a
variável do argumento.
O argumento da chamada (parâmetro real) pode ser uma constante, uma
variável ou uma expressão:
5, v1, v1+5-v2
Por referência
- O argumento ou parâmetro real tem que ser uma variável: v1, v2
...
- A variável do argumento (parâmetro real) é associada com a
variável declarada no subalgoritmo (parâmetro formal) durante a
execução do subalgoritmo.
- Qualquer alteração da variável do subalgoritmo (parâmetro formal)
acontece também na variável do argumento.
- Usaremos a seguinte convenção: o símbolo & indicará a
passagem por referência no argumento e * no parâmetro formal.
15
17
Procedimentos
Procedimento:
Um conjunto de ações que não irá devolver valores ao (sub)algoritmo
chamador.
Forma geral de um procedimento (sintaxe):
Procedimento <nome>(<parâmetros formais>)
Início
Nome_procedimento(argumentos)
18
Procedimentos
Algoritmo <nome_algoritmo>
Inicio
Procedimentos – Exemplos simples
Exemplo 1: Faça um algoritmo que dado um valor real global x, chame
um procedimento que calcula o quadrado de x.
Algoritmo <Quad>
real: x
Procedimento Quadrado()
real: z
Fim
Início
Quadrado()
Fim
20
Procedimentos
Exemplo 2 (muito simples com finalidade de explicar a diferença
entre variáveis locais e globais) : Faça um algoritmo que use um
procedimento para ler o nome de uma pessoa e outro para
mudá-lo.
Algoritmo <EscreveNome>
literal: nome
Procedimento le_nome()
leia (nome)
Fim
21
Procedimentos
Exemplo 3 (muito simples com finalidade de explicar a diferença
entre variáveis locais e globais) : Faça um algoritmo que use um
procedimento para ler o nome de uma pessoa e outro para mudá-lo
(use nome como var local)
Algoritmo <EscreveNome>
literal: nome
Procedimento le_nome()
leia (nome)
Fim
22
Procedimentos
No exemplo 3, a variável global nome e a variável local nome
representam posições de memória totalmente diferentes, logo,
qualquer mudança no conteúdo da variável local, não afetará o
conteúdo da variável global.
23
Funções
Função
Um conjunto de ações cujo objetivo é retornar ao ponto de sua
chamada um valor, o qual será associado ao próprio nome que
identifica a função. Por isso, as funções podem ser utilizadas em
expressões como se fossem variáveis.
O conceito de funções é originário da ideia de função matemática,
onde um valor é calculado a partir de outro(s) valor(es)
fornecido(s) à função.
O comando retorne explicita qual é o valor a retornar.
24
Funções
Função tipo <nome>(<parâmetros-formais>)
Início
Comandos
Fim
onde,
lista-de-parâmetros-formais é a lista das variáveis (com seus
tipos) que recepcionam as variáveis fornecidas quando da chamada da
função
25
Funções
nome(lista-de-parâmetros-reais) onde,
lista-de-parâmetros-reais é a lista das variáveis que se
corresponderão com os parâmetros formais durante a execução da
função.
Os parâmetros reais devem concordar em números, ordem e tipo com os
parâmetros formais.
Exemplo:
26
Funções
INSTRUÇÃO Retorne
Comando usado apenas nas funções que tem o efeito de parar a
execução da função e enviar um valor para o algoritmo chamador. No
corpo de instruções da função deve haver, pelo menos, uma instrução
Retorne.
Sintaxe:
27
Funções
Exemplo 1: Faça um algoritmo que dado um valor real x, chame uma
função que retorne o quadrado de x.
Algoritmo <Quad>
Fim
28
Funções
Ex.2 - Faça uma função para determinar se um número inteiro é par
ou não. Utilize esta função para calcular o total de números pares
dentre um total de n números inteiros positivos.
Algoritmo <Pares_Impares>
inteiro: n,i,x,somapar
Leia ( x )
Fim
29
Funções
Ex.3 - Faça uma função que verifique se um valor é perfeito ou não.
Um valor é dito perfeito quando ele é igual a soma dos seus
divisores excetuando ele próprio (Ex. 6´é perfeito, 6=1+2+3, que
são seu divisores). A função deve retornar um valor booleano.
Função logico perfeito (inteiro: num)
inteiro:soma,i
Início
se (mod(num,i)=0)
soma←soma+i
retorne(1)
senão
retorne(0)
Fim
30
Funções
Ex.4 - Faça uma função que recebe a idade de uma pessoa em anos,
meses e dias e retorna essa idade expressa em dias. Assume que os
meses tem 30 dias.
Função inteiro idadedias(inteiro:anos, meses,dias)
retorne(diast)
Fim
31
Funções
Ex.5 - Faça uma função para calcular o máximo divisor comum (MDC)
de dois números dados como parâmetros. Sabe-se que o MDC tem as
seguintes propriedades :
MDC(x,y)=MDC(x-y,y), se x>y
MDC(x,y)=MDC(y,x)
MDC(x,x)=x
MDC(3,1)=MDC(2,1)=MDC(1,1)=1
32
Funções
Inicio
retorne(x)
fim
33
Funções
Ex.6 –Fazer uma função que transforme horas, minutos e segundos em
segundos. Ex. 2 hr 40 min 10 seg -> 9610 segundos.
Fazer um algoritmo que:
Leia um conjunto de dados de empregado contendo, o número de um
empregado, a hora de início (horas, minutos e segundos) e hora de
término de uma determinada tarefa. A entrada de dados finalizará
quando o número do empregado for negativo;
Calcule, para cada empregado, a duração da tarefa que ele executou,
num mesmo dia, utilizando o módulo anteriormente definido;
Escreva, para cada empregado, o seu número e a duração de sua
tarefa em horas, minutos e segundos.
34
Funções
Ex.7 - Escrever uma função que receba dois números inteiros
positivos, e determine o produto dos mesmos, utilizando o seguinte
método de multiplicação.
Dividir, sucessivamente , o primeiro número por 2, até que se
obtenha 1 como quociente;
Paralelamente, dobrar, sucessivamente, o segundo número;
Somar os números da segunda coluna que tenham um número ímpar na
primeira coluna. O total obtido é o produto procurado.
Exemplo:
Fim
36
Funções
Ex.8 - Faça um algoritmo que leia n pontos no plano e determine se
os pontos estão dentro, fora ou sobre uma circunferência de raio R
e centro em (h,k).
37
Funções e Procedimentos
Ex.9 - Foi realizada uma pesquisa de algumas características
físicas de 50 habitantes de uma certa região. De cada habitante
foram coletados os seguintes dados: sexo, cor dos olhos (azuis,
verdes ou castanhos), cor dos cabelos (louros, pretos ou castanhos)
e idade. Faça um procedimento que leia esses dados em um vetor de
registro. O vetor de registro deve ser enviado por
referência.
Procedimento leia (habitante:*dados[50])
inteiro: i
leia(dados[i].idade)
Nota: No algoritmo principal deve ser definido o tipo
habitante.
38
Funções e Procedimentos
Faça um procedimento que receba o vetor de registro definido no
exercício anterior, por referëncia, e retorne também por
referëncia: a maior idade entre os habitantes e a quantidade de
individuos do sexo feminino cuja idade está entre 18 e 35
(inclusive) e que tenham olhos verdes e cabelos louros.
Procedimento informacoes(habitante:&dados[50],
inteiro:&maioridade,&soma)
inteiro: i
se (dados[i].idade>maioridade)
maioridade ← dados[i].idade
se (dados[i].sexo=“F” e dados[i].idade>=18 e
dados[i].idade<=35 e dados[i].cor_olhos=“verdes” e
dados[i].cor_cab=“louros”)
Funções e Procedimentos
Ex.10. Determinar os números inteiros, menores que 50.000.000 que
são capícuas. Capícuas são números que têm o mesmo valor se lidos
da esquerda para a direita ou da direita para a esquerda. Exemplo:
44, 232, 1661, etc.
Deverão ser escritos os seguintes algoritmos:
Um módulo principal
Uma função que calcule quantos algarismos tem um determinado número
inteiro
Uma procedimento para separar um número em n algarismos
Uma procedimento para formar o número na ordem inversa
40
Funções e Procedimentos
Ex.11. Fazer uma função que, dado um número inteiro N, retorne a
soma dos divisores deste número, exceto ele próprio. Fazer um
algoritmo que, utilizando a função anterior, determine e escreva
todos os pares de números amigos em um intervalo ´[A,B]. Os valores
de A e B (A<B), inteiros maiores que zero , deverão ser
lidos.
Dois números inteiros M e N são amigos se a soma dos divisores de
M, excluindo M, é igual a N e a soma dos divisores de N, excluindo
N, é igual a M.
Antes de se elaborar um algoritmo para este problema, algumas
observações se fazem necessárias:
Se um número inteiro X possui um divisor Y menor que sua raiz
quadrada, o quociente da divisão de X por Y será maior que a raiz
quadrada de X e será, também, um divisor de X. Exemplo: X=64 Y=4,
X/Y=16>sqr(64) e é, também, divisor de 64.
Se o número inteiro X possuir raiz quadrada exata, ela será
naturalmente um divisor de X.
41
Funções
si ← soma_div(i)
escreva (i,si)
fim se
fim se
Funções e Procedimentos
Ex.12. Segundo a conjectura de Goldbach, qualquer número par, maior
que 2, pode ser escrito como a soma de dois números primos. Ex.
8=3+5, 16=11+5, 68=31+37, etc.
Dado um conjunto de números inteiros positivos pares, fazer um
algoritmo que calcule, para cada número, um par de números primos
cuja soma seja igual ao próprio número. Adotar como flag um número
negativo. Para verificar se um número é primo, fazer uma função que
deverá retornar em uma variável lógica o valor verdadeiro, se o
número for primo, e falso, em caso contrário.
44
Funções
se (primo(i) e primo (par-i)) então
escreva (i, par-i)
Funções e Procedimentos
Ex.13.Escreva um algoritmo que leia as medidas dos tres lados a, b
e c de um paralelepípedo, calcule e escreva o valor da sua
diagonal.
L=sqr(a2+b2)
D=sqr(L2+c2)
retorne(hip)
fim
Início
Funções e Procedimentos
Ex.14.Escreva um algoritmo que leia uma sequência de 100 números e
os armazene em um vetor. Depois deve ser lida uma subsequência de 5
números. Desenvolva um módulo para verificar se a subsequência
aparece completa e na mesma ordem em algum ponto do vetor, caso
ocorra informar a primeira posição do vetor onde a subsequência
ocorre.
Exemplo:
Sequência de 100 números
5 5 7 4 6 1 0 2 5 7 4 8 9 1 3 5 7 9 1 2 2 4 5 7 6 7 8 9 …
Subsequência
Resposta: Subsequência ocorre a partir da posição 9
49
Inteiro: i,j
j ←1
Enquanto (j<=4 & V[i+j]=S[j+1]) faça
j←j+1
pos ←i
Retorne (1) /*se os elementos de S forem diferentes faça i←i+j para
buscar outra subsequencia*/
Fim se
Fim se
Fim para