Algoritmia 2 - dei.isep.ipp.ptnfreire/ALGORITMIA 2... · Algoritmo Estrutura Genérica Instruções Validação de um Algoritmo Funções Algoritmia Sumário Geral . Nelson Freire

Nelson Freire (ISEP–DEI-APROG 2013/14) 1/52

Algoritmia 2 Conceitos Básicos

Estruturas de Dados

Instruções de Leitura, Escrita, Atribuição e Decisão

APROG Algoritmia e Programação


Conceitos Básicos

Programa

Modelos de Programação

Programação Procedimental

Método de Desenvolvimento de um Programa

Algoritmos

Representação

Estrutura Básica

Estruturas de Dados

Algoritmo

Estrutura Genérica

Instruções

Validação de um Algoritmo

Funções

Algoritmia Sumário Geral


Conceitos Básicos

Programa




Algoritmos

Representação

Estrutura Básica

Estruturas de Dados

Algoritmo

Estrutura Genérica

Instruções


Funções



Noção de Programa

Sequência de instruções para um computador realizar uma tarefa específica

Em Geral

Lê Dados

Processa Dados

Mostra Resultados

Conceitos Básicos Programa

Dados

Resultados

Programa


Outra Designação

Paradigmas de Programação

Exemplos

Procedimental // APROG

Orientado por Objetos

Funcional

Lógico

Conceitos Básicos Modelos de Programação


Programa = Estruturas de Dados + Algoritmo

Estruturas de Dados

Armazenam dados do programa em memória

Dados

Entrada

Auxiliares

Resultados

Algoritmo

Sequência de instruções

Conceitos Básicos Programação Procedimental

Estruturas de Dados

Algoritmo Programa


Conceitos Básicos Método de Desenvolvimento de um Programa

Análise de Requisitos

Conceção de um Algoritmo (Pseudo-Código ou Fluxograma)

Teste

Algoritmo Válido

Codificação do Algoritmo (Linguagem de Programação JAVA)

Teste

Algoritmo Inválido

Programa

Plano de Teste

Traçagem Manual

Especificação de Requisitos (Enunciado do Problema)

Programa Válido

Programa Inválido


Conceitos Básicos

Programa




Algoritmos

Representação

Estrutura Básica

Estruturas de Dados

Algoritmo

Estrutura Genérica

Instruções


Funções



Formas

Pseudo-Código

Linguagem escrita

Linguagem não-formal

Não compilada

Fluxograma

Forma gráfica

Esquema de símbolos gráficos

Algoritmos Representação de um Algoritmo



Estruturas de Dados + Algoritmo

Pseudo-código

Fluxograma

Estrutura Básica de um Algoritmo

ED

// Declaração de Estruturas de Dados ALG INÍCIO // Sequência de Instruções FIM

Nota

//representa comentário

Algoritmos


Conceitos Básicos

Programa




Algoritmos

Representação

Estrutura Básica

Estruturas de Dados

Algoritmo

Estrutura Genérica

Instruções


Funções



Noção de Estrutura de Dados

Tipos de Dados

Tipos de Estruturas de Dados

Variáveis

Constantes

Variáveis

Tipos

Declaração

Constantes

Tipos

Declaração

Interesse dos Tipos de Dados

Estruturas de Dados Sumário


Noção Simples

Permite armazenar os dados do programa em memória

Existem vários tipos de estrutura de dados

Para vários tipos de dados (texto, números, ...)

Para rentabilizar memória

Tipos de dados têm requisitos de memória diferentes

Estruturas de Dados Noção de Estrutura de Dados

Dados

RAM

Dados

Resultados

Programa


Numéricos

INTEIRO // Ex: 12

REAL // Ex: 1.5

Alfanumérico

TEXTO // sequência de carateres.

// Ex: "Valor Inválido"

Carater

CARATER // Ex: '+', '/', 'a', 'A'

Lógico

BOOLEANO // VERDADEIRO ou FALSO

Estruturas de Dados Tipos de Dados


Variáveis

Conteúdo (valor) pode ser alterado durante execução do programa

Constantes

