View
102
Download
0
Category
Preview:
Citation preview
Introdução à Programação
ETI e IGE
ISCTE
2003/2004Introdução à Programação2
Docentes
Manuel Menezes de Sequeira Joaquim Esmerado Maria Albuquerque Luís Mota
Responsável: Prof. Manuel Menezes de Sequeira Manuel.Sequeira@iscte.pt Gabinete D6.18 Cacifo 202 Telefone 217903909 Telemóvel 962337428 MSN: MMSequeira@hotmail.com Yahoo!: Manuel_Menezes_de_Sequeira
2003/2004Introdução à Programação3
Informação
http://iscte.pt/programacao/p1 http://br.groups.yahoo.com/group/ip-iscte ip-iscte@yahoogrupos.com.br Folhas teóricas Diapositivos das aula teóricas Resumos das aulas práticas
2003/2004Introdução à Programação4
Avaliação
Problema: 10% Em grupo
Trabalho Final: 40% Entrega intermédia: avaliação negativa = -3 Entrega final: trabalho completo Em grupo, com discussão individual
Frequência: 50% Individual, sem consulta: nota mínima 7
Grupos: 2 alunos
2003/2004Introdução à Programação5
Objectivos
Conhecer abordagens típicas de resolução de problemas
Ser capaz de planear resolução de problemas, desenhando e estruturando programas
Dominar ambiente de desenvolvimento e respectivas ferramentas
Ter conhecimentos intermédios de C++
2003/2004Introdução à Programação6
Programa (I)
Programação procedimental Tipos, variáveis e constantes Modularização, abstracção e encapsulamento Rotinas Noções de programação por contrato:
asserções Controlo de fluxo Desenvolvimento de ciclos Agregados
2003/2004Introdução à Programação7
Programa (II)
Programação baseada em objectos: Tipos abstractos de dados Invariantes de classe Classes e categorias de acesso De novo modularização, abstracção e
encapsulamento
2003/2004Introdução à Programação8
Metodologia
Aulas teóricas (2 x 50m) Aulas laboratoriais (3 x 50m) Aulas de dúvidas Esclarecimento de dúvidas via correio
electrónico Por vezes no canal #C++ do IRC
Aula 1
Introdução à programação
2003/2004Introdução à Programação10
O que é um computador?
Máquinaprogramávelgenérica
Processador Memória rápida
RAM e ROM Memória lenta
disco rígido
2003/2004Introdução à Programação11
Arte de Resolver Problemas
Diz-se que só se compreende realmente um assunto depois de o ter ensinado a alguém. Na realidade, só se compreende realmente um assunto depois de o ter ensinado a um computador.
Donald E. Knuth
2003/2004Introdução à Programação12
Algoritmo
Método de resolução de problema Características:
Finitude: tem de terminar Definitude: cada passo bem definido Entradas: zero ou mais, de conjunto bem
definido Saídas: uma ou mais, dependem das entradas Eficácia: operações todas executáveis
2003/2004Introdução à Programação13
Problema
Cálculo do máximo divisor comum de dois inteiros positivos
Entradas: m e n Saídas: k, tal que k = mdc(m, n)
0 < mdc(m, n), ou seja, 1 <= mdc(m, n) mdc(m, n) <= min(m, n)
2003/2004Introdução à Programação14
Variáveis
m : inteiro
12
Nome
Tipo
Valor
2003/2004Introdução à Programação15
Algoritmo do mdc
1
se m < n então
2
k <- m
3
senão
4
k <- n
5
enquanto m ÷ k <> 0 ou n ÷ k <> 0 faça-se:
6
k <- k – 1
7
fim do enquanto
8
2003/2004Introdução à Programação16
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
2003/2004Introdução à Programação17
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
2003/2004Introdução à Programação18
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
2003/2004Introdução à Programação19
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
2003/2004Introdução à Programação20
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
2003/2004Introdução à Programação21
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
7 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
2003/2004Introdução à Programação22
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
7 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
2003/2004Introdução à Programação23
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
7 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
7 12 8 6 Falso Falso Verdadeiro Verdadeiro
2003/2004Introdução à Programação24
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
7 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
7 12 8 6 Falso Falso Verdadeiro Verdadeiro
6 12 8 6 Falso Falso Verdadeiro Verdadeiro
2003/2004Introdução à Programação25
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
7 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
7 12 8 6 Falso Falso Verdadeiro Verdadeiro
6 12 8 6 Falso Falso Verdadeiro Verdadeiro
7 12 8 5 Falso Verdadeiro Verdadeiro Verdadeiro
2003/2004Introdução à Programação26
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
7 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
7 12 8 6 Falso Falso Verdadeiro Verdadeiro
6 12 8 6 Falso Falso Verdadeiro Verdadeiro
7 12 8 5 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 5 Falso Verdadeiro Verdadeiro Verdadeiro
2003/2004Introdução à Programação27
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
7 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
7 12 8 6 Falso Falso Verdadeiro Verdadeiro
6 12 8 6 Falso Falso Verdadeiro Verdadeiro
7 12 8 5 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 5 Falso Verdadeiro Verdadeiro Verdadeiro
7 12 8 4 Falso Falso Falso Falso
2003/2004Introdução à Programação28
Traçado do algoritmo do mdc
Transição m n k m < n m ÷ k <> 0 n ÷ k <> 0 m ÷ k <> 0 ou n ÷ k <> 0
1 12 8 ? Falso ? ? ?
4 12 8 ? Falso ? ? ?
5 12 8 8 Falso Verdadeiro Falso Verdadeiro
6 12 8 8 Falso Verdadeiro Falso Verdadeiro
7 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 7 Falso Verdadeiro Verdadeiro Verdadeiro
7 12 8 6 Falso Falso Verdadeiro Verdadeiro
6 12 8 6 Falso Falso Verdadeiro Verdadeiro
7 12 8 5 Falso Verdadeiro Verdadeiro Verdadeiro
6 12 8 5 Falso Verdadeiro Verdadeiro Verdadeiro
7 12 8 4 Falso Falso Falso Falso
8 12 8 4 Falso Falso Falso Falso
2003/2004Introdução à Programação29
Diagrama de actividade
passo
[¬G]
[G]
Início da actividade
Entroncamento
Guarda
RamificaçãoTransição
Fim da actividade
Actividade
2003/2004Introdução à Programação30
Diagrama de actividade do mdc
[m ÷ k = 0 n ÷ k = 0]
[m ÷ k 0 n ÷ k 0]
k k - 1
k nk m
[m < n] [m n]
{mdc(m, n) < k}
{mdc(m, n) k}
{0 m 0 n}
{k = min(m, n)}
{mdc(m, n) k}
{k = mdc(m, n)}
2003/2004Introdução à Programação31
Linguagens
Linguagem natural Português Ambígua e imprecisa
Linguagem máquina Muito básica: usada pelos computadores
Linguagem de programação de alto nível Sem ambiguidades nem imprecisões Não tão penosa como linguagem máquina
2003/2004Introdução à Programação32
Linguagem de programação C++
LinguagemC++
Compiladorde C++
Processador
Linguagemmáquina
2003/2004Introdução à Programação33
Programa mdc em C++
#include <iostream>
using namespace std;
int main() { cout << "Introduza dois inteiros positivos: "; int m, n; cin >> m >> n;
int k; if(m < n) k = m; else k = n;
while(m % k != 0 or n % k != 0) --k;
cout << "O máximo divisor comum de " << m << " e " << n << " é " << k << endl; }
2003/2004Introdução à Programação34
Fases da resolução de problemas
Especificação Humano
Desenvolvimento do algoritmo Humano
Concretização do algoritmo na linguagem de programação Humano
Tradução do programa para linguagem máquina Computador
Execução do programa (e.g., mdc(131, 47)) Computador
2003/2004Introdução à Programação35
A reter...
Programar Resolver problemas
Algoritmo Receita finita, definida, com entradas, com saídas e eficaz
Correcção de algoritmo Não se demonstra por testes
Tipos de linguagens Naturais, de programação de alto nível, máquina, etc.
Programa Concretização numa linguagem de programação
Compilador Traduz programa de linguagem de programação para
linguagem máquina
2003/2004Introdução à Programação36
Aula 1: Sumário
Computador como máquina programável Programação: arte de resolver problemas Conceito de algoritmo Conceitos de linguagens naturais, de
programação e máquina Programa: concretização dum algoritmo Fases da resolução dum problema usando um
computador
Recommended