Upload
others
View
4
Download
0
Embed Size (px)
Citation preview
Metodos de Programacao 1
Metodos de Programacao 1
Marta Pascoal
Departamento de Matematica, Universidade de Coimbra
Ano lectivo 2010/11
Metodos de Programacao 1
Funcionamento da disciplina
Horario
◮ Teorico-praticas, Marta Pascoal: 3a feira (8.30-10.00) e 5a feira(8.30-10.00), sala Gomes Teixeira
◮ Praticas:P1, Marta Pascoal: 2a feira (14.30-16.00), sala 3.4 ou 0.2, e 5a feira(10.00-11.30), sala 2.2 ou 0.2P2, Marta Pascoal: 2a feira (16.00-17.30), sala 3.4 ou 0.2, e 5a feira(11.30-13.00), sala 2.2 ou 0.2P3, Giuseppe Romanazzi: 2a feira (14.30-16.00), sala 2.2 ou 0.4, e5a feira (10.00-11.30), sala 3.1 ou 0.4P4, Giuseppe Romanazzi: 2a feira (16.00-17.30), sala 2.2 ou 0.4, e5a feira (16.30-18.00), sala 3.1 ou 0.2
◮ Atendimento:2a feira (17.30-18.30) e 3a feira (10.00-11.00), Gab. 4.4, DM3a (16.00-17.00), Sala E.6.1, DEEC
Metodos de Programacao 1
Funcionamento da disciplina
Bibliografia
Base:
◮ Introducao a Programacao usando o Pascal, J. Pavao Martins,McGraw-Hill, Lisboa, 1994
◮ Introduction to Computer Science - an Algorithmic Approach, J.Tremblay, J. DeDourek, R. Bunt, Pascal Edition, McGraw-Hill, 1989
Complementar:
◮ Introduction to Pascal, J. Welsh, J. Elder, MPrentice-Hall Inc, 1982
◮ Introducao a programacao em Pascal, W. Findlay, D. A. Watt, Ed.CETOP, Mem Martins, 1981
◮ How to solve it by computer, R. G. Dromey, Prentice-Hall, 1982
◮ Programacao Sistematica em Pascal, N. Wirth, Campus, 1987
◮ Algorithms + Data structures = Programs, N. Wirth, Prentice-Hall,1976 (ou Algoritmos e Estruturas de Dados, 1986)
Metodos de Programacao 1
Funcionamento da disciplina
Avaliacao
◮ Avaliacao por exame: nota final dada exclusivamente pelo resultadodo exame.Exame de epoca normal: 17 de Junho de 2011 as 14.30Exame de epoca de recurso: 5 de Julho de 2011 as 14.30
◮ Avaliacao contınua (pelo menos 75% de presencas nas aulasteorico-praticas, 75% de presencas nas aulas praticas e nao perturbaro regular funcionamento das aulas):
4NF + NT
5
onde NF = (NF1 + NF2)/2 e a media das notas em duasfrequencias, e NT e a media das notas de trabalhos resolvidos nasaulas praticas (0 ≤ NF , NT ≤ 20).Em cada componente deve haver um mınimo de 7 valores (em 20).Frequencias: 7 de Abril de 2011 e de 31 Maio de 2011
◮ Prova complementar para obter classificacao superior a 17.
Metodos de Programacao 1
Programa
◮ Nocoes Gerais◮ Estrutura e funcionamento basicos dum computador digital◮ Representacao de informacao◮ Metodologia da Programacao
◮ Conceitos Fundamentais de Programacao Imperativa◮ Introducao a linguagem Pascal◮ Tipos elementares, declaracao de variaveis e definicao de constantes◮ Expressoes aritmeticas e logicas◮ Instrucoes◮ Estruturas de controlo◮ Instrucoes de seleccao◮ Instrucoes de repeticao◮ Tabelas
◮ Metodologia da Programacao◮ Subprogramas◮ Recursividade
◮ Registos e conjuntos
Metodos de Programacao 1
Nocoes Gerais
Introducao
Introducao
◮ Computador
O que faz calculos (pessoa ou maquina).
Aparelho electronico usado para processar, guardar e tornaracessıvel informacao de variados tipos.
(in “Priberam Informatica – Lıngua PortuguesaOn-Line”, acedido em 2011-01-25)
Ferramenta que nos permite executar tarefas de forma maiseficiente, rapida e precisa do que manualmente.
Metodos de Programacao 1
Nocoes Gerais
Introducao
Introducao
◮ Programacao
Planificacao, projecto e execucao de uma tarefa.
◮ Programacao de computador
Processo de planificar uma sequencia de instrucoes paraum computador seguir.
Metodos de Programacao 1
Nocoes Gerais
Introducao
Introducao
Fase de resolucao de um problema:
◮ Analisar, compreender e definir o problema.
◮ Descrever uma solucao geral, isto e, uma sequencia de passos quepossam ser usados para resolver o problema (algoritmo).
◮ Seguir os passos indicados e verificar se o metodo encontrado resolverealmente o problema.
Metodos de Programacao 1
Nocoes Gerais
Introducao
Introducao
Fase de implementacao:
◮ Traduzir o algoritmo num codigo (linguagem de programacao).
◮ Garantir que o computador segue as instrucoes e verificar acorreccao das respostas dadas.
◮ Utilizacao do programa.
Algoritmo:
Sequencia de passos para resolver um problema em tempofinito.
Linguagem de programacao (Pascal):
Conjunto de regras, sımbolos e palavras especiais, utilizadaspara construir um programa, com base num algoritmo,suficientemente “simples” para poderem ser entendidas por umcomputador.
Metodos de Programacao 1
Nocoes Gerais
Introducao
Introducao
Documentacao:
A escrita do texto do programa deve ser cuidada eacompanhada de comentarios que o tornem mais facil decompreender e modificar por outros.
Manutencao:
A modificacao dum programa, mesmo depois de concluıdo, porforma a incluir outras melhorias ou a corrigir erros.
Metodos de Programacao 1
Nocoes Gerais
Exemplos
Exemplos
1. program exemplo1(output);
begin
writeln(’ola’);
end.
2. program exemplo2(input, output);
var x, y: integer;
begin
readln(x);
readln(y);
writeln(x+y);
end.
Metodos de Programacao 1
Nocoes Gerais
Exemplos
Exemplos
3. program exemplo3(input, output);
var x, y: integer;
begin
writeln(’x?’);
readln(x);
writeln(’y?’);
readln(y);
writeln(x, ’+’, y, ’=’, x+y);
end.
Metodos de Programacao 1
Nocoes Gerais
Exemplos
Exemplos
4. program exemplo4(input, output);
var x, y: integer;
begin
writeln(’x?’);
readln(x);
if x < 0
then y := -x
else y := x;
writeln(’O valor absoluto de ’, x, ’e’, y);
end.
Metodos de Programacao 1
Nocoes Gerais
Exemplos
Exemplos
5. program exemplo5(input, output);
var i, n: integer;
aux: real;
begin
aux := 0;
writeln(’n?’);
readln(n);
for i:=1 to n do
aux := aux + 1/sqr(i);
writeln(’Resultado: ’, aux);
end.
Metodos de Programacao 1
Nocoes Gerais
Estrutura e funcionamento basicos dum computador digital
Modelo de Von-Neumann
Unidade central de processamento
Dispositivo de Unidade aritmetica e logica Dispositivo deentrada Unidade de controlo saıda
Memoria central
Neste modelo um computador digital tem 3 unidades principais:
◮ Unidade Central de Processamento (CPU): executa operacoes arit-meticas e logicas elementares estipuladas pelo programa e se efectuacontrolo do sistema. Divide-se em:
◮ a unidade aritmetica e logica e◮ a unidade de controlo.
◮ Unidades de Entrada e Saıda (Input/Output): permitem comunica-cao com o exterior.
◮ Memoria Central: armazena programas, dados e resultados.
Metodos de Programacao 1
Nocoes Gerais
Estrutura e funcionamento basicos dum computador digital
Modelo de Von-Neumann
◮ Periferico: Dispositivo de entrada, saıda ou armazenamento auxiliarde um computador.
◮ Hardware: Componentes fısicas de um computador ⇒ Fixo
◮ Software: Conjunto de programas disponıveis num computador ⇒Manipulavel
Linguagens de programacao: em computadores digitais os dados saoarmazenados, e operados, em codigo binario, de 0’s e 1’s.
◮ de baixo nıvel:◮ Linguagem maquina: composta de instrucoes codificadas em binario.◮ Linguagem assembler : usa mnemonicas para representar instrucoes
de linguagem maquina para um computador particular.
◮ de alto nıvel:◮ Fortran, Pascal, C,. . . : Mais proximas dos conceitos humanos e
independentes do processador.
Metodos de Programacao 1
Nocoes Gerais
Representacao de informacao
Representacao digital
◮ Informacao analogica: de variacao contınua
◮ Informacao digital: de variacao discretaInformacao digital binaria: baseada em binary information digit’s(bit’s) com dois estados 0/1.
◮ Memoria: sequencia de celulas que permitem o armazenamento deuma palavra.
◮ Palavra: no de bits que formam uma unidade manipulavel por umcomputador.
A memoria dum computador e definida pelo numero de palavras queconsegue armazenar. Assim, temos:
23 bits = 1 byte 220 bytes = 1024 Kb = 1 M210 bytes = 1 Kb 230 bytes = 1024 M = 1 G
Metodos de Programacao 1
Nocoes Gerais
Representacao de informacao
Representacao de inteiros
Dado um natural n existem k ∈ IN e bi ∈ {0, 1}, i = 1, . . . , k , tais que
n =
k∑
i=0
bi2i
Exemplos:710 = 1× 22 + 1× 21 + 1× 20 72 = 000001111610 = 1× 24 + 0× 23 + 0× 22 + 0× 21 + 0× 20 162 = 00010000
◮ Para representar o sinal de um inteiro pode usar-se o 1o bit.
◮ A representacao e as operacoes sao exactas.
◮ Se a capacidade e ultrapassada ocorre um erro de overflow.
Metodos de Programacao 1
Nocoes Gerais
Representacao de informacao
Representacao de reais
Em representacao vırgula flutuante um real x e escrito como
m × Be , com − E < e < E e −M < m < M
onde:
m e a mantissaB e a basee e o expoente
Sinal expoente mantissa
1 bit 8 bits 23 bits
Exemplos (com B = 10):
23.48 = 0.2348× 102
−0.02348 = −0.2348× 10−1
◮ A gama de variacao e finita e a variacao nao e contınua.
◮ A representacao e as operacoes nao sao exactas.
Metodos de Programacao 1
Nocoes Gerais
Representacao de informacao
Representacao de caracteres
Tabela ASCII (American Standard Code for Information Interchange):
cada caracter e representado por um codigo de 7 bits.00 16 32 48 64 80 96 112
0 NUL DLE 0 @ P ‘ p
1 SOH DC1 ! 1 A Q a q
2 STX DC2 " 2 B R b r
3 ETX DC3 # 3 C S c s
4 EOT DC4 $ 4 D T d t
5 ENQ NAK % 5 E U e u
6 ACK SYN & 6 F V f v
7 BEL ETB ’ 7 G W g w
8 BS CAN ( 8 H X h x
9 HT EM ) 9 I Y i y
10 LF SUB * : J Z j z
11 VT ESC + ; K [ k {
12 FF FS , < L \ l |
13 CR GS - = M ] m }
14 SO RS . > N ^ n ~
15 SI US / ? O _ o DEL
Metodos de Programacao 1
Nocoes Gerais
Metodologia da Programacao
Construcao de um programa
Fase de compilacao:
Programa fonte −→ Compilador
Erros de com-pilacao
Programa objecto
Fase de execucao:
Dados −→Execucao doprograma
Erros de execucao
Resultados
Metodos de Programacao 1
Nocoes Gerais
Metodologia da Programacao
Metodologia da programacao
◮ Correccao: O programa deve ser:
simples,estruturado na abordagem (modular e descendente) doproblema ecumprir o objectivo a que se destina (ou seja, ser“formalmente correcto”).
◮ Clareza: O programa deve reflectir a estrutura do algoritmo, por:
separacao em blocos funcionais,uso adequado das estruturas da linguagem,escolha cuidada de identificadores edocumentacao interna.
◮ Eficiencia: O programa deve ser:
rapido (tempo de execucao) eutilizar pouco espaco de memoria.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Introducao a linguagem Pascal
Introducao a linguagem Pascal
Linguagem de programacao:
conjunto de regras, sımbolos e palavras especiais usadas paraconstruir um programa.
◮ Sintaxe: regras formais que definem a construcao de expressoesvalidas numa linguagem.
Diagramas de sintaxe de Pascal na pagina WOC.
Um programa e sintacticamente correcto se e so se corresponde aum caminho ao longo dos diagramas de sintaxe.
◮ Semantica: conjunto de regras que dao o significado de umaexpressao da linguagem (forma de interpretar as expressoes dalinguagem por forma a lhes dar um significado preciso).
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Introducao a linguagem Pascal
Introducao a linguagem Pascal
◮ Problema: Calcular a temperatura media num dia.
◮ Dados: Temperaturas mınima e maxima nesse dia.
◮ Resultados: Temperatura media nesse dia (ponto medio).
Programa em Pascal:
{ Programa que calcula a temperatura me’dia de um dia }
program TempMedia(input, output);
var tmin, tmax, tmedia: integer;
begin
writeln(’Temperatura mi’’nima?’);
readln(tmin);
writeln(’Temperatura ma’’xima?’);
readln(tmax);
tmedia := (tmin + tmax) div 2;
writeln(’A temperatura me’’dia foi ’, tmedia);
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Introducao a linguagem Pascal
Introducao a linguagem Pascal
Comentario:
{ Programa que calcula a temperatura me’dia de um dia }
Parte declarativa:
program TempMedia(input, output);
var tmin, tmax, tmedia: integer;
Parte operativa (modulo principal):
begin
writeln(’Temperatura mi’’nima?’);
readln(tmin);
writeln(’Temperatura ma’’xima?’);
readln(tmax);
tmedia := (tmin + tmax) div 2;
writeln(’A temperatura me’’dia foi ’, tmedia);
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Introducao a linguagem Pascal
Introducao a linguagem PascalIdentificadores:
Sequencias de letras e dıgitos, iniciadas por uma letra, usadaspara denominar qualquer entidade de um programa.
Identificadores reservados (palavras reservadas):
abs ln reset arctan eoln char sqrt write
ord new boolean rewrite cos odd text readln
get chr output integer sqr round pack input
eof sin dispose maxint pred true succ false
exp put unpack writeln read trunc page
Exemplos: umaletra x1 num3ros
◮ Sımbolos especiais nao podem ser utilizados como identificadores.
◮ Usando palavras reservadas o novo significado sobrepoe-se ao antigo.
◮ Alguns compiladores analisam apenas os caracteres iniciais de umidentificador.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Introducao a linguagem Pascal
Introducao a linguagem Pascal
Tipos de dados:
Conjunto de valores + Conjunto de operacoes
Tipos
Escalares
Pre-definidos
integer
real
char
boolean
Definidos pelo utilizador
Estruturados
array
record
set
file
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Inteiros (integer)
◮ Operadores aritmeticos com operandos e resultados inteiros:Operador Exemplo Operacao
+ 5 + 3 = 8 adicao- 2 - 9 = -7 subtraccao (simetrico)* 33 * 11 = 363 multiplicacao
div 21 div 4 = 5 quociente da divisao inteiramod 21 mod 4 = 1 resto da divisao inteira
◮ Funcoes standard com argumento e resultado inteiros:Funcao Exemplos Resultado
abs abs(-6) = 6 valor absolutosqr sqr(-3) = 9 quadradosucc succ(7) = 8, succ(-7) = -6 sucessorpred pred(10) = 9 predecessor
◮ Constante pre-definida: MAXINT, maximo inteiro
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Inteiros (integer)
◮ Funcoes com argumento inteiro e resultado real:Funcao Exemplo Resultado
sqrt sqrt(3)=1.732050808 raiz quadrada
◮ Operadores relacionais:Operador Exemplo Operacao
= sqr(5) = 25 igualdade<> 2 <> 9 desigualdade< 45 < 1098 menor do que> 17 >- 3 maior do que
>= 2 >= 2 maior do que ou igual a<= -6 <= 7 menor do que ou igual a
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Reais (real)
Representacao interna nao exacta, donde operacoes sobre estes valorespodem introduzir imprecisoes.
◮ Operadores aritmeticos:Operador Exemplo Operacao
+ 5.5+3=8.5, 5.5+3.0=8.5 adicao- 2.2-9=-6.1 subtraccao (simetrico)* 33*0.5=11.5 multiplicacao/ 2.5/2=1.25, 5/4=1.25 divisao real
◮ Funcoes com resultado real se o argumento for real:Funcao Exemplo Resultado
abs abs(-6.5)=6.5, abs(-5)=5 valor absolutosqr sqr(3.1)=9.61 potencia
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Reais (real)
◮ Funcoes de transferencia (com argumento real e resultado inteiro):Funcao Exemplo Resultadotrunc trunc(-3.7)=-3, trunc(3.7)=3 truncaturaround round(-3.7)=-4, round(3.7)=4 arredondamento
round(3.2)=3, round(-3.2)=-3
◮ Funcoes com resultado real:Funcao Exemplo Resultado
cos cos(3)=0.98999, cos(3.1415)=1.0 cossenosin sin(3)=0.14112, sin(3.1415)=0.0 seno
arctan arctan(-1)=3.11415 arco de tangentesqrt sqrt(4)=2.0, sqrt(9.0)=3.0 raiz quadradaexp exp(1)=2.71828 exponencialln ln(2.71828)=1.0, ln(1)=0.0 logaritmo nepperiano
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Reais (real)
◮ Operadores relacionais:Operador Exemplo Operacao
= ????? igualdade<> desigualdade< menor do que> maior do que
>= maior do que ou igual a<= menor do que ou igual a
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Caracteres (char)
O conjunto dos caracteres inclui:
0 1 2...9 ... A B C...Y Z ... a b c...y z ... + - * ( )
onde:
◮ cada subconjunto esta ordenado;
◮ cada caracter tem uma representacao interna - no natural;
◮ qualquer caracter e representado entre plicas:’A’ 6= A ’+’ 6= + ’5’ 6= 5
variavel operador numeral
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Caracteres (char)
◮ Funcoes de transferencia:Funcao Exemplo Operacao
chr chr(65) = ’A’ caracterord ord(’A’) = 65 no interno correspondente
◮ Funcoes com argumento e resultado char:Funcao Exemplo Operacaosucc succ(’R’) = ’S’ chr(ord(char)+1)pred pred(’b’) = ’a’, pred(’A’) = ?? chr(ord(char)−1)
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Logicos (boolean)
◮ Operadores logicos: Seguem tabelas de verdade e regras respectivas.
Operador Operacaoand conjuncao (∧)or disjuncao (∨)not negacao (¬)
p q p and q p or q not p
V V V V FV F F V FF V F V VF F F F V
Exemplos:
1. x ∈]0, 1] ou x > 0 ∧ x ≤ 1, escreve-se: (x > 0) and (x <= 1)
2. (n > 1) and (n < 0) e falso3. not (5 < 2) = true e verdadeiro
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Logicos (boolean)
◮ Funcoes com argumento e resultado logicos:Funcao Exemplo Operacaopred pred(true)=false predecessorsucc succ(false)=true sucessor
◮ Funcao com argumento inteiro e resultado logico:Funcao Exemplo Operacao
odd odd(5)=true, odd(2)=false ımpar
◮ Funcao com argumento logico e resultado inteiro:Funcao Exemplo Operacao
ord ord(true)=1, ord(false)=0 no interno
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos pre-definidos: Exemploprogram calculadora(input, output);
var operador: char;
x, y, resultado: real;
begin
{ Ler dados }
write(’x, y?’);
read(x, y);
write(’operador?’);
read(operador);
{ Efectuar calculo }
case operador of
’+’: resultado := x + y;
’-’: resultado := x - y;
’*’: resultado := x * y;
’/’: resultado := x / y
end;
{ Escrever resultado }
write(x, operador, y, ’=’, resultado)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos definidos pelo utilizador: Definicao por enumeracao
Definicao de tipo:
−→ type −→ identificador −→ = −→ tipo simples −→ ; −→
;
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
..
.
Definicao de tipo por enumeracao:
−→ ( −→ identificador −→ ) −→
,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos definidos pelo utilizador: Definicao por enumeracao
Exemplos:
type naipe= (ouros, copas, paus, espadas);
premios= (primeiro, segundo, terceiro);
dias= (segunda, terca, quarta, quinta, sexta,
sabado, domingo);
var trunfo: naipe;
lugar: premios;
d: dias;
E NAO type premios= (1o, 2o, 3o);!!!
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos definidos pelo utilizador: Definicao por enumeracao
Sao validos:
◮ operadores relacionais: segunda < quinta
◮ funcoes pred, succ e ord:pred(quarta) = terca, succ(terca) = quarta, ord(terca) = 1,
uma vez queord(segunda)=0, ord(terca)=1, ord(quarta)=2, . . .
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Tipos definidos pelo utilizador: Definicao por subdomınio
Se as variaveis tomam apenas alguns valores dum domınio definido esuficiente definir um novo tipo indicando o primeiro e o ultimo valores.
−→ constante .. constante −→
Exemplos:
◮ type NaoNegativo= 0 .. MAXINT;
dias= (segunda, terca, quarta, quinta, sexta,
sabado, domingo);
DiasUteis= segunda .. sexta;
var n: NaoNegativo;
dia: DiasUteis;
Herdam-se operacoes e funcoes do domınio inicial.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Declaracao de dados: Variaveis
−→ var −→ identificador −→ : −→ tipo −→ ; −→
,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..............................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
◮ Obrigatoria a declaracao de variaveis antes dum bloco de instrucoessobre elas.
◮ Permite a reserva antecipada das celulas de memoria que podem vira ser usadas, o que depende do numero e do tipo das variaveis.
Exemplos:
var x, y: real;
n: integer;
d: DiasUteis;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Declaracao de dados: Constantes
Literal: valor constante utilizado num programa.
Exemplo:dobro := 2 * x;
−→ const −→ identificador −→ = −→ constante −→ ; −→.......................................
.
.
.
.
.
.
.
.
.
.
.
.
.
..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
◮ Definicao dos valores constantes a utilizar no programa.
◮ Tipo definido automaticamente atraves do valor da constante.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tipos elementares, declaracao de variaveis e definicao de constantes
Declaracao de dados: Constantes
Exemplos:
const pi = 3.1415926;
titulo = ’Alice no Pais das Maravilhas’;
delta = 0.5E-06;
iva = 0.20;
◮ Nomes mais sugestivos do que os valores.
◮ Mais simples alterar o valor de uma constante do que modificartodas as ocorrencias de um valor no programa.
◮ O valor da constante nao pode ser alterado ao longo do programa.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Expressoes aritmeticas e logicas
Expressoes aritmeticas e logicasExpressoes aritmeticas em Pascal:
◮ Contem variaveis, constantes e operadores.
◮ A ordem pela qual as operacoes sao efectuadas e definida pelaprioridade dos operadores envolvidos.
Prioridades (semelhantes as usadas para expressoes matematicas):
Operadores Prioridadenot 4*, /, div, mod, and 3+, -, or 2=, <>, >, >=, <, <= 1
Tal como na avaliacao de expressoes matematicas:
◮ avaliacao feita por ordem nao crescente de prioridade dos operadores,
◮ com operadores de igual prioridade, avaliacoes feitas da esquerdapara a direita.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Expressoes aritmeticas e logicas
Expressoes aritmeticas e logicasExemplos:
◮ 10 div 2 * 3 = 5 * 3 = 15
◮ 5 * 2 / 4 * 2 = 10 / 4 * 2 = 2.5 * 2 = 5.0
◮ (3 > 0) and not (3 < 10) = true and not true = true
and false = false
A utilizacao de parentesis altera estas regras:
◮ 10 div (2 * 3) = 10 div 6 = 1
◮ 5 * 2 / (4 * 2) = 5 * 2 / 8 = 10 / 8 = 1.25
Notas:
◮ As variaveis de uma expressao ja devem ter um valor.
◮ Dois operadores nao podem aparecer seguidos.
◮ O operador de multiplicacao ‘*’ nao pode ser omitido.
◮ Em caso de duvida usar parentesis.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
InstrucoesInstrucao de atribuicao:
Instrucao que atribui o valor de uma expressao a uma variavel.
→ variavel → := → expressao →
Variavel e expressao (que devolve valor) tem que ter o mesmo tipo(excepto na atribuicao de um valor inteiro a uma variavel real).
Exemplos:
var i: integer;
x: real;
teste: boolean;
letra: char;
...
i := 3;
letra := chr(i);
teste := True;
x := x + i + 10;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
Instrucoes
Instrucao de atribuicao:
◮ Troca dos valores de duas variaveis (do mesmo tipo):
var i, j, aux: integer;
Considerando i = 2 e j = 5,
aux := i;
i := j;
j := aux;
produz i = 5 e j = 2.
◮ Incrementar o valor de uma variavel:Considerando i = 1,
i := i + 1;
produz i = 2.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
Instrucoes
Instrucao de sequenciacao:
Especifica a ordem de execucao das instrucoes executando-assequencialmente.
◮ ‘;’ delimita o fim duma instrucao e serve de separador de instrucoes.
◮ Um grupo de instrucoes, isto e, um bloco de instrucoes, e delimitadopelas palavras reservadas begin e end.
→ begin → instrucao → end → ; →
;
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
............................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
Instrucoes
Instrucoes de entrada/saıda:
Para recolha de dados e escrita de resultados.
→ program → identificador → ( → identificador→ ) → ; →
,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Em geral sao utilizados:
◮ input: que representa o teclado;
◮ output: que representa o ecra.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
Instrucoes: Leitura
→ read → ( −−−−−−− → lista variaveis →) →
readln........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..................................................................
..............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
canal → ,........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..................................................................
..............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
◮ Os valores obtidos atraves do canal de entrada sao atribuıdos, porordem, as variaveis na instrucao de leitura.
◮ As variaveis a ler e os valores dados tem que ser do mesmo tipo.
Exemplos:
◮ read(i,j) ou read(input,i,j): leitura do teclado,
◮ read(dados1,i,j): leitura do ficheiro dados1.
◮ readln(i,j) ou readln(input,i,j), readln(dados1,i,j): omesmo mas mudando a linha apos a leitura.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
Instrucoes: Leitura
Podem ler-se valores:
◮ Numericos: ignorando espacos em branco e mudancas de linha.
◮ Caracteres: um de cada vez.
Exemplo:
var x: real;
c1, c2, c3: char;
n: integer;
Dada a sequencia 6.5 a123 a instrucao read(x,c1,c2,c3,n); produz:
x = 6.5, c1 = ’ ’, c2 = ’a’, c3 = ’1’, n = 23
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
Instrucoes: Escrita
→ write → ( −−−−−−− → lista de saıda →) →
writeln........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..................................................................
..............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
canal → ,........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..................................................................
..............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Exemplos:
◮ write(i,j) ou write(output,i,j): escrita no ecra,
◮ write(res1,i,j): escrita no ficheiro res1.
◮ writeln(i,j) ou writeln(output,i,j), writeln(res1,i,j): omesmo mas mudando a linha apos a escrita.
◮ Dados x = 5.0, c1 = ’g’, n = 3, teste = True, temos:Instrucoes Saıdawrite(n), write(3) 3
write(n+2*x), write(13.0) +1.300000E+01
write(c1), write(’g’) g
write(’Uma string’) Uma string
write(teste), write(2 > 1) True
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
Instrucoes: Escrita
Especificadores de formatoEspecificam o modo como aparece a informacao:
express~ao : comprimento do campo : parte decimal
onde,
◮ express~ao: informacao a ser escrita,
◮ comprimento do campo: campo minımo para escrever sımbolos(alargado automaticamente se insuficiente),
◮ parte decimal: numero de casas decimais, para reais.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes
Instrucoes: Escrita
Especificadores de formatoExemplos:
◮ Dados x = -9.0, n = 3,Instrucoes Saıdawrite(x:6:2) -9.00
write(x:3:2) -9.00
write(n:3) 3
◮ Instrucao: write(’Inteiro ’:2, n:3, ’ e real ’:10, x:4)
Saıda: Inteiro 3 e real -9.0
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Estruturas de controlo
Estruturas de controlo
Estruturas de controlo
Instrucoes especiais em Pascal para controlar o fluxo dumasequencia de instrucoes, alterando a ordem sequencial explıcita.
Estruturas de Base
Sequencia
Seleccao
{Alternativa
Multipla
Repeticao
Enquanto
Ate que
Com contador
Subprograma
{Procedimento
Funcao
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: if-then-else
Seleccao alternativa
Escolha de instrucoes a executar consoante o valor de umaexpressao logica.Se a expressao e verdadeira, e executada a instrucaocorrespondente a then, senao e executada a instrucaocorrespondente a else.Nao existindo else passa-se a instrucao seguinte.
−→ if −→expressao
logica−→ then −→ instrucao −→ else −→ instrucao −→
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...............................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: if-then-else
Exemplos:
◮ Executar a divisao entre dois inteiros.
writeln(’x, y? ’);
readln(x,y);
res := x div y;
writeln(x, ’ / ’, y, ’ = ’, res);
◮ Executar a divisao entre dois inteiros, se o divisor for nao nulo.
writeln(’x, y? ’);
readln(x,y);
if y <> 0
then
begin
res := x / y;
writeln(x, ’ / ’, y, ’ = ’, res)
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: if-then-else
Exemplos:
◮ Executar a divisao entre dois inteiros, se o divisor for nao nulo, senaoimprimir mensagem de erro.
writeln(’x, y? ’);
readln(x,y);
if y <> 0
then
begin
res := x / y;
writeln(x, ’ / ’, y, ’ = ’, res)
end
else writeln(’Erro! O divisor e’’ nulo.’);
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: if-then-else
Problema:Dados 3 inteiros positivos, verificar se podem ser o comprimento doslados dum triangulo. Se assim for classificar o triangulo.
◮ Tres inteiros positivos sao lados de um triangulo se cada um e menordo que a soma dos restantes dois.
◮ Um triangulo e:◮ equilatero se os lados sao todos iguais;◮ isosceles se apenas dois lados sao guais;◮ escaleno se os lados sao todos diferentes.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: if-then-else
Exemplos:
◮ program triangulo (input, output);
var a, b, c: 1 .. MAXINT;
begin
writeln(’a, b, c?’);
readln(a, b, c);
if (a < b + c) and (b < a + c) and (c < a + b)
then if (a = b) or (a = c) or (b = c)
then if (a = b) and (b = c)
then writeln(’Triangulo Equilatero’)
else writeln(’Triangulo Isosceles’)
else writeln(’Triangulo Escaleno’)
else writeln(’Nao formam um triangulo’);
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: case
Seleccao multipla
Escolha de instrucoes a executar consoante o valor de umaconstante que pode ter mais do que 2 valores.
→ case → expressao → of → constante → : → instrucao → end →
,
;
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.....................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Exemplo:
case i of
1 : instrucao1;
2 : instrucao2;
3, 4 : instrucao3
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: case
◮ Expressao tem de ser de um dos tipos enumeraveis (nao real).
◮ Expressao e constantes tem de ser do mesmo tipo.
◮ Se uma constante aparece em mais do que uma instrucao surge umerro de compilacao.
◮ Em Pascal standard se expressao nao tem o valor de uma dasconstantes surge um erro de execucao.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: case
Exemplo:Fazer corresponder uma mensagem a uma classificacao A, B, C, D ou F.
case nota of
’A’, ’B’: writeln(’Bom trabalho!’);
’C’ : writeln(’Trabalho normal.’);
’D’, ’F’: writeln(’Mau trabalho...’)
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de seleccao
Instrucoes de seleccao: case
Instrucoes equivalentes:
◮ if (nota = ’A’) or (nota = ’B’) or (nota = ’C’) or
(nota = ’D’) or (nota = ’F’)
then case nota of
’A’, ’B’: writeln(’Bom trabalho!’);
’C’ : writeln(’Trabalho normal.’);
’D’, ’F’: writeln(’Mau trabalho...’)
end
else writeln(’A nota dada nao e valida’);
◮ if (nota = ’A’) or (nota = ’B’)
then writeln(’Bom trabalho!’)
else if (nota = ’C’)
then writeln(’Trabalho normal.’)
else if (nota = ’D’) or (nota = ’F’)
then writeln(’Mau trabalho!’)
else writeln(’A nota dada nao e valida’);
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: while-do
Repeticao: Ciclos
Repete uma instrucao simples ou composta, enquanto aexpressao logica e verdadeira.
−→ while −→expressao
logica−→ do −→ instrucao −→
◮ O ciclo divide-se em:◮ cabeca: teste logico, efectuado antes de tudo,◮ corpo: instrucao executada se o teste e verdadeiro.
◮ Cada execucao do corpo dum ciclo chama-se uma iteracao do ciclo.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: while-do
Repeticao: Ciclos
◮ Se expressao e falsa, entao o ciclo nunca e efectuado.
◮ Se expressao e sempre verdadeira, entao o ciclo nunca para: ciclo
infinito.
Tipos classicos de ciclos:
◮ Ciclo controlado por um contador: ciclo que e executado um numeroconhecido de vezes.
◮ Ciclo controlado por um sucesso: ciclo que termina quando algo noseu corpo indica que se deve sair.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: while-do
Problema: Escrever as primeiras 10 potencias de 2.
1. program potencias1(output);
const lim = 10;
var i: integer;
begin
i := 1; { Inicializacao }
while i <= lim do { Ciclo }
begin
writeln(’2^’, i,’ = ’, exp(i * ln(2)));
i := i + 1; { Incremento }
end
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: while-do
Problema: Escrever as primeiras 10 potencias de 2.
2. program potencias2(output);
const lim = 10;
var i, potencia: integer;
begin
i := 1; { Inicializacao }
potencia := 2;
while i <= lim do { Ciclo }
begin
writeln(’2^’, i,’ = ’, potencia);
i := i + 1; { Incremento }
potencia := potencia * 2
end
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: while-do
Problema: Escrever as potencias de 2 inferiores a 1000.
3. program potencias3(output);
const lim = 1000;
var i, potencia: integer;
begin
i := 1; { Inicializacao }
potencia := 2;
while potencia < lim do { Ciclo }
begin
writeln(’2^’, i,’ = ’, potencia);
i := i + 1; { Incremento }
potencia := potencia * 2
end
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: repeat-until
Repeticao: Ciclos
Repete uma instrucao simples ou composta, ate que aexpressao logica seja verdadeira.
−→ repeat −→ instrucao −→ until −→expressao
logica−→
“Traducao” de um ciclo repeat-until em while-do:
repeat
Instruc~oes
until cond. paragem;
aux := true;
while aux do
begin Instruc~oes;
aux := cond. paragem
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: repeat-until
Diferencas entre repeat-until e while-do:
◮ No repeat repete-se uma instrucao elementar (ou composta) ate quea expressao logica se torne verdadeira:
◮ O teste logico do repeat (a cabeca do ciclo) e efectuado no final,logo o ciclo e executado pelo menos uma vez.
Situacoes em que e vantajoso utilizar repeat-until em vez dewhile-do:
◮ Por vezes a condicao de paragem so fica definida apos a primeirapassagem do ciclo.
◮ Nestes casos usar while-do obriga a uma inicializacao artificial.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: repeat-until
Exemplo: Ler uma classificacao com valores A, B, C, D ou F.
writeln(’De uma nota:’);
readln(nota);
while (nota <> ’A’) and (nota <> ’B’) and (nota <> ’C’) and
(nota <> ’D’) and (nota <> ’F’) do
begin
writeln(’A nota dada nao e valida!’);
writeln(’A nota inserida deve ser A, B, C, D ou F.’);
writeln(’De uma nota:’);
readln(nota)
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: repeat-until
Exemplo: Ler uma classificacao com valores A, B, C, D ou F.
repeat
writeln(’De uma nota:’);
readln(nota);
if (nota <> ’A’) and (nota <> ’B’) and (nota <> ’C’) and
(nota <> ’D’) and (nota <> ’F’)
then
begin
writeln(’A nota dada nao e valida!’);
writeln(’A nota inserida deve ser A, B, C, D ou F.’)
end
until (nota = ’A’) or (nota = ’B’) or (nota = ’C’) or
(nota = ’D’) or (nota = ’F’);
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: for-to-do
Repeticao: Ciclos
O ciclo e repetido um numero fixo de vezes.
−→ for −→ indentificador de variavel −→ := −→ expressao
todownto
−→ expressao −→ do −→ instrucao −→
....................................... ............. ................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
........................................
..............
Esta estrutura usa um contador do numero de repeticoes com duasvariantes:
◮ incremento de 1 unidade (to);
◮ decremento de 1 unidade (downto).
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: for-to-do
Problema: Escrever as primeiras 10 potencias de 2.
1. program potencias4(output);
const lim = 10;
var i, potencia: integer;
begin
potencia := 2;
for i := 1 to lim do
begin
writeln(’2^’i,’ = ’, potencia);
potencia := potencia * 2
end
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: for-to-do
Notas:
◮ O identificador de variavel (contador) e as expressoes tem que ser domesmo tipo: literais nao reais.
◮ Nao se pode alterar o valor do contador dentro do ciclo (emboraesse valor possa ser utilizado).
◮ No final do ciclo o contador pode nao estar definido.
◮ Num ciclo for-to-do, se o valor final e inferior ao inicial, entaonada e executado.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: for-to-do
Problema: Imprimir no ecra o triangulo de caracteres:
A
AB
ABC
ABCD
ABCDE
ABCDEF
program ImprimeLetras(output);
var letraFinal, letraActual: char;
begin
for letraFinal := ’A’ to ’F’ do
begin
for letraActual := ’A’ to letraFinal do
write(letraActual);
writeln
end
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: Exemplos
Dada a temperatura em cada hora de um dia determinar as temperaturasmınima e maxima desse dia.
1. Iniciar o processo (temperaturas mınima e maxima) e condicao deparagem do ciclo (horas).
2. Enquanto horas ≤ numhoras Fazer
2.1 Actualizar dados.Obter nova temperatura.Comparar temperatura com a mınima ate ao momento.Comparar temperatura com a maxima ate ao momento.
2.2 Actualizar condicao de paragem do ciclo.
3. Escrever resultados.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: Exemplos
program Temperatura1(input, output);
const numhoras = 24;
var temp, min, max, hora: integer;
begin
min := MAXINT;
max := -MAXINT;
for hora := 1 to numhoras do
begin
read(temp);
if temp < min
then min := temp;
if temp > max
then max := temp
end;
writeln(’A temperatura minima neste dia foi: ’, min);
writeln(’A temperatura maxima neste dia foi: ’, max)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: Exemplos
{ Cabecalho }
program Temperatura2(input, output);
{ Parte declarativa }
const numhoras = 24;
var temp, imin, min, imax, max, hora: integer;
{ Bloco principal }
begin
{ Inicializacoes }
imin := 0;
min := MAXINT;
imax := 0;
max := -MAXINT;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: Exemplos
{ Ciclo}
for hora := 1 to numhoras do
begin
read(temp);
if temp < min then
begin
imin := hora;
min := temp
end;
if temp > max then
begin
imax := hora;
max := temp
end
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Instrucoes de repeticao: Exemplos
{ Escrita de resultados }
writeln(’Minima: ’, min, ’ atingida as ’, imin, ’ h.’);
writeln(’Maxima: ’, max, ’ atingida as ’, imax, ’ h.’)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
1. Escrever n ∈ IN em “notacao binaria”.
2. Aproximar a raiz de 2− ex − sin x = 0 em [a, b], pelo metodo dabisseccao:
2.1 aplicando o metodo k vezes,2.2 aplicando o metodo ate obter um intervalo de amplitude inferior a δ.
3. Aproximar∫ b
af (x) dx , com f (x) = ex − sin x , usando a regra dos
trapezios e n subintervalos:
∫ b
a
f (x) dx ≈h
2(f (x0) + 2f (x1) + · · ·+ 2f (xn − 1) + f (xn)) ,
onde h = b−an
, x0 = a, xi = xi−1 + h.
4. Calcular kp com k , p ∈ IN.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
Escrever n ∈ IN em “notacao binaria”.
program binario(input, output);
var n: 0..maxint;
begin
writeln(’De n:’);
readln(n);
write(’Em base 2: ’);
while n > 0 do
begin
write(n mod 2);
n := n div 2
end
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
Aproximar a raiz de 2− ex − sin x = 0 em [a, b], pelo metodo dabisseccao. Aplicar o metodo, no maximo, k vezes.
1. Ler a, b, k
2. i ← 0, continua ← verdade
3. Enquanto i ≤ k e continua fazer
3.1 Incrementar i
3.2 m← a+b
2
3.3 Se f (a)f (m) < 0 entao b ← m
Senao Se f (m)f (b) < 0 entao a← m
Senao continua ← falso
4. Escrever m e f (m)
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
program bisseccao(input, output);
var i, k: integer;
a, b, m, fa, fb, fm: real;
continua: boolean;
begin
writeln(’De a e b:’);
readln(a, b);
writeln(’De o numero de iteracoes:’);
readln(k);
i := 0;
fa := 2 - sin(a) - exp(a);
fb := 2 - sin(b) - exp(b);
continua := (fa * fb) < 0;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
while (i < k) and continua do
begin i := i + 1;
m := (a + b) / 2;
fm := 2 - sin(m) - exp(m);
if (fa * fm) < 0 then
begin b := m;
fb := fm;
end
else if (fm * fb) < 0 then
begin a := m;
fa := fm;
end
else continua := false
end;
writeln(’f(’, m, ’)=’, fm, ’ apos ’, i,’ iteracoes.’)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
Aproximar a raiz de 2− ex − sin x = 0 em [a, b], pelo metodo dabisseccao. Aplicar o metodo ate obter um intervalo de amplitude inferiora δ.
program bisseccao2(input, output);
var a, b, m, fa, fb, fm, delta, erro: real;
begin
writeln(’De a e b:’);
readln(a, b);
writeln(’De a tolerancia delta:’);
readln(delta);
fa := 2 - sin(a) - exp(a);
fb := 2 - sin(b) - exp(b);
erro := b - a;
continua := (fa * fb) < 0;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
while (abs(erro) >= delta) and continua do
begin m := (a + b) / 2;
fm := 2 - sin(m) - exp(m);
if (fa * fm) < 0 then
begin b := m;
fb := fm;
end
else if (fm * fb) < 0 then
begin a := m;
fa := fm;
end
else continua := false;
erro := b - a
end;
writeln(’f(’,m,’)=’,fm,’ com erro menor que ’,erro,’.’)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
Aproximar∫ b
af (x) dx , com f (x) = ex − sin x , usando a regra dos
trapezios e n subintervalos:
∫ b
a
f (x) dx ≈h
2(f (x0) + 2f (x1) + · · ·+ 2f (xn − 1) + f (xn)) ,
onde h = b−an
, x0 = a, xi = xi−1 + h.
1. Ler a, b, n
2. Calcular amplitude de intervalos h = b−an
3. x0 ← a, soma← 0
4. Para k desde 1 ate n − 1 fazer
4.1 xk ← xk + h
4.2 soma ← soma +f (xk)
5. integral ← h2(f (a) + 2× soma + f (b))
6. Escrever integral
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
program trapezios(input, output);
var k, n: integer;
a, b, h, xk, fxk, soma, integral: real;
begin
writeln(’De a e b: ’);
readln(a, b);
writeln(’De o numero de sub-intervalos: ’);
readln(n);
h := (b-a) / n;
xk := a;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
soma := 0;
for k := 1 to n-1 do
begin
xk := xk + h;
fxk := exp(xk) - sin(xk);
soma := soma + fxk
end;
integral := h*(exp(a)-sin(a)+2*soma+exp(b)-sin(b))/2;
writeln(’Int(f)= ’, integral)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
Calcular kp com k , p ∈ IN.
program potencias(input, output);
var k, p, m, n, kaux, prod: integer;
begin
writeln(’De k e p: ’);
readln(k, p);
prod := 1;
m := p;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplos
prod := 1;
m := p;
while m <> 0 do
begin kaux := k;
n := 1;
while 2*n <= m do
begin kaux := sqr(kaux);
n := n * 2;
end;
prod := prod * kaux;
m := m - n
end;
writeln(k,’^’,p,’=’, prod)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplo
Calcular o valor da funcao seno num ponto dado, atraves do desenvolvi-mento em serie, desprezando termos de valor absoluto inferior a 10−8.
sin x =
+∞∑
k=0
(−1)kx2k+1
(2k + 1)!= x −
x3
3!+
x5
5!−
x7
7!+ · · ·
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Exemplo
program FSeno(input, output);
const epsilon = 1E-8;
var k: integer;
x, termo, seno: real;
begin write(’Indique x: ’);
readln(x);
k := 1;
termo := x;
seno := 0;
while abs(termo) >= epsilon do
begin seno := seno + termo;
k := k + 2;
termo := - termo * sqr(x) / ((k-1) * k)
end;
writeln(’sen(’, x, ’)= ’, seno)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
Leitura de dados
1. Quantidade de valores a ler conhecida a priori.
2. Quantidade de valores a ler desconhecida:
2.1 Utilizacao de uma sentinela para assinalar o final da sequencia.2.2 Leitura a partir de um ficheiro e utilizacao das funcoes eof e eoln:
◮ eof(f) e True se e so se e detectado o final do ficheiro f.◮ eoln(f) e True se e so se e detectado o final de uma linha no
ficheiro f.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Instrucoes de repeticao
ExemploContar o numero de caracteres de um ficheiro.
program ContaCaracteres(f, output);
var c: char;
conta: integer;
f: text;
begin assign(f, ’dados.txt’);
reset(f);
conta := 0;
while not eof(f) do
if eoln(f) then readln(f)
else
begin read(f, c);
conta := conta + 1
end;
close(f);
writeln(’O ficheiro tem ’, conta,’ caracteres.’)
end.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas
Tabela:
Agregado de elementos do mesmo tipo, cada um pode seracedido atraves da indicacao da posicao que ocupa na tabela.
−→ array −→ [ −→ tipo simples −→ ] −→ of −→ tipo −→
,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..............................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
..
.
.
Permitem:
◮ denotar um grupo de variaveis por um unico identificador,
◮ aceder a cada componente por indicacao de um ındice.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Declaracao
Uma tabela e caracterizada:
◮ pela dimensao (ou limites dos seus ındices) e
◮ pelo tipo dos seus elementos.
Diferentes tipos:
◮ unidimensionais (com um so ındice): array [1..20] of integer;
◮ bidimensionais (com 2 ındices): array [1..20, 1..20] of real;
(ou: array [1..20] of array [1..20] of real];)
◮ . . .
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Declaracao
Exemplos:
const m = 10;
n = 20;
type vector = array [1 .. 20] of integer;
matriz = array [1 .. m, 1 .. n ] of real;
palavra = array [0 .. 15] of char;
var x, y: vector;
A: matriz;
p: palavra;
notas: array [’A’ .. ’F’] of integer;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Acesso
Sao armazenadas varias posicoes de memoria que podem ser acedidas porindicacao da posicao, do mesmo modo que qualquer variavel:
x[3] := 5;
i := 1;
j := 10;
A[i,j] := 2 / x[3];
p[1] := ’C’;
notas[p[1]] := 0;
y := x; { Nao valido em Pascal standard }
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Algumas operacoes com vectoresDados:
type vector = array [1 .. 100] of integer;
var x: vector;
dimx, i: integer;
◮ Leitura:
writeln(’De o tamanho do vector:’);
readln(dimx);
writeln(’De as ’, dimx, ’ componentes do vector:’);
for i := 1 to dimx do
read(x[i]);
◮ Escrita:
write(’Vector: ’);
for i := 1 to dimx do
write(x[i], ’ ’);
writeln;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Algumas operacoes com vectores
var x, y, z: vector;
dim, i, soma: integer;
◮ Produto interno:
soma := 0;
for i := 1 to dim do
soma := soma + x[i] * y[i];
◮ Adicao:
for i := 1 to dim do
z[i] := x[i] + y[i];
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Algumas operacoes com matrizes
Dados:
type matriz = array [1 .. 100, 1 .. 100] of integer;
var A: matriz;
m, n, i, j: integer;
◮ Leitura:
writeln(’De o numero de linhas:’);
readln(m);
writeln(’De o numero de colunas:’);
readln(n);
writeln(’De as ’, m*n, ’ componentes da matriz:’);
for i := 1 to m do
for j := 1 to n do
read(A[i,j]);
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Algumas operacoes com matrizes
◮ Escrita:
writeln(’Matriz:’);
for i := 1 to m do
begin
for j := 1 to n do
write(A[i,j]:4, ’ ’);
writeln
end
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Algumas operacoes com matrizes
var A: matriz;
m, n, i, j, soma, SomaMax, IndMax: integer;
◮ Encontrar o ındice da linha com soma maxima:
SomaMax := 0;
IndMax := 1;
for j := 1 to n do
SomaMax := SomaMax + A[1,j];
for i := 2 to m do
begin soma := 0;
for j := 1 to n do
soma := soma + A[i,j];
if soma > SomaMax then
begin SomaMax := soma;
IndMax := i
end
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Tabelas: Algumas operacoes com matrizes
var A, B, S, P: matriz;
m, n, k, i, j, l: integer;
◮ Adicao:
for i := 1 to m do
for j := 1 to n do S[i,j] := A[i,j] + B[i,j];
◮ Produto: Dadas Am×n, Bn×k , A×B e uma matriz Pm×k de elemento
pij =
n∑
r=1
airbrj
for i := 1 to m do
for j := 1 to k do
begin
P[i,j] := 0;
for l := 1 to n do P[i,j] := P[i,j] + A[i,l]*B[l,j]
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Exemplos
1. Capicua?
2. Representacao em base binaria
3. Medias da turma
4. Factorizacao de um inteiro em factores primos
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Exemplos
3. Considere os 20 nomes de uma turma e as respectivas notas a 5disciplinas dados na forma:
Ana Rita Fonseca . 10 15 11 9 14Anıbal Silva . 16 14 13 11 10
Elabore um programa que imprima nome e media de cada aluno docurso.
4. Todo o inteiro positivo pode ser decomposto como produto depotencias de numeros primos. Por exemplo:
2268 = 22 × 34 × 71
Elabore um programa que escreva a representacao canonica de uminteiro positivo dado.
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Mais operacoes com vectores
var x: vector;
i, j, aux, n, meio: integer;
◮ Troca de dois elementos do vector
aux := x[i];
x[i] := x[j];
x[j] := aux;
◮ Inversao de todos os elementos do vectorTrocar elementos desde as posicoes extremas do vector ate asposicoes centrais.
meio := n div 2;
for i := 1 to meio do
begin
aux := x[i];
x[i] := x[n-i+1];
x[n-i+1] := aux
end;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Mais operacoes com vectores
var x: vector;
aux, i, n: integer;
◮ Permutacao a esquerdaOs elementos do vector rodam uma posicao para a esquerda.O primeiro passa para a ultima posicao.
aux := x[1];
for i := 1 to n-1 do
x[i] := x[i+1];
x[n] := aux;
◮ Remocao do elemento na posicao k ∈ {1, . . . , n}Rodar os elementos das posicoes de k a n uma posicao a esquerda.Actualizar a dimensao utilizada.
for i := k to n-1 do
x[i] := x[i+1];
n := n-1;
Metodos de Programacao 1
Conceitos Fundamentais de Programacao Imperativa
Tabelas
Mais operacoes com vectores
var x: vector;
i, k, elm, n: integer;
◮ Insercao de um novo elemento na posicao k ∈ {1, . . . , n} (e n + 1inferior a dimensao maxima)Rodar os elementos das posicoes de n ate k uma posicao a direita.Inserir o novo valor.Actualizar a dimensao utilizada.
for i := n downto k do
x[i+1] := x[i];
x[k] := elm;
n := n + 1;
Metodos de Programacao 1
Metodologia da Programacao
Metodologia da Programacao
Programacao estruturada descendente caracterizada por:
◮ Resolucao do problema de forma global
◮ Refinar os varios passos distintos do programa
Surge a necessidade de dividir o programa em “blocos” (ou modulos)correspondentes aos subproblemas identificados.
Subprogramas:
Grupos de instrucoes tratados como um todo e identificadospor um nome.
◮ Funcoes
◮ Procedimentos
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
Funcao:
Subprograma que fornece um valor.
Exemplos de funcoes pre-definidas em Pascal:
1. sqrt: Integer / Real → Real
2. ord: Char → Integer
3. odd: Integer → Boolean
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
Funcao:f : X → Y
x 7→ f (x)
Do mesmo modo, para definir uma funcao em Pascal e necessarioidentificar:
1. domınio (tipo de variaveis),
2. contra-domınio (tipo do resultado),
3. expressao designatoria.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
→ function → identificador→ ( → argumentos → ) → : → tipo ;
bloco → ;
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
..
.................................................................................................................................................................................................................................................................................... ..............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
....................................... ............. ................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
........................................
..............
Bloco contem:
◮ as declaracoes das entidades usadas pela funcao,
◮ as instrucoes usadas pela funcao (corpo da funcao).
◮ Tipo deve ser um tipo simples.
◮ Tem de haver pelo menos uma instrucao de atribuicao do valor dafuncao.
◮ Esse valor nao pode voltar a ser usado depois de uma chamada dafuncao no programa principal.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
Exemplos:
1. function f(x: real): real;
begin f := exp(x) - sin(x)
end;
2. function distancia(x1, y1, x2, y2: real): real;
begin distancia := sqrt(sqr(x1 - x2) + sqr(y1 - y2))
end;
3. function positivo1(n: integer): boolean;
begin if n > 0
then positivo1 := true
else positivo1 := false
end;
4. function positivo2(n: integer): boolean;
begin positivo2 := (n > 0)
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
Chamada da funcao analoga a das funcoes pre-definidas:
1. valor := f(pi)+2.5; (const pi = 3.1415;)
2. d := distancia(0,0,1,1);
3. writeln(positivo1(2 * a)); (var a: integer; . . . a := 5;)
4. teste2 := positivo2(-2);
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program trapezios1(input, output);
var k, n: integer;
a, b, h, xk, soma: real;
function f(x: real): real;
begin f := exp(x) - sin(x);
end;
begin writeln(’De a, b e o numero de sub-intervalos: ’);
readln(a, b, n);
h := (b-a) / n;
xk := a;
soma := 0;
for k := 1 to n-1 do
begin xk := xk + h;
soma := soma + f(xk)
end;
writeln(’Int(f)= ’, h*(f(a)+2*soma+f(b))/2)
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas
A declaracao de um subprograma deve ser feita na parte declarativa doprograma e constituıda por:
◮ cabecalho e
◮ bloco de instrucoes, que se divide ainda:◮ numa parte declarativa, onde se definem entidades (constantes,
tipos, variaveis, subprogramas) a usar, e◮ numa parte operativa, que contem o conjunto de instrucoes a
executar.
Um subprograma:
◮ e uma instrucao valida dentro do programa onde e declarado.
◮ e invocado atraves do seu identificador.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Domınios de identificadores
Para limitar o domınio de accao de um identificador podemos ter:
◮ Identificadores locais: reconhecidos apenas no subprograma em queestao declarados.
◮ Identificadores globais: reconhecidos nos subprogramas do blocoonde sao definidos.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Domınios de identificadores
Exemplo:
program A;
var x, y: real; { x, y variaveis globais }
function B(...): real;
var i: integer; { i variavel local }
begin ...
end;
function C(...): integer;
var k, i: integer; { k, i variaveis locais }
begin ...
end;
begin ...
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Domınios de identificadores
Declaracao local:
◮ torna claro que variaveis locais so tem significado dentro dosubprograma em que sao declaradas (programa mais legıvel),
◮ a utilizacao de variaveis locais fora dos subprogramas em que saodeclaradas provoca erro de compilacao,
◮ facilita a minimizacao do espaco de memoria.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Domınios de identificadores
Regras de identificacao do domınio de um identificador:
1. O domınio e o bloco no qual o identificador esta declarado e todosos nele englobados (exceptuando a regra 2).
2. Quando um identificador e redeclarado num bloco B, englobado porum bloco A, a nova declaracao sobrepoe-se as anteriores, masapenas no ambito de B.
3. Os identificadores standard sao considerados declarados num blocoimaginario que engloba todo o programa.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
A modificacao de variaveis globais em funcoes pode causar efeitoslaterais: chamada da funcao altera o valor de variaveis externas.
Exemplo:
function f(x: integer): real;
begin a := a * x; { a variavel global }
f := sqrt(x) + a
end;
Dependencia da ordem pela qual se efectuam os calculos. Para a = 1,
f(9) + a = 12 + 9 = 21 e a + f(9) = 1 + 12 = 13f(9) + a 6= a + f(9)!!!
E conveniente nao modificar o valor de variaveis nao locais.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
Exemplo: Escrever um programa que dado um inteiro positivo verifiquese este e capicua.
program capicua (input, output);
type intpositivo = 0 .. maxint;
var n: intpositivo;
function inverso(num: intpositivo): intpositivo;
var inv: intpositivo;
d: 0 .. 9;
begin inv := 0;
repeat
d := num mod 10;
inv := inv * 10 + d;
num := num div 10
until num = 0;
inverso := inv
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
begin writeln(’De um inteiro positivo:’);
readln(n);
if n = inverso(n)
then writeln(n, ’Capicua’)
else writeln(n, ’Nao capicua’)
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Funcoes (function)
O valor do numero nao e alterado fora da funcao.O identificador da funcao pode aparecer a esquerda de instrucoes deatribuicao no bloco da funcao, o que parece tornar desnecessaria avariavel local inv.No entanto, no seu bloco de definicao, o aparecimento a direita de umainstrucao de atribuicao do identificador da funcao, como,
y := inverso(x);
e uma chamada da funcao a si propria, logoinverso := inverso * 10 + d;
e sintacticamente errado pois inclui uma chamada a inverso semparametros. E necessario usar uma variavel auxiliar.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas: Procedimentos: (procedure)
Procedimento:
Subprograma que corresponde a uma sequencia de accoesespecıfica. Nao devolve um resultado.
→ procedure → identificador → ( → argumentos → ) → ;
bloco → ;
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.................................................................................................................................................................................................................................................................................... ..............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
....................................... ............. ................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
........................................
..............
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program trapezios3(input, output);
var k, n: integer;
a, b, h, xk, soma, IT: real;
procedure LerDados;
begin
writeln(’De a, b: ’);
readln(a, b);
writeln(’De o numero de sub-intervalos: ’);
readln(n)
end;
function f(x: real): real;
begin f := exp(x) - sin(x)
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplosprocedure CalculaIT;
begin h := (b-a) / n;
xk := a;
soma := 0;
for k := 1 to n-1 do
begin xk := xk + h;
soma := soma + f(xk)
end
IT := h*(f(a)+2*soma+f(b))/2)
end;
procedure EscreverRes;
begin writeln(’Int(f)= ’, IT)
end;
begin LerDados;
CalculaIT;
EscreverRes
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program trapezios4(input, output); { Identificadores locais }
var n: integer;
a, b, IT: real;
procedure LerDados;
begin writeln(’De a, b: ’);
readln(a, b);
writeln(’De o numero de sub-intervalos: ’);
readln(n)
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplosprocedure CalculaIT;
var k: integer;
h, xk, soma: real;
function f(x: real): real;
begin f := exp(x) - sin(x)
end;
begin h := (b-a) / n;
xk := a;
soma := 0;
for k := 1 to n-1 do
begin xk := xk + h;
soma := soma + f(xk)
end;
IT := h*(f(a)+2*soma+f(b))/2)
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
procedure EscreverRes;
begin writeln(’Int(f)= ’, integral)
end;
begin LerDados;
CalculaIT;
EscreverRes
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Subprogramas
A utilizacao de subprogramas reduz:
◮ o comprimento total do programa,
◮ as areas de potenciais erros,
◮ o esforco de programacao.
Alem disso:
◮ Subprogramas podem ser chamados varias vezes no mesmoprograma.
◮ Subprogramas podem ser testados individualmente.
◮ Subprogramas podem ser utilizados em novos programas.
◮ Quanto mais complexo o programa, maior a necessidade de divisaoem subprogramas.
◮ Subprogramas aumentam a clareza do programa, tornando maissimples a sua compreensao, modificacao ou extensao.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Parametros
◮ A troca de informacao entre o programa e o subprograma e feitaatraves da lista de parametros.
◮ Usar apenas variaveis globais pode nao ser suficiente.
Exemplo: Rodar os valores de tres variaveis globais reais x, y, z.
procedure rodar;
var aux: real;
begin
aux := x;
x := y;
y := z;
z := aux
end;
O procedimento apenas roda as variaveis x, y e z!
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
ParametrosParametros formais
−→ ( −− −→ identificador −→ : −→ tipo −→ ) −→
var ,
cabecalho de procedimento
cabecalho de funcao
;
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
....................................................................... ............. ........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
................................................................................................................................................................................... ............. .......................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
........................................................................................................................................................................................................................................................................................................................................................................................................................... .............
........................................................................................................................................................................................................................................................................................................................................................................................................................... ............. ............................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.......................................................................................................................................................................................................................................................................................................................................................................................................................................... ............. .............................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
Exemplo:
{ n1, n2, n3 parametros formais }
procedure rodar1(var n1, n2, n3 : real);
var aux : real;
begin aux := n1;
n1 := n2;
n2 := n3;
n3 := aux
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Parametros
Parametros reais
−→ ( −→ expressao −→ ) −→
id. variavel
id. proc.
id. funcao
,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.................................................................................................................................................................... .............
.................................................................................................................................................................... .............
.................................................................................................................................................................... ............. ............................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
............................................................................................................................................................................................. ............. .............................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
Chamada do procedimento:
rodar1(x, y, z); { x, y, z parametros reais ou concretos }
ou
rodar1(p, q, r); { p, q, r parametros reais ou concretos }
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Passagem de parametros por valor e por referencia
Metodo de passagem de parametros:
◮ Passagem por referencia (parametros de classe variavel)
◮ Passagem por valor (parametros de classe valor)
◮ Passagem por argumentos funcionais (parametros de classefuncional)
Regras:
◮ O numero de parametros nas duas listas deve coincidir.
◮ Cada parametro real corresponde a um parametro formal, com aordem na lista.
◮ Parametros reais e formais correspondentes devem ser da mesmaclasse e do mesmo tipo.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Passagem de parametros por referencia
Classe variavel
Da-se ao procedimento uma copia da posicao em memoria doparametro real.Alteracoes a esse parametro mantem-se apos o seu final.
◮ Parametros formais devem ser precedidos da palavra var.
◮ Parametros reais sao necessariamente variaveis.
procedure rodar1(var n1, n2, n3: integer);
Quando um parametro e passado por referencia, e fornecida a sualocalizacao em memoria.O espaco de memoria e partilhado e a modificacao feita ao parametroformal reflecte-se no real. A variavel e a mesma, com um nome diferente.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Passagem de parametros por valor
Classe valor
Da-se ao procedimento uma copia do valor do parametro real.Alteracoes a esse parametro nao se mantem apos o seu final.
Exemplo:
procedure PartesReal(var pInt: integer; var pDec: real;
x: real);
begin pInt := trunc(x);
pDec := x - parteInt
end;
Parametros formais: pInt e pDec de classe variavel, x de classe valor.
◮ Nao e precedido de var.
◮ O parametro real comporta-se no bloco do subprograma como umavariavel local.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program trapezios5(input, output);
var nint: integer;
linf, lsup: real;
procedure LerDados(var a, b: real; var n: integer);
begin writeln(’De os limites de integracao: ’);
readln(a, b);
writeln(’De o numero de sub-intervalos: ’);
readln(n)
end;
function IT(a, b: real; n: integer): real;
begin ...
end;
procedure EscreverRes(res: real);
begin writeln(’Int(f)= ’, res)
end;
begin LerDados(linf, lsup, nint);
EscreverRes(IT(linf, lsup, nint))
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
function IT(a, b: real; n: integer): real;
var k: integer;
h, xk, soma: real;
function amplitude(a, b: real; n: integer): real;
begin amplitude := (b-a) / n
end;
function f(x: real): real;
begin f := exp(x) - sin(x)
end;
begin h := amplitude(a, b, n);
xk := a;
soma := 0;
for k := 1 to n-1 do
begin xk := xk + h;
soma := soma + f(xk)
end;
IT := h*(f(a)+2*soma+f(b))/2)
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
1. Todo o inteiro positivo pode ser decomposto como produto depotencias de numeros primos. Por exemplo:
2268 = 22 × 34 × 71
Elabore um programa que escreva a representacao canonica de uminteiro positivo dado.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program canonico(input,output);
var n: integer;
procedure LeN(var n: integer);
begin write(’De n:’);
readln(n)
end;
procedure CriaImprimeCanonico(n: integer);
var ...
begin ...
end;
begin LeN(n);
CriaImprimeCanonico(n)
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplosprocedure CriaImprimeCanonico(n: integer);
var i, cont: integer;
primeiro: boolean;
begin i := 2;
primeiro := true;
while n > 1 do
begin cont := 0;
while (n mod i = 0) and (n > 1) do
begin n := n div i;
cont := cont + 1
end;
if cont > 0 then
begin if primeiro
then primeiro := false
else write(’ x ’);
write(i:1, ’^’, cont:1)
end;
i := i + 1
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
2. Considere os 20 nomes de uma turma e as respectivas notas a 5disciplinas dados na forma:
Ana Rita Fonseca . 10 15 11 9 14Anıbal Silva . 16 14 13 11 10
Elabore um programa que imprima nome e media de cada aluno docurso.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program Medias(input, output);
var aluno: 1..20;
procedure TrataAluno;
begin ...
end;
procedure TrataNota;
begin ...
end;
begin for aluno := 1 to 20 do
begin TrataAluno;
TrataNota;
readln;
writeln
end
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
procedure TrataAluno;
var compnome: 0 .. 32;
procedure ImprimeNome;
begin ...
end;
procedure Completa;
begin ...
end;
begin ImprimeNome;
Completa
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
procedure ImprimeNome;
var proxcar: char;
begin compnome := 0;
repeat
read(proxcar);
write(proxcar);
compnome := compnome+1;
until proxcar = ’.’
end;
procedure Completa;
begin while compnome < 32 do
begin write(’ ’);
compnome := compnome+1
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
procedure TrataNota;
var nota, media: 0..20;
cadeira: 1..5;
total: 0..100;
begin
total := 0;
for cadeira := 1 to 5 do
begin
read(nota);
total := total+nota
end;
media := round(total/5);
write( media:10)
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
3. Elabore um programa que imprima os primeiros n termos dasucessao associada a serie harmonica:
Hn = 1 +1
2+
1
3+ · · ·+
1
n
Por exemplo, para n = 3, o programa devera imprimir:1
3/2
11/6
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program SerieHarm(input,output);
var n: integer;
procedure SerieHarmonica(n: integer);
begin ...
end;
begin writeln(’De n: ’);
readln(n);
SerieHarmonica(n)
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
procedure SerieHarmonica(n: integer);
var i, auxn, auxd, serien, seried: integer;
procedure soma(an, ad, bn, bd: integer; var num, den: integer);
begin ...
end;
procedure EscreverFraccao(num, den: integer);
begin ...
end;
begin serien := 0;
seried := 1;
for i:=1 to n do
begin
auxn := 1;
auxd := i;
soma(serien, seried, auxn, auxd, serien, seried);
EscreverFraccao(serien, seried)
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
procedure soma(an, ad, bn, bd: integer; var num, den: integer);
procedure simplifica(var num, den: integer);
begin ...
end;
begin
num := an*bd + bn*ad;
den := ad * bd;
simplifica(num, den)
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
procedure simplifica(var num, den: integer);
var divisor: integer;
function mdc(a, b: integer): integer;
begin ...
end;
begin
divisor := mdc(num, den);
if divisor > 1
then
begin
num := num div divisor;
den := den div divisor
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
function mdc(a, b: integer): integer;
var resto: integer;
begin
while b <> 0 do
begin
resto := a mod b;
a := b;
b := resto
end;
mdc := a
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
procedure EscreverFraccao(num, den: integer);
begin
if (num = 0) or (den = 1)
then writeln(num)
else writeln(num,’/’,den)
end;
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
4. Classificar os primeiros 100 inteiros positivos nas seguintescategorias:
◮ Perfeito: se o numero e igual a soma dos seus divisores (porexemplo, o 6).
◮ Abundante: se o numero e inferior a soma dos seus divisores (porexemplo, o 12).
◮ Reduzido: se o numero e superior a soma dos seus divisores (porexemplo, o 9).
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program Classificar(output);
var n, soma: integer;
function SomaDivisores(n: integer): integer;
begin ...
end;
begin for n := 1 to 100 do
begin write(n:5);
soma := SomaDivisores(n);
if soma = n
then writeln(’ e um numero perfeito.’)
else if soma > n
then writeln(’ e um numero abundante.’)
else writeln(’ e um numero reduzido.’)
end
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
function SomaDivisores(n: integer): integer;
var i, soma: integer;
begin
soma := 1;
for i := 2 to n-1 do
if n mod i = 0 then
soma := soma + i;
SomaDivisores := soma
end;
E suficiente testar os divisores ate n div 2!
for i := 2 to n div 2 do
ou entao
lim := n div 2;
for i := 2 to lim do
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
5. Listar os primeiros 100 numeros primos.Um inteiro positivo n e um numero primo se e maior do que 1 e senao tem divisores nao proprios (isto e, se nao tem outros divisoresque nao 1 e n).
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
program ListarPrimos(output);
var n, conta: integer;
function TestePrimo(n: integer): boolean;
begin conta := 0;
n := 2;
writeln(’Lista dos primeiros 100 numeros primos’);
while conta < 100 do
begin if TestePrimo(n)
then
begin writeln(n);
conta := conta + 1
end;
n := n + 1
end
end.
Metodos de Programacao 1
Metodologia da Programacao
Subprogramas
Exemplos
function TestePrimo(n: integer): boolean;
var divisor, lim: integer;
begin
TestePrimo := true;
lim := n-1;
divisor := 2;
while TestePrimo and (divisor <= lim) do
begin
TestePrimo := (n mod divisor) <> 0;
divisor := divisor + 1
end
end;
E suficiente testar os divisores ate trunc(sqrt(n))!
lim := trunc(sqrt(n));
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
De novo operacoes com vectores
◮ Inversao de todos os elementos do vectorTrocar elementos desde as posicoes extremas do vector ate asposicoes centrais.
procedure Inverte(var x: vector; n: integer);
var i, meio: integer;
begin
meio := n div 2;
for i := 1 to meio do
Troca(x, i, n-i+1)
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
De novo operacoes com vectores
◮ Permutacao a esquerdaOs elementos do vector rodam uma posicao para a esquerda.O primeiro passa para a ultima posicao.
procedure RodaEsq(var x: vector; n: integer);
var aux, i: integer;
begin
aux := x[1];
for i := 1 to n-1 do
x[i] := x[i+1];
x[n] := aux
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
De novo operacoes com vectores
◮ Remocao do elemento na posicao k ∈ {1, . . . , n}Rodar os elementos das posicoes de k a n uma posicao a esquerda.Actualizar a dimensao utilizada.
procedure Remove(var x: vector; var n: integer; k: integer);
var i: integer;
begin
for i := k to n-1 do
x[i] := x[i+1];
n := n-1
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
De novo operacoes com vectores
◮ Insercao de um novo elemento na posicao k ∈ {1, . . . , n} (e n + 1inferior a dimensao maxima)Rodar os elementos das posicoes de n ate k uma posicao a direita.Inserir o novo valor.Actualizar a dimensao utilizada.
procedure Insere(var x: vector; var n: integer;
elm, k: integer);
var i: integer;
begin
for i := n downto k do
x[i+1] := x[i];
x[k] := elm;
n := n + 1
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Mais operacoes com vectores
◮ Pesquisa de um elemento no vector
function Procura1(x: vector; n, elm: integer): boolean;
var i: integer;
begin Procura1 := false; { Devolve true sse encontra elm }
for i := 1 to n do
if elm = x[i] then Procura1 := true
end;
function Procura2(x: vector; n, elm: integer): integer;
var i: integer;
begin Procura2 := 0; { Devolve posicao de elm em x }
for i := 1 to n do { ou 0 se nao o encontrou }
if elm = x[i] then Procura2 := i
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Mais operacoes com vectores
◮ Pesquisa de um elemento no vector O ciclo termina assim que forencontrada uma ocorrencia do elemento procurado.
function Procura3(x: vector; n, elm: integer):
integer;
var i: integer;
achou: boolean;
begin
i := 0;
achou := false;
while (i < n) and not achou do
begin
i := i+1;
achou := elm = x[i]
end;
Procura3 := i
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados (ordem crescente)
◮ Pesquisa sequencial de um elemento num vector ordenado por ordemcrescenteO ciclo termina assim que:
◮ for encontrada uma ocorrencia do elemento procurado ou◮ surja um valor maior do que esse.
Por exemplo, dado1 3 10 15 54
o elemento 9 nao pertence ao vector, enquanto que 15 se encontra na 3a
posicao.
No pior caso todas as posicoes do vector, n, sao examinadas.
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados (ordem crescente)
function PesqSeq(x: vector; n, elm: integer): integer;
var i: integer;
achou: boolean;
begin
PesqSeq := 0;
i := 0
achou := false;
while (i < n) and not achou do
begin
i := i+1;
achou := elm <= x[i]
end;
if achou then
if elm = x[i] then
PesqSeq := i
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados: Pesquisa◮ Pesquisa binaria de um elemento num vector por ordem crescente
O elemento e comparado com a posicao media do vector.◮ Se esse valor e igual ao elemento entao o ciclo termina,◮ Se esse valor e maior do que o elemento entao repete-se a pesquisa
na primeira metade do vector,◮ Se esse valor e menor do que o elemento entao repete-se a pesquisa
na segunda metade do vector.
Por exemplo, dado
1 3 10 15 23 24 32 87 99
o elemento 15 e procurado nos seguinte vectores:
1 3 10 15 10 15 15
No pior caso sao examinadas log n posicoes do vector.
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados: Pesquisa
function PesqBin(x: vector; n, elm: integer): integer;
var inicio, meio, fim: integer;
achou: boolean;
begin PesqBin := 0;
inicio := 1;
fim := n;
achou := false;
while (inicio <= fim) and not achou do
begin meio := (inicio+fim) div 2;
if elm = x[meio] then achou := true
else if elm > x[meio] then inicio := meio + 1
else fim := meio - 1
end;
if achou then PesqBin := meio
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados: Insercao
◮ Insercao de um novo elemento num vector por ordem nao-decrescen-te (e n + 1 inferior a dimensao maxima)Procurar posicao do vector com o primeiro valor superior ao novoelemento, k .Inserir novo elemento na posicao k .
Por exemplo, dado o numero 15 e o vector:
1 3 10 23 99
15 sera inserido na posicao 4, obtendo-se
1 3 10 15 23 99
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados: Insercao
function PosInserir(x: vector; n, elm: integer): integer;
var i: integer;
achou: boolean;
begin i := 1;
achou := false;
while (i <= n) and not achou do
if elm < x[i] then achou := true
else i := i+1;
PosInserir := i
end;
procedure InsereOrd(var x: vector; var n: integer; elm: integer);
var pos: integer;
begin pos := PosInserir(x, n, elm);
Insere(x, n, elm, pos)
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados: Insercao
◮ Insercao de um novo elemento num vector por ordem nao-decrescen-te (e n + 1 inferior a dimensao maxima)Inserir o novo elemento na posicao n + 1.Colocar o novo elemento na posicao correcta do vector, fazendotrocas com o valor a esquerda enquanto esse for superior.
Por exemplo, dado o numero 15 e o vector:
1 3 10 23 99
15 sera inserido na posicao 6, e em seguida obtem-se
1 3 10 23 99 15
1 3 10 23 15 99
1 3 10 15 23 99
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados: Insercao
procedure ColocaEmOrdem(var x: vector; n, pos: integer);
var i: integer;
para: boolean;
begin i := pos-1;
para := false;
while (i >= 1) and not para do
if x[i+1] > x[i]
then para := true
else
begin Troca(x, i+1, i);
i := i-1
end
end;
procedure InsereOrd1(var x: vector; var n: integer; elm: integer);
begin Insere(x, n, elm, n+1);
ColocaEmOrdem(x, n, n)
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados: Insercao
◮ Insercao de um novo elemento num vector por ordem nao-decrescen-te (e n + 1 inferior a dimensao maxima)Rodar os valores do vector superiores ao elemento a inserir umaposicao a direita.Inserir o novo elemento na posicao correcta.
Por exemplo, dado o numero 15 e o vector:
1 3 10 23 99
obtem-se1 3 10 23 99 99
1 3 10 23 23 99
1 3 10 15 23 99
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Operacoes com vectores ordenados: Insercao
procedure InsereOrd2(var x: vector; var n: integer; elm: integer);
var i: integer;
para: boolean;
begin i := n;
para := false;
while (i >= 1) and not para do
if elm > x[i] then para := true
else
begin
x[i+1] := x[i];
i := i-1
end;
if para then x[i] := elm
else x[1] := elm;
n := n+1
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Insercao linear◮ Metodos de ordenacao: Insercao linear
O vector tem uma sequencia ordenada e outra nao ordenada.No inıcio a primeira sequencia contem apenas um elemento.O 1o elemento da sequencia nao ordenada e inserido na posicao cor-recta da sequencia ordenada (deslocando os elementos maiores paraa esquerda), e passa da sequencia nao ordenada para a ordenada.Repete-se ate todos os elementos estarem na sequencia ordenada.
Por exemplo, dado: 10 3 15 99 23 temos a sequencia:
10 3 15 99 23
3 10 15 99 23
3 10 15 99 23
3 10 15 99 23
3 10 15 23 99
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Insercao linear (“original”)procedure InsercaoLinear(var x: vector; n: integer);
var novo, k, i, aux: integer;
para: boolean;
begin for novo := 2 to n do
begin
i := 1;
para := false;
while (i < novo) and (not para) do
if x[novo] < x[i] then para := true
else i := i+1;
if para then
begin
aux := x[novo];
for k := novo downto i+1 do
x[k] := x[k-1];
x[i] := aux
end
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Insercao linear (trocar com elementos a
esquerda ate a posicao certa)
procedure InsercaoLinear1(var x: vector; n: integer);
var novo, i: integer;
para: boolean;
begin for novo := 2 to n do
begin
i := novo;
para := false;
while (i > 1) and (not para) do
if x[i] > x[i-1] then para := true
else
begin
Troca(x, i-1, i);
i := i-1
end
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Insercao linear (rodar a direita ate a
posicao certa ficar disponıvel)
procedure InsercaoLinear2(var x: vector; n: integer);
var novo, i, aux: integer;
para: boolean;
begin for novo := 2 to n do
begin aux := x[novo];
i := novo-1;
para := false;
while (i >= 1) and (not para) do
if aux > x[i] then para := true
else
begin x[i+1] := x[i];
i := i-1
end;
if x[i+1] > aux then x[i+1] := aux
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Insercao linear (bonus. . . )
procedure InsercaoLinear3(var x: vector; n: integer);
var novo, k, i, aux: integer;
para: boolean;
begin for novo := 2 to n do
begin
aux := x[novo];
i := novo-1;
para := false;
while (i >= 1) and (not para) do
if aux > x[i] then para := true
else i := i-1;
for k := novo downto i+2 do
x[k] := x[k-1];
x[i+1] := aux
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Seleccao linear
◮ Metodos de ordenacao: Seleccao linearDado o vector x com posicoes de 1 a n:
1. Encontrar o maior dos n elementos.2. Colocar esse elemento na posicao final por troca com o n-esimo.3. Ordenar as n − 1 primeiras posicoes do vector x.
Por exemplo, dado o vector: 10 3 15 99 23 teremos asseguintes situacoes:
10 3 15 23 99
10 3 15 23 99
10 3 15 23 99
3 10 15 23 99
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Seleccao linear
function IndexMaior(x: vector; n: integer): integer;
var i, posmax: integer;
begin posmax := 1;
for i := 2 to n do
if x[i] > x[posmax] then posmax := i;
IndexMaior := posmax
end;
procedure SeleccaoLinear(var x: vector; n: integer);
var i, posmax: integer;
begin for i := n downto 2 do
begin
posmax := IndexMaior(x, i);
Troca(x, i, posmax)
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Seleccao linear (sem subprogramas)
procedure SeleccaoLinear2(var x: vector; n: integer);
var i, j, posmax: integer;
begin
for i := n downto 2 do
begin
posmax := 1;
for j := 2 to i do
if x[j] > x[posmax] then posmax := j;
Troca(x, i, posmax)
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Borbulhagem
◮ Metodos de ordenacao: Borbulhagem (Bubblesort)Dado o vector x com posicoes de 1 a n:
1. Percorrer a tabela, trocando pares de elementos consecutivos fora deordem.
2. Repetir o processo ate se efectuar uma passagem completa semtrocar pares.
Por exemplo, dado o vector: 10 15 3 99 23 teremos as se-guintes situacoes:
10 3 15 23 99
3 10 15 23 99
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Borbulhagem
procedure Borbulhagem(var x: vector; n: integer);
var i: integer;
para: boolean;
begin
repeat
para := true;
for i:= 1 to n-1 do
if x[i] > x[i+1] then
begin
Troca(x, i, i+1);
para := false
end;
until para
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Borbulhagem (com limite melhorado)
◮ Metodos de ordenacao: Borbulhagem (Bubblesort)Depois de 1 passagem o maior elemento do vector fica colocado naultima posicao.Depois de 2 passagens o 2o maior elemento fica colocado napenultima posicao, e assim sucessivamente.Entao o no de componentes do vector consideradas pode irdiminuindo a cada passagem.Dado o vector x com posicoes de 1 a n:
1. Fazer dim=n.2. Percorrer a tabela da posicao 1 a dim, trocando pares de elementos
consecutivos fora de ordem.3. Decrementar dim.4. Repetir 2. e 3. ate se efectuar uma passagem completa sem trocar
pares.
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Borbulhagem (com limite melhorado)
procedure Borbulhagem1(var x: vector; n: integer);
var i, dim: integer;
para: boolean;
begin
dim := n;
repeat
para := true;
for i:= 1 to dim-1 do
if x[i] > x[i+1] then
begin
Troca(x, i, i+1);
para := false
end;
dim := dim-1;
until para
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Shellsort◮ Metodos de ordenacao: Shellsort
No algoritmo de borbulhagem trocam-se elementos contıguos dovector, o que pode levar a um elevado no de trocas.Uma alternativa (Donald Shell) troca elementos com um dado espa-camento entre si, que diminui quando nao se realizam trocas.Dado o vector x com posicoes de 1 a n:
1. Fazer espaco=n/2.2. Percorrer a tabela, trocar pares de elementos a distancia espaco fora
de ordem.3. Repetir 2. ate se efectuar uma passagem completa sem trocar pares.4. Fazer espaco=espaco/2.5. Repetir 2., 3. e 4. ate espaco=0.
Por exemplo, dado o vector: 99 23 15 10 3 teremos:
15 10 3 23 99
3 10 15 23 99
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Shellsort
procedure Shellsort(var x: vector; n: integer);
var i, espaco: integer;
para: boolean;
begin espaco := n div 2;
repeat
repeat
para := true;
for i:= 1 to n-espaco do
if x[i] > x[i+espaco] then
begin
Troca(x, i, i+espaco);
para := false
end;
until para;
espaco := espaco div 2;
until espaco = 0
end;
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Comparacao de eficiencia
◮ Quando existem varios algoritmos para implementar a mesmaoperacao e util compara-los em termos de eficiencia.
◮ O tempo de execucao pode depender da rapidez do processador.
◮ Em alternativa estima-se o no de operacoes (“mais relevantes”) quecada algoritmo implica para um conjunto de dados, para o melhorcaso, o caso medio ou o pior caso.
◮ Algoritmos de pesquisa: no de comparacoes◮ Algoritmos de ordenacao: no de comparacoes e/ou no de trocas
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Eficiencia
Pior dos casos: Borbulhagem
◮ O ciclo repeat-until e executado n − 1 vezes.
◮ Cada ciclo repeat-until inclui um ciclo for-to-do com n − 1passagens. Cada passagem faz 1 comparacao.
Numero total de comparacoes:
(n − 1)(n − 1) = n2 − 2n + 1
Numero total de trocas coincidente com o no de comparacoes.
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Eficiencia
Pior dos casos: Borbulhagem (com limite melhorado)
◮ Como em cada passagem pelo vector um dos elementos fica naposicao correcta, entao o ciclo repeat-until e executado, nomaximo, n − 1 vezes.
◮ Cada ciclo repeat-until inclui um ciclo for-to-do com n − kpassagens, com k = 1, . . . , n − 1. Em cada passagem e feita 1comparacao.
Numero total de comparacoes:
n−1∑
k=1
(n − k) =
n−1∑
k=1
n−n−1∑
k=1
k = n(n − 1)−n(n − 1)
2=
n(n − 1)
2=
n2 − n
2
Numero total de trocas coincidente com o no de comparacoes.
Metodos de Programacao 1
Metodologia da Programacao
Tabelas
Ordenamento de vectores: Eficiencia
Pior dos casos: Seleccao linear
◮ O ciclo for-to-do e executado n − 2 vezes.
◮ Cada ciclo for-to-do inclui a procura do maior elemento nas n − kprimeiras posicoes, com k = 2, . . . , n. Em cada passagem e feita 1comparacao.
Numero total de comparacoes:
n∑
k=2
(n − k − 1) =n−1∑
k=1
(n − k) =n2 − n
2
Numero total de trocas:n − 1
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Rercusividade
Algo diz-se recursivo quando e definido em funcao de si proprio.
Exemplos:
◮ Funcao factorial n! =
{n × (n − 1)!, n ≥ 1
1, n = 0
◮ Funcao potencia bn =
{b × bn−1, n ≥ 1
1, n = 0
mais sugestivos do que:
◮ Funcao factorial n! = n× (n − 1)× · · · × 2× 1
◮ Funcao potencia bn =
n vezes︷ ︸︸ ︷
b × b × · · · × b × b
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
RecursividadeImplementacoes iterativas
◮ Funcao factorial
function factorial(n: integer): integer;
var i, prod: integer;
begin prod := 1;
for i:=1 to n do
prod := prod*i;
factorial := prod
end;
◮ Funcao potencia
function potencia(b, n: integer): integer;
var i, prod: integer;
begin prod := 1;
for i:=1 to n do
prod := prod*b;
potencia := prod
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Chamada de uma funcao recursiva
factrec(3)
Valor devolvido: 3×factrec(2)
factrec(2)
Valor devolvido: 2×factrec(1)
factrec(1)
Valor devolvido: 1×factrec(0)
factrec(0)
Valor devolvido: 1
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Chamada de uma funcao recursiva
factrec(3)
Valor devolvido: 3×2
factrec(2)
Valor devolvido: 2×1
factrec(1)
Valor devolvido: 1×1
factrec(0)
Valor devolvido: 1
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Implementacoes recursivas
◮ Funcao factorial
function factRec(n: integer): integer;
begin
if n=0 then
factRec := 1 { chamada base }
else factRec := n * factRec(n-1) { chamada recursiva }
end;
◮ Funcao potencia
function potRec(b, n: integer): integer;
begin
if n=0 then
potRec := 1 { chamada base }
else potRec := b * potRec(b, n-1) { chamada recursiva }
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Notas:
◮ O caso base garante a paragem das chamadas recursivas.
◮ Cada chamada recursiva fica contida no bloco que a chamou.
◮ Cada chamada recursiva cria um novo conjunto de variaveis locais.As variaveis do bloco de chamada nao podem ser usadas masmantem-se em memoria.
Recursivo / Iterativo:
◮ Definicoes recursivas traduzem, muitas vezes, o processo de formamais natural e a sua implementacao e mais clara.
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Algoritmo de Euclides para determinar o maximo divisor comum entrea, b ∈ IN0
◮ mdc(a, b) = a se b = 0
◮ mdc(a, b) = mdc(b, a mod b) se b 6= 0
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
◮ Implementacao recursiva
function mdcRec(a, b: integer): integer;
begin if b=0 then
mdcRec := a
else mdcRec := mdcRec(b, a mod b)
end;
◮ Implementacao iterativa
function mdcIte(a, b: integer): integer;
var aux: integer;
begin while b <> 0 do
begin aux := a mod b;
a := b;
b := aux
end;
mdcIte := a
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
As versoes recursivas podem ser mais eficientes do que as iterativas.
Exemplo:
◮ Escrever um programa que inverta uma sequencia de caracteres.
procedure Inverter;
var c: char;
begin
read(c);
if c <> ’.’ then
Inverter;
write(c)
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
RecursividadeImplementacao iterativa (obriga ao uso duma tabela e conhecimentoprevio da dimensao maxima):
procedure LeVector(var x: vector; var n: integer);
var i: integer;
begin writeln(’De o tamanho do vector:’);
readln(n);
writeln(’De as ’, n, ’ componentes do vector:’);
for i := 1 to n do
read(x[i])
end;
procedure EscreveVectorInv(x: vector; n: integer);
var i: integer;
begin write(’Vector: ’);
for i := n downto 1 do
write(x[i]);
writeln
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Escrever um subprograma que calcule o numero de combinacoes de m, na n, dados m ≥ n, com:
(mn
)
=m!
n!(m − n)!
function comb1(m, n: integer): integer;
begin
comb1 := factRec(m) div (factRec(n)*factRec(m-n))
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Escrever um subprograma que calcule o numero de combinacoes de m, na n, dados m ≥ n, com:
(mn
)
=
(m − 1
n
)
+
(m − 1n − 1
)
sabendo que
(n0
)
= 1 e
(nn
)
= 1.
function comb2(m, n: integer): integer;
begin
if (n = 0) or (m = n)
then comb2 := 1
else comb2 := comb2(m-1, n)+comb2(m-1, n-1)
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Calculo de comb2(4,2) usando a versao recursiva:
comb2(4,2) comb2(3,2) comb2(2,2)=1comb2(2,1) comb2(1,1)=1
comb2(1,0)=1comb2(3,1) comb2(2,1) comb2(1,1)=1
comb2(1,0)=1comb2(2,0)=1
A versao recursiva efectua 11 chamadas de funcoes, algumas repetidas!.
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Versao iterativa:
function combIt(m, n: integer): integer;
var prod, i: integer;
begin
prod := 1;
for i := m downto m-n+1 do
prod := prod * i;
for i := n downto 2 do
prod := prod div i;
combIt := prod
end;
A versao iterativa utiliza 2 variaveis auxiliares.
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Elaborar subprogramas que leiam uma sequencia de inteiros positivos eescrevam as suas somas parciais,
1. da esquerda para a direita.
2. da direita para a esquerda.
3. da esquerda para a direita, e depois da direita para a esquerda
Exemplo:Os resultados de cada procedimento para a sequencia 1 2 3 4 5 0
seriam:
1. 1 3 6 10 15
2. 5 9 12 14 15
3. 1 3 6 10 15
5 9 12 14 15
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
procedure EscreveSomaEsq;
var sparcialE: integer;
procedure SomaEsq;
var n: integer;
begin read(n);
if n <> 0 then
begin
sparcialE := sparcialE + n;
write(sparcialE, ’ ’);
SomaEsq
end
end;
begin sparcialE := 0;
SomaEsq
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
procedure EscreveSomaDir;
var sparcialD: integer;
procedure SomaDir;
var n: integer;
begin read(n);
if n <> 0 then
begin
SomaDir;
sparcialD := sparcialD + n;
write(sparcialD, ’ ’)
end
end;
begin sparcialD := 0;
SomaDir
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividadeprocedure EscreveSoma;
var sparcialE, sparcialD: integer;
procedure Soma;
var n: integer;
begin read(n);
if n <> 0 then
begin
sparcialE := sparcialE + n;
write(sparcialE, ’ ’);
Soma;
sparcialD := sparcialD + n;
write(sparcialD, ’ ’)
end
else writeln
end;
begin sparcialE := 0;
sparcialD := 0;
Soma
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Pesquisa sequencial
function pesqSeqRec(x: vector; n, k: integer): integer;
begin
if n = 0 then
pesqSeqRec := 0
else
if x[n] = k then
pesqSeqRec := n
else pesqSeqRec := pesqSeqRec(x, n-1, k)
end;
Cada chamada recursiva cria uma copia do vector.
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Pesquisa sequencial com recursao encapsuladaEvita a copia do vector em cada nova chamada recursiva.
function pesqSeqRecEnc(x: vector; n, k: integer): integer;
function pesq(n: integer): integer;
begin
if n = 0 then pesq := 0
else
if x[n] = k then pesq := n
else pesq := pesq(n-1)
end;
begin pesqSeqRecEnc := pesq(n)
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade
Pesquisa binaria (vector ordenado)
function pesqBinRec(x: vector; esq, dir, k: integer): integer;
var m: integer;
begin
if esq > dir then pesqBinRec := 0
else
begin
m := (esq + dir) div 2;
if x[m] = k then pesqBinRec := m
else
if x[m] < k then
pesqBinRec := pesqBinRec(x, m+1, dir, k)
else pesqBinRec := pesqBinRec(x, esq, m-1, k)
end
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
RecursividadePesquisa binaria com recursao encapsulada (vector ordenado)
function pesqBinRecEnc(x: vector; n, k: integer): integer;
function pesq(esq, dir: integer): integer;
var m: integer;
begin if esq > dir then pesq := 0
else
begin m := (esq + dir) div 2;
if x[m] = k then pesq := m
else if x[m] < k then
pesq := pesq(m+1, dir)
else pesq := pesq(esq, m-1)
end
end;
begin pesqBinRecEnc := pesq(1, n)
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Mais recursividade1. Produto entre dois inteiros a e b
prod(a, b) =
{0 se b = 0
b + prod(a− 1, b) se b ≥ 1
2. Sucessao de Fibonacci
un =
0 se n = 11 se n = 2
un−1 + un−2 se n ≥ 3
3. Torres de Hanoi
Mover n discos da torre 1 para a torre 3, usando 2 como auxiliar.◮ Apenas se pode mover 1 disco de cada vez.◮ Um disco nao pode ser colocado em cima de outro mais pequeno.◮ Todos os discos tem que estar numa das torres.
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Ordenamento de vectores: Ordenamento por fusao (Mergesort)
◮ Metodos de ordenacao: MergesortDado o vector x com posicoes de 1 a n:
1. Ordenar a 1a metade de x (elementos de 1 a (n+1) div 2).2. Ordenar a 2a metade de x (elementos de (n+1) div 2 - 1 a n).3. Fundir as duas metades, mantendo a ordem.
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade: Ordenamento por fusao (Mergesort)
procedure MergeSort(var x: vector; n: integer);
procedure Ordena(esq, dir: integer);
var m: integer;
procedure Fusao(esq1, dir1, esq2, dir2: integer);
begin ...
end;
begin if dir-esq >= 1 then
begin m := (esq+dir) div 2;
Ordena(esq, m);
Ordena(m+1, dir);
Fusao(esq, m, m+1, dir)
end
end;
begin Ordena(1, n)
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade: Ordenamento por fusao (Mergesort)
procedure Fusao(esq1, dir1, esq2, dir2: integer);
var i, j, k, aux: integer;
begin i := esq1;
j := esq2;
repeat
if x[i] > x[j] then
begin aux := x[j];
for k := j downto (i+1) do
x[k] := x[k-1];
x[i] := aux;
j := j+1;
end
else i := i+1;
until (i >= j) or (j > dir2)
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Ordenamento de vectores: Quicksort
◮ Metodos de ordenacao: Quicksort
◮ Desenvolvido por Hoare (1961).◮ Promove a troca de elementos distantes do vector.
Dado o vector x com posicoes de 1 a n:
1. Escolher um elemento x[i] de x.2. Colocar x[i] na posicao correcta, s, de modo a que a esquerda
fiquem os elementos inferiores, e a direita os superiores, a x[i].3. Repetir o raciocınio para os subvectores de posicoes de 1 a s-1 e de
s+1 a n.
Tempo medio de execucao proporcional a: n log n.
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade: Quicksort
procedure Particao(var x: vector; n, A: integer);
var aux, esq, dir: integer;
begin esq := 1;
dir := n;
repeat
while x[esq] < A do esq := esq+1;
while x[dir] > A do dir := dir-1;
if esq <= dir then
begin Trocar(x, esq, dir);
esq := esq + 1;
dir := dir - 1
end
until esq > dir
end;
Chamada (elementos de x inferiores a x[(n+1) div 2] a esquerda esuperiores a direita):
Particao(x, n, x[(n+1) div 2]);
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade: Quicksort
procedure QuickSort(var x: vector; n: integer);
procedure OrdenaParcial(inf, sup: integer);
var A, esq, dir: integer;
begin ...
end;
begin OrdenaParcial(1, n)
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade: Quicksort
procedure OrdenaParcial(inf, sup: integer);
var A, esq, dir: integer;
begin esq := inf; dir := sup;
A := x[(inf + sup) div 2];
repeat
while x[esq] < A do esq := esq+1;
while x[dir] > A do dir := dir-1;
if esq <= dir then
begin Trocar(x, esq, dir);
esq := esq + 1; dir := dir - 1
end
until esq > dir;
if inf < dir then OrdenaParcial(inf, dir);
if esq < sup then OrdenaParcial(esq, sup)
end;
Metodos de Programacao 1
Metodologia da Programacao
Recursividade
Recursividade mutuaprogram ex(input, output);
var n: integer;
function EImPar(n: integer): boolean; forward;
function EPar(n: integer): boolean;
begin if n = 0 then Epar := true
else EPar := EImpar(n-1)
end;
function EImPar(n: integer): boolean;
begin if n = 0 then EImpar := false
else EImpar := EPar(n-1)
end;
begin write(’Qual e o n? ’); read(n);
if EPar(n) then writeln(’Sim, ’, n, ’ e par.’)
else writeln(’N~ao, ’, n, ’ n~ao e par.’);
end.
Metodos de Programacao 1
Registos
Registos
Registo:
Agregado de (um numero fixo de) elementos de tipos diferentes,cada um pode ser acedido atraves da identificacao do campo.
−→ record −→ lista de campos −→ end −→
Metodos de Programacao 1
Registos
Registos: Declaracao
Um registo e caracterizado:
1. pelos campos que o constituem, e tipos respectivos.
Exemplos:
type data = record dia: 1..31;
mes: 1..12;
ano: 1900..2100
end;
vector = record dim: integer;
elementos: array [1 .. DimMax] of real
end;
var ponto1, ponto2: record x, y: real
end;
x: vector;
aniversarios: array [1 .. 100] of data;
Metodos de Programacao 1
Registos
Registos: Acesso
Atribuicao global (valida para registos do mesmo tipo):
ponto1 := ponto2;
Atribuicao de campo (acrescentando a desginacao do campo a alterar):
ponto1.x := sqrt(4);
x.dim := 3;
x.elementos := [2.5 4.0 0];
Metodos de Programacao 1
Registos
Registos: Instrucao withA instrucao with:
permite fixar uma variavel do tipo registo e aceder de formasimplificada aos seus campos.
Exemplos:
◮ with ponto1 do
begin
x := ponto2.x;
y := ponto2.y
end;
◮ with x do
begin
readln(dim);
for i := 1 to dim do
read(elementos[i])
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
A serie harmonica revisitada:
1. Defina operacoes basicas para o tipo de dados
type fraccao = record num, den: integer
end;
3. Elabore um programa que imprima os primeiros n termos dasucessao associada a serie harmonica:
Hn = 1 +1
2+
1
3+ · · ·+
1
n
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure LeFraccao(var x: fraccao);
begin
writeln(’Escreva o numerador:’);
read(x.num);
writeln(’Escreva o denominador:’);
read(x.den)
end;
procedure EscreveFraccao(x: fraccao);
begin
if (x.num = 0) or (x.den = 1) then writeln(x.num)
else writeln(x.num,’/’,x.den)
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure Simplifica(var x: fraccao);
var aux: integer;
begin with x do
begin if den < 0 then
begin num := -num;
den := abs(den);
end;
aux := mdc(abs(num), den);
num := num div aux;
den := den div aux
end
end;
procedure NovaFraccao(x, y: integer; var res: fraccao);
begin res.num := x;
res.den := y;
simplifica(res)
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure Adicao(x, y: fraccao; var res: fraccao);
begin
NovaFraccao(x.num*y.den + y.num*x.den, x.den * y.den, res)
end;
procedure Subtraccao(x, y: fraccao; var res: fraccao);
begin
NovaFraccao(x.num*y.den - y.num*x.den, x.den * y.den, res)
end;
procedure Multiplicacao(x, y: fraccao; var res: fraccao);
begin
NovaFraccao(x.num*y.num, x.den * y.den, res);
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure SerieHarmonica(n: integer);
var i: integer;
aux, serie: fraccao;
begin
NovaFraccao(0, 1, serie);
for i:=1 to n do
begin
NovaFraccao(1, i, aux);
Adicao(serie, aux, serie);
EscreveFraccao(serie)
end
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
Suponha as declaracoes:
type Data = record dia: 1..31;
mes: 1..12;
ano: 1900..2100
end;
Id = record Nome: packed array [1..35] of char;
DataNas: Data;
Sexo: 1..2; { 1=Feminino, 2=Masculino }
EstCivil: 1..4 { 1=Solt, 2= Cas, 3=Viu, 4=Div }
end;
Faca subprogramas para:
1. saber se um candidato tem 16 anos no dia do previsto casamento.
2. saber se dois candidatos podem casar, isto e, se sao de sexosopostos, se tem ambos mais de 16 anos no dia do previstocasamento e se nao sao casados.
Metodos de Programacao 1
Registos
Tabelas compactadas
O tipo de dados packed array representa tabelas compactadas.
1. Declaracao:
type palavra = packed array [1..20] of char;
var p1, p2: palavra;
2. Manipulacao semelhante a de tabelas, mas admitindo atribuicaoglobal entre tabelas de igual comprimento:
p1 := ’Pascal ’;
p1 := p2;
3. Escrita:
writeln(’Linguagem: ’, p1);
4. Comparacao (lexicografica) entre tabelas de igual comprimento, comos operadores <, <=, >, >=, <>, =:
if p1 <= p2 then writeln(p1, ’ ’, p2)
else writeln(p2, ’ ’, p1);
Metodos de Programacao 1
Registos
Registos: Exemplo
1. function idade(x: Id; hoje: Data): integer;
var d, dh: integer;
begin
with x do
begin
dh := hoje.ano*10000 + hoje.mes*100 + hoje.dia;
d := DataNas.ano*10000 + DataNas.mes*100 + DataNas.dia
end;
idade := (dh - d) div 10000
end;
2. function PodeCasar(x1, x2: Id; dcas: Data): boolean;
var c: boolean;
begin
c := (idade(x1, dcas) >= 16) and (x1.EstCivil <> 2);
c := (idade(x2, dcas) >= 16) and (x2.EstCivil <> 2) and c;
c := (x1.Sexo <> x2.Sexo) and c;
PodeCasar := c
end;
Metodos de Programacao 1
Registos
Exemplo
3. Considere:
const max = 100;
type lista = array [1..max] of Id;
Escreva um programa que leia um ficheiro no formato:
1 / 2 / 1970 1 2 Esta
31 / 1 / 1970 2 1 Este
...
e escreva no ecra esta lista, por ordem alfabetica (e por ordem dedata de nascimento).
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure avanca;
var c: char;
begin repeat read(c) until c = ’/’
end;
procedure LeData(var d: data);
begin with d do
begin read(dia); avanca;
read(mes); avanca;
read(ano)
end
end;
Metodos de Programacao 1
Registos
Registos: Exemploprocedure LeNome(var p: palavra);
var i, k: integer;
begin i := 1;
while not eoln do
begin read(p[i]); i := i+1;
end;
for k := i to 35 do p[k] := ’ ’;
readln
end;
procedure LeCandidato(var x: Id);
begin with x do
begin write(’Dia de nascimento:’); LeData(DataNas);
write(’Sexo (1=F, 2=M):’); read(Sexo);
write(’Estado civil (1=S, 2=C, 3=V, 4=D):’);
read(EstCivil);
write(’Nome:’); LeNome(Nome)
end
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure LeLista(var x: lista; var n: integer);
var i: integer;
begin write(’Quantos s~ao?’);
read(n);
for i := 1 to n do LeCandidato(x[i]);
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure TrocaRegisto(var x: lista; i, j: integer);
var aux: Id;
begin
aux := x[i];
x[i] := x[j];
x[j] := aux
end;
procedure OrdenaAlfabeticamente(var x: lista; n: integer);
var i, j, max: integer;
begin for i := n downto 2 do
begin max := 1;
for j := 2 to i do
if x[j].nome > x[max].nome then max := j;
TrocaRegisto(x, i, max)
end;
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
function MaiorData(d1, d2: Data): boolean;
begin
with d1 do
MaiorData := (ano>d2.ano) or
((ano=d2.ano) and (mes>d2.mes)) or
((ano=d2.ano) and (mes=d2.mes) and (dia>d2.dia))
end;
procedure OrdenaData(var x: lista; n: integer);
var i, j, max: integer;
begin for i := n downto 2 do
begin
max := 1;
for j := 2 to i do
if MaiorData(x[j].DataNas, x[max].DataNas) then max := j;
TrocaRegisto(x, i, max)
end;
end;
Metodos de Programacao 1
Registos
Registos: Exemplo
Para evitar a troca de registos em x durante a ordenacao pode utilizar-seuma tabela que na posicao i contem o ındice do i-esimo elemento dalista ordenada.
Por exemplo, dado o vector:
Posicao:x:
1 2 3 4 5Vitor Elisa Anibal Ana Nuno
o seu correspondente “ordenado” e:
Posicao:x:
4 3 2 5 1Vitor Elisa Anibal Ana Nuno
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure OrdemAlfabetica(x: lista; n: integer; var P: vector);
var i, j, max: integer;
begin for i := n downto 2 do
begin max := 1;
for j := 2 to i do
if x[P[j]].nome > x[P[max]].nome then max := j;
TrocaPos(P, i, max)
end;
end;
...
{ Programa principal }
for i := 1 to n do Posicao[i] := i;
OrdemAlfabetica(x, n, Posicao);
...
Metodos de Programacao 1
Registos
Registos: Exemplo
procedure EscreveCandidato(x: Id);
begin
with x do
begin
write(DataNas.dia,’ / ’, DataNas.mes,’ / ’, DataNas.ano,’ ’);
writeln(Sexo,’ ’, EstadoCivil,’ ’, Nome)
end
end;
procedure EscreveLista(x: lista; n: integer);
var i: integer;
begin
for i := 1 to n do EscreveCandidato(x[i])
end;
Metodos de Programacao 1
Conjuntos
Conjuntos
Conjunto:
Agregado de elementos do mesmo tipo.
−→ set of −→ tipo simples −→
Permitem:
◮ denotar um grupo de variaveis por um unico identificador.
Metodos de Programacao 1
Conjuntos
Conjuntos: Declaracao
Declaracao:
type CorPrimaria = (amarelo, azul, vermelho);
Cor = set of CorPrimaria;
digitos = set of 0..9;
minusculas = set of ’a’..’z’;
var letra: minusculas;
d: digitos;
Exemplos de conjuntos:
◮ Vazio, ∅: []
◮ {0, 2, 4, 6, 8}: [0, 2, 4, 6, 8]
◮ {′a′,′ b′,′ c ′,′ d ′,′ j ′}: [’a’..’d’, ’j’]
◮ {amarelo, azul}: [amarelo..azul] (ou [amarelo, azul])
Metodos de Programacao 1
Conjuntos
Conjuntos: Relacoes
Pertenca:in : X × set → boolean
(x , S) 7→ x ∈ S
onde x deve ser do tipo dos elementos de S.
Exemplos:
◮ 2 in [0, 2, 4, 6, 8] e verdadeiro;
◮ amarelo in [azul] e falso;
◮ x in [] e falso, para qualquer valor de x.
Metodos de Programacao 1
Conjuntos
Conjuntos: Relacoes
Dados dois conjuntos, A e B, do mesmo tipo:
◮ A = B: igualdade A = B;
◮ A <> B: desigualdade A 6= B;
◮ A <= B: inclusao A ⊆ B;
◮ A >= B: inclusao B ⊆ A.
Exemplos:
◮ [2, 4] >= [4] e verdadeiro;
◮ [amarelo] = [azul] e falso;
◮ [] <= B e verdadeiro, para qualquer conjunto B.
Nota:
◮ [1, 2, 1] = [1, 2] = [2, 1]
Metodos de Programacao 1
Conjuntos
Conjuntos: Operacoes
Dados dois conjuntos, A e B, do mesmo tipo:
◮ A + B: representa a uniao de A e B, A ∪ B;
◮ A * B: representa a interseccao de A e B, A ∩ B;
◮ A - B: representa o complementar de B relativamente a A, A\B.
Exemplos:
◮ [0, 2, 4, 6, 8] + [2] e [0, 2, 4, 6, 8];
◮ [0, 2, 4, 6, 8] - [2] e [0, 4, 6, 8];
◮ [0, 4, 6, 8] - [3] e [0, 4, 6, 8];
◮ x + [] e x, para qualquer valor de x;
◮ x * [] e [], para qualquer valor de x.
Metodos de Programacao 1
Conjuntos
Conjuntos: Operacoes
Mais operacoes sobre conjuntos, dados
var A: digitos;
i: 0..9;
1. Inserir um elemento:
A := A + [i];
2. Remover um elemento:
A := A - [i];
3. Percorrer um conjunto (e escreve-lo):
for i := 1 to DMax do
if i in A then writeln(i);
Metodos de Programacao 1
Conjuntos
Conjuntos: Exemplo
Considerando as declaracoes
const sup = 100;
type elemento = inf..sup;
conjunto = set of elemento;
com inf = 2, crie e escreva o conjunto de numeros primos menores ouiguais a sup usando o metodo do Crivo de Eratostenes.
O Crivo de Eratostenes consiste em, comecando com uma lista completados inteiros, eliminar sucessivamente os multiplos de 2, 3, 5, . . . ate alista so conter numeros primos.
Metodos de Programacao 1
Conjuntos
Conjuntos: Exemplo
procedure CrivoEratostenes(n: elemento; var primos: conjunto);
var i, p: elemento;
crivo: conjunto;
begin crivo := [2..n];
primos := [];
i := 2;
while crivo <> [] do
begin while not(i in crivo) do i := i+1;
primos := primos + [i];
p := i;
while p <= n do
begin crivo := crivo - [p];
p := p + i;
end;
end;
end;
Metodos de Programacao 1
Revisoes
Exemplos
Todo o inteiro positivo pode ser decomposto como produto de potenciasde numeros primos. Por exemplo:
2268 = 22 × 34 × 71
Elabore subprogramas para:
1. Obter a representacao canonica de um inteiro positivo.
2. Verificar se um dado inteiro na forma canonica e, ou nao, umnumero primo.
3. Calcular o produto de dois numeros inteiros na forma canonica.
4. Calcular o maximo divisor comum de dois inteiros na forma canonica.
5. Calcular o mınimo multiplo comum de dois inteiros na formacanonica.
Metodos de Programacao 1
Revisoes
Exemplosprogram TrataCanonico(input,output);
type intnneg = 0..MAXINT;
canonico = array [1..100] of intnneg;
var a, b, adim, bdim, resdim: intnneg;
aP, aE, bP, bE, resP, resE: canonico;
procedure le_n(var n: intnneg);
begin repeat
write(’De n:’);
readln(n);
until n > 0
end;
procedure novofactor(var nP, nE: canonico; var ndim: intnneg;
p, e: intnneg);
begin ...
end;
Metodos de Programacao 1
Revisoes
Exemplos
procedure cria_canonico(n: intnneg;
var nP, nE: canonico; var ndim: intnneg);
begin ...
end;
function primo(nP, nE: canonico; ndim: intnneg): boolean;
begin ...
end;
procedure produto(nP, nE, mP, mE: canonico; ndim, mdim: intnneg;
var resP, resE: canonico; var resdim: intnneg);
begin ...
end;
procedure mmc(nP, nE, mP, mE: canonico; ndim, mdim: intnneg;
var resP, resE: canonico; var resdim: intnneg);
begin ...
end;
Metodos de Programacao 1
Revisoes
Exemplos
procedure mdc(nP, nE, mP, mE: canonico; ndim, mdim: intnneg;
var resP, resE: canonico; var resdim: intnneg);
begin ...
end;
procedure imprime_canonico(nP, nE: canonico; ndim: intnneg);
begin ...
end;
begin le_n(a); cria_canonico(a, aP, aE, adim);
le_n(b); cria_canonico(b, bP, bE, bdim);
produto(aP, aE, bP, bE, adim, bdim, resP, resE, resdim);
write(’Produto:’); imprime_canonico(resP, resE, resdim);
mmc(aP, aE, bP, bE, adim, bdim, resP, resE, resdim);
write(’MMC:’); imprime_canonico(resP, resE, resdim);
mdc(aP, aE, bP, bE, adim, bdim, resP, resE, resdim);
write(’MDC:’); escrever_canonico(resP, resE, resdim)
end.
Metodos de Programacao 1
Revisoes
Exemplos
procedure novofactor(var nP, nE: canonico; var ndim: intnneg;
p, e: intnneg);
begin ndim := ndim + 1;
nP[ndim] := p;
nE[ndim] := e
end;
function primo(nP, nE: canonico; ndim: intnneg): boolean;
begin primo := (ndim = 0) or ((ndim = 1) and (nE[1] = 1))
end;
procedure imprime_canonico(nP, nE: canonico; ndim: intnneg);
var i: intnneg;
begin write(nP[1]:1, ’^’, nE[1]:1)
for i := 2 to ndim do
write(’ x ’, nP[i]:1, ’^’, nE[i]:1)
end;
Metodos de Programacao 1
Revisoes
Exemplos
procedure cria_canonico(n: intnneg; var nP, nE: canonico;
var ndim: intnneg);
var i, cont: intnneg;
begin i := 2;
ndim := 0;
while n > 1 do
begin cont := 0;
while (n mod i = 0) and (n > 1) do
begin n := n div i;
cont := cont + 1
end;
if cont > 0 then
novofactor(nP, nE, ndim, i, cont)
i := i + 1
end
end;
Metodos de Programacao 1
Revisoes
Exemplos
procedure produto(nP, nE, mP, mE: canonico; ndim, mdim: intnneg;
var resP, resE: canonico; var resdim: intnneg);
var ni, mi: intnneg;
begin
resdim := 0;
ni := 1;
mi := 1;
...
Metodos de Programacao 1
Revisoes
Exemplos
while (ni <= ndim) and (mi <= mdim) do
if nP[ni] < mP[mi] then
begin novofactor(resP, resE, resdim, nP[ni], nE[ni]);
ni := ni + 1
end
else
if nP[ni] > mP[mi] then
begin novofactor(resP, resE, resdim, mP[mi], mE[mi]);
mi := mi + 1
end
else
begin novofactor(resP, resE, resdim, nP[ni], nE[ni]+mE[mi]);
ni := ni + 1;
mi := mi + 1
end;
...
Metodos de Programacao 1
Revisoes
Exemplos
while (ni <= ndim) do
begin novofactor(resP, resE, resdim, nP[ni], nE[ni]);
ni := ni + 1
end;
while (mi <= mdim) do
begin novofactor(resP, resE, resdim, mP[mi], mE[mi]);
mi := mi + 1
end
end;
Metodos de Programacao 1
Revisoes
Exemplos
procedure mmc(nP, nE, mP, mE: canonico; ndim, mdim: intnneg;
var resP, resE: canonico; var resdim: intnneg);
var ni, mi, max: intnneg;
begin
resdim := 0;
ni := 1;
mi := 1;
...
Metodos de Programacao 1
Revisoes
Exemplos
while (ni <= ndim) and (mi <= mdim) do
if nP[ni] < mP[mi] then
begin novofactor(resP, resE, resdim, nP[ni], nE[ni]);
ni := ni + 1
end
else
if nP[ni] > mP[mi] then
begin novofactor(resP, resE, resdim, mP[mi], mE[mi]);
mi := mi + 1
end
else
begin if nE[ni] < mE[mi] then max := mE[mi]
else max := nE[ni];
novofactor(resP, resE, resdim, mP[mi], max);
ni := ni + 1; mi := mi + 1
end;
Metodos de Programacao 1
Revisoes
Exemplos
while (ni <= ndim) do
begin novofactor(resP, resE, resdim, nP[ni], nE[ni]);
ni := ni + 1
end;
while (mi <= mdim) do
begin novofactor(resP, resE, resdim, mP[mi], mE[mi]);
mi := mi + 1
end
end;
Metodos de Programacao 1
Revisoes
Exemplos
procedure mdc(nP, nE, mP, mE: canonico; ndim, mdim: intnneg;
var resP, resE: canonico; var resdim: intnneg);
var ni, mi, min: intnneg;
begin resdim := 0;
ni := 1;
mi := 1;
while (ni <= ndim) and (mi <= mdim) do
if nP[ni] < mP[mi] then ni := ni + 1
else
if nP[ni] > mP[mi] then mi := mi + 1
else
begin if nE[ni] < mE[mi] then min := nE[ni]
else min := mE[mi];
novofactor(resP, resE, resdim, mP[mi], min);
ni := ni + 1;
mi := mi + 1
end
end;