Conteúdo (valor) não pode ser alterado durante execução do programa

Estruturas de Dados Tipos de Estruturas de Dados


Tipos

Simples (guardam um valor simples – de cada vez)

Numéricas

INTEIRO // para guardar um valor inteiro

REAL

Alfanumérica

TEXTO // para guardar uma sequência de carateres

Lógico

BOOLEANO // para guardar o valor VERDADEIRO ou FALSO

Carater

CARATER // para guardar um carater

Complexas (guardam conjuntos de dados)

Vetores // em memória volátil (RAM)

Ficheiros // em memória permanente (Disco, DVD, etc.)

Estruturas de Dados Variáveis 1/2


Declaração

Sintaxe (formato)

Tipo_de_Dados lista_nomes_variáveis // vírgula para separar

Exemplos

INTEIRO nota_1, nota_2

TEXTO nome

Nomes

Devem ser significativos

Tornam programa fácil de

Ler

Compreender

Detetar erros

Desenvolver

Estruturas de Dados Variáveis 2/2


Tipos

Numéricas

INTEIRO // para guardar um valor inteiro

REAL

Alfanumérica

TEXTO // para guardar uma sequência de carateres

Lógico

BOOLEANO // para guardar o valor VERDADEIRO ou FALSO

Carater

CARATER // para guardar um carater

Estruturas de Dados Constantes 1/2


Declaração

Sintaxe

CONSTANTE Tipo_de_Dados nome=valor

Exemplo

CONSTANTE REAL PI=3.14

Nomes

Devem ser significativos

Tornam programa fácil de

Ler

Compreender

Detetar erros

Desenvolver

Estruturas de Dados Constantes 2/2


Melhor gestão do espaço de memória do programa

Espaço de memória ajustado aos tipos de dados

Programas mais robustos

Cada tipo de dados define o conjunto de operações que podem ser

executadas sobre os respectivos dados

P. ex., impede

TEXTO * TEXTO

TEXTO / TEXTO

Estruturas de Dados Interesse dos Tipos de Dados


Conceitos Básicos

Programa




Algoritmos

Representação

Estrutura Básica

Estruturas de Dados

Algoritmo

Estrutura Genérica

Instruções


Funções



Corresponde à Estrutura Genérica de um Programa

Algoritmo Estrutura Genérica da Secção Algoritmo (ALG)

Processamento

Saída/Escrita de Resultados

Entrada/Leitura de Dados

Resultados Resultados

Dados Dados

Programa


Tipos de Instruções

Leitura

Escrita

Atribuição

Controlo de Fluxo

Decisão

Repetição

Algoritmo Instruções

ED

// declarações de variáveis e constantes

ALG

INÍCIO

// sequência de instruções

FIM


Interesse

Ler dados da entrada do computador e guardá-los em variáveis

Pseudo-Código Fluxograma

Sintaxe

LER(lista_variáveis)

Exemplos

LER(nome)

LER(nota_1,nota_2)

Leitura e Escrita Instrução de Leitura

nome

nota_1, nota_2

lista_variáveis


Interesse

Escrever na saída do computador, uma lista de valores, conteúdos de variáveis e/ou constantes


Sintaxe

ESCREVER(lista_valores)

Exemplos

ESCREVER(nome)

ESCREVER(“Nome=“,nome)

Instrução de Escrita Leitura e Escrita

lista_valores

nome

“Nome=“,nome


Interesse

Alterar o conteúdo (valor) de uma variável


Sintaxe

variável valor // operador de atribuição:

Exemplo

nome “APROG”

y 5 + x // x é uma variável

Atribuição Instrução de Atribuição

variável valor

nome “APROG”

y 5 + x


Usados

Expressões Aritméticas Operadores Aritméticos

+ ( adição )

- ( subtracção )

* ( multiplicação )

/ ( divisão real ) Ex: x/ 10 Ex: 15 / 10 ( = 1.5 )

DIV ( divisão inteira ) Ex: x DIV 10 Ex: 15 DIV 10 ( = 1 )

MOD ou % ( resto da divisão inteira ) Ex: x MOD 4 EX: 15 % 10 ( = 5 )

^ ( exponenciação ) Ex: x ^ 5

Operadores Aritméticos Atribuição


Interesse Definir ordem de execução das operações em expressões com múltiplos operadores Exemplo

X + 5 * 10 ^ 2

Listagem

Precedência de Operadores (Em Geral) Atribuição

()

NÃO

^

* / DIV MOD

+ -

< <= > >=

= !=

E

OU

Maior

Menor

Operadores Precedência

Nota: operadores na mesma linha têm a mesma precedência


Interesse

Tipos de Instruções de Decisão

Condição

Instrução SE

Instrução CASO

Instruções SE Encaixadas

Erros Frequentes

Decisão Sumário


Escolher uma ação entre várias ações alternativas

Exemplo

Conversão de Euros em Dólares, Libras ou Ienes

Decisão Interesse


SE

SE ... ENTÃO ... SENÃO

SE ... ENTÃO

CASO

Instruções SE

Decisão é baseada numa condição

Decisão Tipos de Instruções de Decisão


É uma expressão booleana // proposição

Valor é VERDADEIRO ou FALSO

Pode usar os operadores

Relacionais = ≠ ( alternativas: != , <>) > ≥ ( >= ) < ≤ ( <= )

Lógicos

OU (x<0 OU y<0) // VERDADEIRO => Pelo menos 1 condição simples verdadeira

E (x<0 E y<0) // VERDADEIRO => Todas condições simples verdadeiras

NÃO NÃO(x<0)

Tipos

Simples Ex: nota<15 // não é decomposta noutras condições

Composta Ex: (x+1≥y)E(x>20) // pode ser decomposta noutras condições

Condição Decisão


Sintaxe (Pseudo-Código)

Semântica (Fluxograma)

SE (Condição) ENTÃO

instrução_1

...

instrução_n

SENÃO

instrução_1

...

instrução_m

FSE

Tipos

SE ... ENTÃO ... SENÃO // Para escolher 1 ação entre 2 ações alternativas

SE ... ENTÃO // Para condicionar a execução de uma acção

SE (Condição) ENTÃO

instrução_1

...

instrução_n

FSE

Ação

Instrução SE Decisão

Ação 1

Ação 2


Determinar se um dado número inteiro é ou não positivo

Algoritmo (Pseudo-Código)

Traçagens

Instrução SE: Exemplo 1 Decisão

ED

INTEIRO n

INÍCIO

ESCREVER("Insira um número inteiro:")

LER(n)

SE (n>0) ENTÃO

ESCREVER(n, " é um número positivo")

SENÃO

ESCREVER(n, " não é um número positivo")

FSE

FIM

n n>0 Saída

Insira um número inteiro

10

V

10 é um número positivo

n n>0 Saída


-3

F

-3 não é um número positivo


Determinar o valor absoluto de um dado número inteiro


Traçagens

Instrução SE: Exemplo 2 Decisão

ED

INTEIRO n

INÍCIO

ESCREVER("Insira um número inteiro:")

LER(n)

SE (n<0) ENTÃO

n <- n * (-1)

FSE

ESCREVER("Valor absoluto é ",n)

FIM

n n<0 Saída


-3

V

Valor absoluto é 3

n n<0 Saída


5

F

Valor absoluto é 5


Exemplos de selector x // varíável tipo inteiro x+1

Especificação de Cada caso (caso_1, ..., caso_n) Lista de valores ... que selector pode assumir Valores discretos

Ex: 1,2,3,4 ( x≥1 E x≤4 ) Valores únicos Ordem dos valores é irrelevante

Caso OUTRO Opcional

Sintaxe (Pseudo-Código)

Semântica (Fluxograma)

CASO (selector) SEJA caso_1: ação_1 caso_2: ação_2

... caso_n: ação_n OUTRO: ação_outro

FCASO

Interesse Para escolher uma ação entre múltiplas ações alternativas ... ... cuja seleção é baseada no valor de uma expressão (selector) do tipo inteiro ou carater

Instrução CASO Decisão


Converter Euros em Dólares, Libras ou Ienes


Instrução CASO: Exemplo 1 Decisão 1/2

ED

REAL euros

CARATER moeda

INÍCIO

ESCREVER("Euros:")

LER(euros)

SE (euros<=0) ENTÃO

ESCREVER("Valor Inválido")

SENÃO

ESCREVER("Escolha uma Moeda: Dólar (d), Libra (l) ou Iene (i)")

LER(moeda)

ESCREVER(euros, " Euros = ")

CASO moeda SEJA

'd', 'D': ESCREVER(euros * 1.534, " Dólares")

'l', 'L': ESCREVER(euros * 0.774, " Libras")

'i', 'I': ESCREVER(euros * 161.480, " Ienes")

OUTRO: ESCREVER("Moeda Inválida")

FCASO

FSE

FIM


Traçagens


euro moeda euro<=0 Saída

Euros:

10

F

Escolha uma Moeda: Dólar (d), Libra (l) ou Iene (i)

d

10 Euros =

13.18 Dólares


Euros:

-5

V

Valor Inválido


Euros:

10

F

Escolha uma Moeda: Dólar (d), Libra (l) ou Iene (i)

i

Moeda Inválida


Determinar nº de dias de um dado mês e ano



ED

INTEIRO mes, ano

INÍCIO

ESCREVER("Insira o número do mês")

LER(mes)

CASO (mes) SEJA

1,3,5,7,8,10,12: ESCREVER("Mês tem 31 dias")

4,6,9,11: ESCREVER("Mês tem 30 dias")

2: ESCREVER("Insira o ano")

LER(ano)

SE (ano<1) ENTÃO

ESCREVER("Ano Inválido !!!")

SENÃO

SE (ano MOD 4=0 E (ano MOD 100!=0 OU ano MOD 400=0)) ENTÃO

ESCREVER("Mês tem 29 dias")

SENÃO

ESCREVER("Mês tem 28 dias")

FSE

FSE

OUTRO: ESCREVER("Mês Inválido !!!")

FCASO

FIM


Traçagens


mes ano ano<1

ano MOD 4=0

E

(ano MOD 100!=0 OU ano MOD 400=0)

Saída

Insira o número do mês

2

Insira o ano

2012

F

V

Mês tem 29 dias

mes ano ano<1

ano MOD 4=0

E


Saída


10

Mês tem 31 dias

mes ano ano<1

ano MOD 4=0

E


Saída


0

Mês Inválido !!!


Exemplo 1

LER(nota)

SE (nota<8) ENTÃO

ESCREVER(‘‘Reprovado‘‘) SENÃO

SE (nota<10) ENTÃO

ESCREVER (‘‘Oral‘‘) SENÃO

ESCREVER(‘‘Aprovado‘‘) FSE

FSE

Interesse Para escolher uma ação entre mais de duas ações alternativas

LER(nota)

SE (nota<8) ENTÃO

SE (estatuto=‘‘especial‘‘) ENTÃO

ESCREVER(‘‘Oral‘‘)

SENÃO

ESCREVER(‘‘Reprovado‘‘) FSE

SENÃO

SE (nota<10) ENTÃO

ESCREVER (‘‘Oral‘‘)

SENÃO

ESCREVER(‘‘Aprovado‘‘) FSE

FSE

Exemplo 2

Instruções SE Encadeadas/Encaixadas Decisão


Condição

INTEIRO x, y, z

Fluxograma

Incorrecto Correcto

Erros Frequentes

Incorrecto Correcto

SE ( xy ) ENTÃO ... SE ( x=y ) ENTÃO ...

SE ( x=y=z ) ENTÃO ... SE ( x=y E y=z ) ENTÃO ...

LER(x) x

ESCREVER(“X:”, x) “X:”, x

Decisão


Conceitos Básicos

Programa




Algoritmos

Representação

Estrutura Básica

Estruturas de Dados

Algoritmo

Estrutura Genérica

Instruções


Funções



Plano de Testes

Traçagem Manual

Validação do Algoritmo Sumário


Validação do Algoritmo Plano de Testes

Noção

Especifica um conjunto de testes para validar um algoritmo

Cada teste define

Dados de entrada

Resultado esperado

Representação

Tabela

Exemplo

Programa para mostrar o quadrante a que pertence um ponto (x,y) fornecido pelo utilizador

Teste Nº

Dados de Entrada Resultado Esperado Resultado Obtido

Verificação (Passou ou Falhou) x y

1 1 1 1º Quadrante

2 -1 1 2º Quadrante

3 -1 -1 3º Quadrante

... ... ... ...


Validação do Algoritmo Traçagem Manual

Noção

Representa a execução passo-a-passo de um algoritmo

Representação

Tabela

Uma coluna para cada variável

Uma coluna para cada condição

Uma coluna para a saída

Exemplo

Traçagem para x=1 e y=2

x y s s MOD 2 = 0 Saída

X:

1

Y:

2

3

F

3 é ímpar

// Exemplo ED INTEIRO x, y, s INÍCIO ESCREVER("X:") LER(x) ESCREVER("Y:") LER(y) s <- x + y SE (s MOD 2 = 0) ENTÃO ESCREVER(s," é par") SENÃO ESCREVER(s," é ímpar") FSE FIM


Conceitos Básicos

Programa




Algoritmos

Representação

Estrutura Básica

Estruturas de Dados

Algoritmo

Estrutura Genérica

Instruções


Funções



Noção de Função

Funções

Matemáticas

Texto

Números Aleatórios

Funções Sumário


Funções Noção de Função

Interesse

Retorna resultado de uma operação e pode aceitar múltiplos argumentos

Exemplo

Função ABS(x)

Retorna valor absoluto do argumento x

x pode ser um valor, uma variável ou uma expressão numérica

Exemplos

ED

REAL r, y, w

INTEIRO v

INÍCIO

...

r <- ABS(y) + ABS(w+8)

...

SE( ABS(y) > r ) ENTÃO

...

FSE

...

CASO ( ABS(v) ) SEJA

...

FCASO

...

ESCREVER( "Resultado =", ABS(r))

FIM


Funções Matemáticas

Interesse

Retornam resultado de operação matemática

Exemplos

Sintaxe Resultado

RAIZQUADRADA(x) Raiz quadrada de x

SENO(x) Seno do ângulo x (x em radianos)

COS(x) Co-seno do ângulo x (x em radianos)

TG(x) Tangente do ângulo x (x em radianos)

ABS(x) Valor absoluto de x

ARREDONDAR(x,n) x arredondado para n casas decimais

INT(x) Parte inteira de x


Funções Texto

Interesse

Retornam o resultado de uma operação sobre valores do tipo TEXTO

Exemplos

Função Resultado

COMPRIMENTO(texto) Número de carateres de texto

MAIUSCULAS(texto) texto com letras maiúsculas

MINUSCULAS(texto) texto com letras minúsculas

SEPARAR(texto,s) Vector contendo as sequências de carateres delimitadas por s que existem dentro de texto

INDICE(texto,c) Índice do carater c dentro de texto. O primeiro carater tem índice zero.

VALOR(texto) Valor numérico correspondente ao valor guardado em texto.

RETIRARESPAÇOS(texto) texto sem espaços no início e no fim


Funções Número Aleatório

Exemplos de Uso

Função Resultado

ALEATORIO() Número REAL aleatório entre [0, 1[

ED REAL r, w INTEIRO i INÍCIO ... r ALEATORIO() ... SE( ALEATORIO() > w ) ENTÃO ... FSE ... ESCREVER( "Número Aleatório =", ALEATORIO() ) ... i INT(ALEATORIO() * 10) + 1 FIM

i nº inteiro aleatório do intervalo [1, 11[

Fórmula INT(ALEATORIO() * (largura intervalo) ) +

limite Inferior intervalo largura intervalo = limite superior – limite

inferior

Documents

Algoritmia 2 - dei.isep.ipp.ptnfreire/ALGORITMIA 2... · Algoritmo Estrutura Genérica Instruções Validação de um Algoritmo Funções Algoritmia Sumário Geral . Nelson Freire