Upload
david-duarte
View
222
Download
0
Embed Size (px)
Citation preview
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
1/115
1
AlgoritmosCET
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
2/115
2
OBJECTIVOS DA CADEIRA
Fornecer aos alunos os conhecimentos bsicos de algoritmia,
capacitando-os para o desenho e documentao dos algoritmos de
suporte a programas informticos e/ou procedimentos genricos
que venham a ser necessrios. Adicionalmente os alunos ficaro
capacitados com conhecimentos gerais de programao
conducentes implementao de algoritmos simples recorrendo
linguagem de programao
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
3/115
3
PROGRAMA DA CADEIRA Conceitos bsicos
Problemas computacionais e consequente organizao de umcomputador e necessidades de processamento de dados. Anlise do problema. Tcnicas de programao.
Tipos de dados. Algoritmos.
Conceitos avanados
Desenvolvimento de um algoritmo. Estruturas de repetio, seleco simples e mltipla. Estruturas de dados pilhas, listas de espera, listas de
prioridade, rvores.
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
4/115
4
PROGRAMA DA CADEIRA Ferramentas de desenho
Fluxogramas. Diagramas de Fluxo de Dados.
Algoritmos elementares
Manipulaes de dados inseres, remoes e buscas. Algoritmos de ordenao quicksort, shellsort, bubblesort e
heapsort. Manipulao de strings algoritmos Knuth-Morris-Pratt e Boyer-
Moore. Manipulao de matrizes mono, bi e multi-dimensionais.
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
5/115
5
PROGRAMA DA CADEIRA Programao
Estruturao de um programa. Programao por eventos. O ambiente de desenvolvimento Visual Studio. A linguagem de programao C#.
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
6/115
6
BIBLIOGRAFIA
Baase, S. & Gelder, A. V. Computer Algorithms Introduction toDesign & Analysis. Addison-Wesley
Neto, J. P. (2004). Programao, Algoritmos e Estrturas deDados. Lisboa: Escolar Editora
Salvetti, D. D. & Barbosa, L. M. Algoritmos. Makron Books
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
7/115
7
SISTEMAS DE INFORMAOSistema de Informao um sistema que rene, guarda, processa e
faculta informao relevante para a organizao (...), de modo que ainformao acessvel e til para aqueles que a querem utilizar, inclundo
gestores, funcionrios, clientes, (...). Um Sistema de Informao um
sistema de actividade humana (social) que pode envolver ou no, a
utilizao de computadores.
[Buckingham, et al. 1978]
Sistema de Informao uma combinao de procedimentos,
informao, pessoas e Tecnologias de Informao, organizadas
para o alcance de objectivos de uma organizao.
[Alter 1992]
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
8/115
8
TI-TECNOLOGIAS DE INFORMAOTecnologias de Informao, so o conjunto de equipamentos e suportes
lgicos (hardware e software) que permitem executar tarefas comoaquisio, transmisso, armazenamento, recuperao e exposio de
dados.
[Alter 1992]Exemplos de T I
Hardware Software de sistema
Software aplicacional Comunicaes Ferramentas de desenvolvimento
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
9/115
9
DADOS VS. INFORMAODados, so elementos primitivos, com os quais e atravs de algum
tipo de processamento, se obtm a informao.
PROCESSAMENTO INFORMAODADOS
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
10/115
10
GESTO DO SISTEMA DE INFORMAO
GESTO DA
INFORMAO
INFORMAO
DADOS
OUTROS
RECURSOS
T I
GESTO DO SISTEMA DE INFORMAO
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
11/115
11
GESTO DO SISTEMA DE INFORMAO
Gesto de Sistemas de Informao a gesto do recurso informao e de todosos recursos envolvidos no planeamento , desenvolvimento, explorao e
manuteno do SI.
[Amaral, Varajo 2000]
Investir em TI no significa investir nos Sistemas de Informao
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
12/115
12
EXERCCIO: GESTO DE STOCKSContexto
Empresa que no pretende adquirir computadores tem a finalidade de automatizar enormalizar a gesto do armazm. Todos os procedimentos tm de ser executados
manualmente no recorrendo a quaisquer meios informticos.
Perguntas a responder
Como controlar os stocks existentes na empresa?
Como controlar as entradas e saidas dirias?
Como controlar as encomendas a efectuar?
Como controlar os monos (produtos sem movimento mais de 90 dias)?
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
13/115
13
ALGORITMOSAlgoritmo uma sequncia ordenada e finita de operaes bem definidas,
que partido de informao fornecida previamente, produz, num tempo finito,um resultado que a soluo de um determinado problema, ou em
alternativa a indicao de que a soluo no pode ser obtida.
Caracteristicas Principais [Horowitz e Sahni 82]:
Limitao Definio Entradas Sadas Eficincia
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
14/115
14
FORMAS DE
REPRESENTAO
Vantagens De universal entendimento
Desvantagens Pode gerar Ambiguidades
Exemplo:Mquina de calcular simples para a
execuo das operaes de x, :, + e
Verificar se a mquina est ligada,seno ligar
Limpar memria do visor Recolher 1 operando Recolher operao
Recolher 2 operando Efectuar clculo Apresentar Resultado
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
15/115
15
FORMAS DE
REPRESENTAO Vantagens Visual e Simples
Desvantagens Inadequado para
problemas complexos
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
16/115
16
FORMAS DE
REPRESENTAO
Primitivas:
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo SN
Incio de fluxograma
Estado com espera
Estado sem espera
Deciso
Aco
Aco
Condio
Fluxo
Fim de fluxograma
n Elemento de ligao
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
17/115
17
FORMAS DE
REPRESENTAO
Exemplo:
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
Recolher 1 Operando
Recolher Operao
Recolher 2 Operando
Efectuar Clculo
Apres. Resultado
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
18/115
EXERCCIO: Mquina de calcular Pretende-se desenvolver um programa para a realizao de operaes aritmticas.
Recolha 1 Operando
Recolha 2 OperandoRecolha de Operador
Operador
tem 2
Operando
Efectuar
calculo
Apresentar
resultado
Deseja
sair
N
N
S
S
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
19/115
19
Exerccio: Multiplicao Recolhe dois valores do utilizador e
efectua a sua multiplicao recorrendoapenas operao de soma.
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
20/115
20
Exerccio: Multiplicao Multiplicao usando apenas somas
Recolha X
X > 0
R=0
Apresentar RN
Recolha Y
X = X - 1S
R = R + Y
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
21/115
21
Exerccio: Multiplicao Troca do maior pelo menor (reduzindo o nmero de ciclos a efectuar)
Recolha X Recolha Y
R=0
X > 0 Apresentar RN
X = X - 1S
R = R + Y
X > YAux=XX=Y
Y=Aux
S
N
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
22/115
EXERCCIO: Factorial Pretende-se desenvolver um programa que dado um determinado nmero
clcule o seu factorial F = N! = N x (N-1) x (N-2) x x (N-(N-1))
O factorial de um nmero obtido pela sucessiva multiplicao do nmeropor ele prprio diminuido de uma unidade, at atingir a unidade.
definio corrente matemtica que um factorial s pode ser clculadopara nmeros inteiros positivos, o que no sendo explicito no enunciadocondiciona o nosso algoritmo a nvel da validao dos dados.
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
23/115
EXERCCIO: Factorial F = N! = N x (N-1) x (N-2) x x (N-(N-1))
Recolha X
X 1
msg erro
R = 1 R = R * X
X = X - 1
Apresentar R
N
S
S
N
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
24/115
24
EXERCCIO: Signos Pretende-se dada uma certa data de
nascimento indicar o signo correspondente. Nocontexto deste problema consideraremos queexistem 12 signos num ano, sendo o primeiro
entre 15 de Janeiro e 14 de Fevereiro, osegundo entre 15 de Fevereiro e 14 de Maro,, o dcimo primeiro entre 15 de Novembro e
14 de Dezembro e o dcimo segundo entre 15de Dezembro e 14 de Janeiro.
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
25/115
25
EXERCCIO: Signos
Recolher ano 1
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
26/115
26
EXERCCIO: Signos
D>=15 S
1
N
Signo M-1=0SN
Signo 12Signo M-1 Signo M
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
27/115
27
FORMAS DE
REPRESENTAO Vantagens Visual e simples, pelo quefacilita o entendimento global do
algoritmo
Facilita a representao do
encapsulamento e da recursividade
em relao ao fluxograma
Desvantagens Inadequado para
problemas complexos
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
28/115
28
FORMAS DE
REPRESENTAO
Primitivas (mais comuns):
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
Processo
Deciso
Iterao
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
29/115
29
FORMAS DE
REPRESENTAO
Primitivas (mais comuns):
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
Deciso Mltipla
Iterao
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
30/115
30
FORMAS DE
REPRESENTAO
Exemplo:
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
Recolher 1 Operando
Recolher Operao
Recolher 2 Operando
Efectuar Clculo
Apresentar Resultado
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
31/115
EXERCCIO: Linguagem natural Clculo do zero da equao ax+b=0
Incio de programa Ler a, b Se a diferente de 0 ento
calcula o valor de x (ax+b=0 x=-b/a) imprimir valor de x
Se no imprimir No h zero Fim de programa
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
32/115
EXERCCIO: Fluxograma Clculo do zero da equao ax+b=0
Ler a
a 0No h 0N S
Ler b
x=-b/a
Mostra x
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
33/115
EXERCCIO: Pseudo-cdigo Clculo do zero da equao ax+b=0
1. Incio de programa2. ler a, b3. se a0 ento
x=-b/aimprimir valor do zero x
senoimprimir No h zero
fim de se
4. Fim de programa
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
34/115
34
FORMAS DE
REPRESENTAO Vantagens Permite a representao deum algoritmo, tanto ao seu nvel mais
abstracto ou ao seu nvel mais
especfico.
Simplicidade, Legibilidade e Exactido.
Desvantagens Pode esconder os
problemas de eficincia face a
linguagem de mais baixo nvel.
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
35/115
35
FORMAS DE
REPRESENTAO
Primitivas:
STARTIdentificao do ponto inicial do algoritmo
END
Identificao do ponto final do algoritmo
INPUT Primitiva para recolha de dados do utilizador
OUTPUT Primitiva para apresentao de dados ao
utilizador
SET = Atribuio do resultado da expresso varivel
indicada
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
36/115
36
FORMAS DE
REPRESENTAO
Primitivas (continuao):
IF THEN
ELSE
END IF
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo ?N S
?SN
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
37/115
37
FORMAS DE
REPRESENTAO
Primitivas (continuao):
WHILE
END WHILE1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo?
S
N?
S
N
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
38/115
38
FORMAS DE
REPRESENTAO
Primitivas (continuao):
DO
WHILE 1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo
?
N
S
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
39/115
39
FORMAS DE
REPRESENTAO
Primitivas (continuao):
FOR TO [STEP
END FOR
1. Linguagem Natural
2. Fluxograma3. Diagrama de Chapin
4. Pseudo-Cdigo?
S
N
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
40/115
40
FORMAS DE
REPRESENTAO
Primitivas (continuao):FUNCTION (parmetros da
funo)
END FUNCTION
CALL (parmetros dafuno)
VAR [,]
CONST [,]
STRUCT [,]
[ ]END STRUCT
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
V i i
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
41/115
41
FORMAS DE
REPRESENTAO
Variveis:INTEGER
inteiroDECIMAL(n,m)
decimal com n dgitos dos quais m direita da virgula, por exemploDECIMAL(4,1) poder representarnmeros do tipo com valores entre 999,9 e +999,9
DATEdata com qualquer formato, por exemployyyy-MM-dd
TIME hora com qualquer formato, por exemplohh:mm:ss
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
V i i
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
42/115
42
FORMAS DE
REPRESENTAO
Variveis (continuao):STRING(n)
cadeia de caractres com comprimento nmaior que 0, um caso particular ser oSTRING(1)
CHARletra, correspondente a STRING(1)
LONG STRINGcadeia de caractres sem comprimentodefinido
BOOLEANdado s com duas ocorrncias,
verdadeiro (TRUE) e falso (FALSE)POINTER
tipo especial de varivel que utilizadopara apontar para outras variveis,tipicamente utilizado nas listas e rvores
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
Exemplo: Mquina de calcular
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
43/115
43
FORMAS DE
REPRESENTAO
Exemplo: Mquina de calcularSTART
DECIMAL(10,2) Op1DECIMAL(10,2) Op2Char OperDECIMAL(10,2) R
OUTPUT Introduza o 1 operandoINPUT Op1
OUTPUT Introduza o operadorINPUT Oper
IF Oper necessita 2 operador THENOUTPUT Introduza o 2 operandoINPUT Op2
END IF
CALL EfectuarCalculo (Op1, Oper, Op2, R)OUTPUT O RES. da operao :, R
END
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
Exerccio: Factorial (WHILE)
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
44/115
44
FORMAS DE
REPRESENTAO
Exerccio: Factorial (WHILE)START
DECIMAL(10,0) XINT R
OUTPUT Introduza o valor de N!INPUT X
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
IF X=1R=R*XX=X-1
END WHILE
OUTPUT O factorial + REND IF
END
Exerccio: Factorial (DO)
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
45/115
45
FORMAS DE
REPRESENTAO
Exerccio: Factorial (DO)START
DECIMAL(10,0) XINT R
OUTPUT Introduza o valor de N!
INPUT X
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
IF X1
OUTPUT O facturial , REND IF
END
Exerccio: Factorial (FOR)
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
46/115
46
FORMAS DE
REPRESENTAO
Exerccio: Factorial (FOR)START
DECIMAL(10,0) XINT R
OUTPUT Introduza o valor de N!
INPUT X
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
IF X
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
47/115
OUTRAS NOTAESfor i := 1,...., n dofor j := 1,...., n do
cij := 0for k := 1,...., n docij := cij + aik
bkjSzwarcfiter e Markenzon ( [SM94] )
for i 1 at n dofor j 1 at n do
cij
0for k 1 at n docij cij + aik
bkjTerada ( [Ter91] )
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
48/115
OUTRAS NOTAESfor i 1 to n by 1 dofor j 1 to n by 1 do
c(i,j) 0for k 1 to n by 1 doc(i,j) c(i,j) + a(i,k)
b(k,j)Horowitz e Sahni ( [HS82] )
1 set i 12 set j 1set c[i,j] 03 set k 1
c[i,j]
c[i,j] + a[i,k]
b[if k
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
49/115
49
EXERCCIOS ESTRUTURAS DE REPETIO
< WHILE >TAMANHO RELATIVO DE DOIS NMEROS
Para dois nmeros inteiros positivos, determinar quantas vezes o
primeiro divide exactamente o segundo. Se o primeiro no divide o
segundo, ento o nmero de vezes zero.
Implementar um algoritmo para a resoluo do problema apresentado,
atravs de um fluxograma e em pseudo-cdigo.
EXERCCIOS ESTRUTURAS DE REPETIO
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
50/115
50
EXERCCIOS ESTRUTURAS DE REPETIO
< DO >MXIMO DE UM CONJUNTO DE N ELEMENTOS
Elabore um algoritmo que determine o valor mximo de um conjunto
de N nmeros inteiros positivos introduzidos pelo utilizador. O conjunto
de valores terminado com o valor zero.Implementar um algoritmo para a resoluo do problema apresentado,
atravs de um fluxograma e em pseudo-cdigo.
EXERCCIOS ESTRUTURAS DE REPETIO
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
51/115
51
EXERCCIOS ESTRUTURAS DE REPETIO
< FOR >SEQUNCIA DE FIBONACCI
Partindo-se de um nico casal de coelhos recm-nascidos e supondo
que um casal se torna frtil aps dois meses de vida e, a partir de
ento, produz um novo casal a cada ms e que os coelhos nuncamorrem , a quantidade de casal de coelhos aps n meses dada pelo
n-simo termo da sequncia abaixo.
Esta sequncia caracteriza-se pela seguinte formula recorrente:
F[k] = F[k-2] + F[K-1], com F[0] = 1 e F[1] = 1
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
52/115
EXERCCIO: MQUINA DE BILHETESPretende-se desenvolver um algoritmo que faculte a venda automtica
de bilhetes de comboio com base nas definies apresentadas de
seguida. Apresentar o respectivo fluxograma e pseudo-cdigo.
S existem quatro destinos e o preo dos bilhetes de X; 1.5X;2.4X e 4X respectivamente. O valor X definido a 1 de Janeiro
de cada ano sendo fixo ao longo de todo o ano; possvel a venda de bilhetes para crianas sendo neste caso o
valor reduzido a metade;
Por opo o utente pode adquirir bilhetes de ida e volta; A mquina dever dar trocos em Euros mediante a entrega de
notas de 50 , 20 , 10 , e 5 e moedas de 2 , 1, 50 c, 20 c,10 c e 5 c. Os trocos inferiores a 5 c. no so entregues.
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
53/115
ARRAYS
ARRAY Tabela unidimensional, que permite guardar um conjunto devariveis todas com mesmo tipo e aceder a cada uma delas
atravs de um index.
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
54/115
ARRAYSEx: Representar numa tabela de tamanho n o conjunto de valores
T {3,12.5, 10, 4, 3}
Ou seja:
T[0] = 3 T[4] = 3T[1] = 12.5 ...T[2] = 10 T[n-2] = 0T[3] = 4.2 T[n-1] = 0
312.5
10 4.2 3 0 0 0
0 1 2 3 n-1n-24 ... Inde x
array
1 elemento ltimoelemento
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
55/115
EXERCCIO: MQUINA DE BILHETESOptimizao: Utilizar um Array com as vrias notas/moedas que a
mquina comporta de forma a optimizar o algoritmo
desenhado
Ou seja uma varivel array M[k] de tamanho 10, onde kvaria de 0 a 9
M[0] 50
M[1] 20
M[2] 10
M[3] 5
M[4] 2
M[5] 1
M[6] 50 c
M[7] 20 c
M[8] 10 c
M[9] 5 c
EXERCCIOGrandezas Descrio
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
56/115
56
EXERCCIOMQUINA DE BILHETES
OPTIMIZADA
BOAS PRTICAS Lista de Grandezas
Constantes e Variveis
X Valor base do bilhete
PB Preo do bilheteD Destino
TP Tipo do bilhete
TV Tipo da Viagem
T Troco
M[]Array com notas/moedas utilizadasno troco
k ndice utilizado no array M[]
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
57/115
CONSTANTES E LITERAISConstante Grandeza que se mantm invarivel durante a exec. de
um algoritmo (programa).
e.g.:
So constantes, no Algoritmo da mquina de venda de bilhetes, X eM[].
Em C# se quisermos definir uma constante para o valor de Pi,fazemos,
Const double PI = 3.1415926535
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
58/115
VARIVEISVariveis Grandezas que variam ao longo da execuo do algoritmo
(programa)
e.g.:So variveis, no Algoritmo da mquina de venda de bilhetes, PB, T,
D, etc.
Em C#,int i = 0while ( i
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
59/115
LITERAISLiteral Designamos por literal um valor, quando este atribudo a
uma varivel
e.g.:
int x = 15
int k = 0x0fstring saudacao = Bom dia
Em C# os valores literais podem ser indicados em base decimal ouhexadecimal
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
60/115
TIPOS SIMPLES DE DADOS
Tipo Valores Permitidos no intervalo [a, b]sbyte Inteiros entre -128 e 127
byte Inteiros entre 0 e 255
short Inteiros entre -32768 e 32767
ushort Inteiros entre 0 e 65535
int Inteiros entre -2147483648 e 2147483647
uint Inteiros entre 0 e 4294967295
long Inteiros entre -9223372036854775808 e 9223372036854775807ulong Inteiros entre 0 e 18446744073709551615
Tipos Numricos
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
61/115
TIPOS SIMPLES DE DADOSTipo Min m Mx m Min e Mx e Val Min aprox. Val Mn aprox.
float 0 224 -149 104 1.5x10 -45 3.4x10 -38
double 0 253 -1075 970 5.0x10 -324 1.7x10 308
decimal 0 296 -26 0 1.0x10 -28 7.9x10 28
Nota: Com float e double armazenados na forma m x 2e e decimal armazenado na
forma m x 10e
Outros Tipos Simples
Tipo Valores Permitidos
char Carcter nico em Unicode, arm como inteiro entre 0 e 65535bool Valor Boleano, Verdadeiro (True) ou Falso (False)
string Uma sequncia de caracteres
EXERCCIO
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
62/115
62
MQUINA DE
BILHETES STARTVAR DECIMAL(10,2) PB
CALL RecolhaDados()
CALL CalculaValor()
OUTPUTO preo do bilhete : , PB
CALL RecolhaPagamento()
CALL CalculaTroco()
CALL EntregaBilhete()END
PSEUDO-CDIGO Abordagem Macro
Tratamento Tipo Destino Tratamento Tipo Bilhete Tratamento Tipo Viagem Tratamento do Troco
EXERCCIO A
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
63/115
63
EXERCCIO: Arrays
Elabora um algoritmo que imprima todos
os valores de um array. Elabora um algoritmo que some todos os
elementos de um array unidimencional. Elabora um algoritmo que some todos os
elementos de um array bidimencional.
Dado um determinado array, encontra ondice do maior e do menor valor.
EXERCCIO Ordenao
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
64/115
64
EXERCCIO: Ordenao
Elabora um algoritmo que ordene os
valores de um array.
ALGORITMOd
Quicksort Mtodo de ordenao muito rpido e eficiente
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
65/115
65
de
ORDENAO
Mtodo de ordenao muito rpido e eficiente
Possui uma complexidade ptima O(n.log(n)) para ocaso mdia ao invs de O(n2) Inventado por C.A.R. Hoare em 1960. Foi publicado em 1962 aps uma srie de
alteraes.
Funcionamento: Divide a tarefa de ordenar o vector em dois problemas de
ordenao menores; Os problemas menores so ordenados de forma
independente; E os resultados so combinados para produzir a soluo
do problema todo; Os dois arrays so processados de modo a distribuir os
menores valores para um array e os maiores para ooutro.
Quick sort Bubble sort
Merge sort Selection sort Heapsort Insertion sort
Shell sort Radix sort Gnome sort Count sort
Bogosort Bucket sort Cocktail sort
ALGORITMOd
Quicksort Array a ordenar:
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
66/115
66
de
ORDENAO
Array a ordenar:
Coloca-se os menores valores na metade esquerdae os maiores na metade direita;
Divide-se o array em dois para serem ordenados;
Aps a ordenao de ambas as metades;
No final voltam-se a unir de modo a compor aresposta ao problema inicial.
Quick sort Bubble sort
Merge sort Selection sort Heapsort Insertion sort
Shell sort Radix sort Gnome sort Count sort
Bogosort Bucket sort Cocktail sort
0824157693
9856701423
9876543210
01423
43210 98765
98567
ALGORITMOde
Quicksort Como se separam os menores valores para a
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
67/115
67
de
ORDENAO
Como se separam os menores valores para a
esquerda e os maiores para a direita?
escolhido um valor aleatrio, Pivot, normalmentea meio do array;
Valores menores que o Pivot sero colocados
esquerda, enquanto que valores maiores serocolocados direita; Ini e Fim apontam respectivamente para o incio e
para o fim do array; Ini e Fim avanam em direco do Pivot;
Cada par de valores nas metades incorrectas serotrocados.
Quick sort Bubble sort
Merge sort Selection sort Heapsort Insertion sort
Shell sort Radix sort Gnome sort Count sort
Bogosort Bucket sort Cocktail sort
0824157693
Pivot FimIni
ALGORITMOde
Quicksort Ini avana para a direita at encontrar um elemento
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
68/115
68
de
ORDENAO
Ini avana para a direita at encontrar um elemento
maior que Pivot; Fim avana para a esquerda at encontrar um valormenor que Pivot;
Neste momento d-se a troca dos valores;
Quick sort Bubble sort
Merge sort Selection sort Heapsort Insertion sort
Shell sort Radix sort Gnome sort Count sort
Bogosort Bucket sort Cocktail sort
0824157693
Pivot FimIni
9824157603
Pivot FimIni
9824157603
Pivot FimIni
9864157203
ALGORITMOde
Quicksort
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
69/115
69
de
ORDENAO
Quick sort Bubble sort
Merge sort Selection sort Heapsort Insertion sort
Shell sort Radix sort Gnome sort Count sort
Bogosort Bucket sort Cocktail sort
9864157203
9867154203
9867154203
9867514203
FimIni
FimIni
FimIni
FimIni
ALGORITMOde
Quicksort
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
70/115
70
de
ORDENAO
Quando o valor de Fim menor que o valor de Ini o
processo de separao termina e inicia-se aresoluo dos subproblemas;
Quick sort Bubble sort
Merge sort Selection sort Heapsort Insertion sort
Shell sort Radix sort Gnome sort Count sort
Bogosort Bucket sort Cocktail sort
9827514603
IniFim
ALGORITMOde
Quicksort - C#
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
71/115
71
de
ORDENAOclassQuicksort
{
private static void swap(int[] Array, intIni, intFim)
{
inttemp = Array[Ini];
Array[Ini] = Array[Fim];
Array[Fim] = temp;
}
Quick sort Bubble sort
Merge sort Selection sort Heapsort Insertion sort
Shell sort Radix sort Gnome sort Count sort
Bogosort Bucket sort Cocktail sort
ALGORITMOde
Quicksort - C#
bli t ti id t (i t[] A i t I i i t Fi ) {
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
72/115
72
de
ORDENAOpublic static voidsort (int[] Array, intIni, intFim) {
intLHold = Ini;
intRHold = Fim;
RandomObjRan = newRandom();
intPivot = ObjRan.Next(Ini, Fim);
swap(Array, Pivot, Ini);
Pivot = Ini;
Ini = Ini + 1;
while(Fim >= Ini) {
if(Array[Ini] >= Array[Pivot] && Array[Fim] < Array[Pivot])
swap(Array, Ini, Fim);
else if(Array[Ini] >= Array[Pivot])
Fim = Fim - 1;
else if(Array[Fim] < Array[Pivot])Ini = Ini + 1;
else{
Fim = Fim - 1;
Ini = Ini + 1;
}
}swap(Array, Pivot, Fim);
Pivot = Fim;
if(Pivot > LHold) sort(Array, LHold, Pivot);
if(RHold > Pivot + 1) sort(Array, Pivot + 1, RHold);
}
}
Quick sort Bubble sort
Merge sort Selection sort Heapsort Insertion sort
Shell sort Radix sort Gnome sort Count sort
Bogosort Bucket sort Cocktail sort
EXERCCIO: Algoritmo de Procura
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
73/115
73
EXERCCIO: Algoritmo de Procura
Dado uma determinada palavra e um
dado texto, determina se a referidapalavra aparece em algum lugar no texto.
EXERCCIOALGORITMO DE
Fora Bruta Consiste em comparar a Palavra com o
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
74/115
74
GO O
PROCURA
Consiste em comparar a Palavra com o
Texto, no sentido da esquerda-direita,comparando caracter a caracter.
Os ndices p e t correm respectivamente aPalavra e o Texto partindo da posio 0.
Quando houver coincidncia numa letra oslavores de p e t so incrementados.
A Palavra deslocada 1 posio em relaoao Texto sempre que Palavra[p]Texto[t],sendo p=0 e t=t+1.
Fora Bruta Exemplificao
O pior caso Cdigo C# (1) Cdigo C# (2)
EXERCCIOALGORITMO DE
Exemplificao Texto = O nosso texto!
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
75/115
75
PROCURA
Fora Bruta Exemplificao
O pior caso Cdigo C# (1) Cdigo C# (2)
e to O osso te to
Palavra = osso
!
4
4osso
3o
2o
1soPotxetossonOT
3210987654321
EXERCCIOALGORITMO DE
O pior caso Se a Palavra no existe no Texto, para cada
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
76/115
76
PROCURA
Fora Bruta Exemplificao
O pior caso Cdigo C# (1) Cdigo C# (2)
, p
valor de t entre 0 e TamT-TamP+1 soefectuadas, no mximo, TamP+1comparaes.
35
75baaa
65baaa
55baaa45baaa
35baaa
25baaa
15baaaPaaaaaaaaaaT
0987654321
TamT-TamP+1 = 10-4+1 = 7 ciclos
(TamP+1)(TamT-TamP+1) = 5*7 = 35 comparaes
Para valores elevados de TamP e TamT a FB torna-se
invivel
EXERCCIOALGORITMO DE
intt, p;
string[] Texto;
Texto = new string[14] { "O" " " "n" "o" "s" "s" "o" " " "t" "e" "x" "t" "o"
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
77/115
77
PROCURATexto = new string[14] { O , , n , o , s , s , o , , t , e , x , t , o ,
"!"};
string[] Palavra = new string[4] { "o", "s", "s", "o"};
t = 0;
p = 0;
while(t < Texto.Length) {
while(p < Palavra.Length) {Console.Write(" "+ Palavra[p] + " - " + Texto[t + p] + "\n");
if(Palavra[p]==Texto[t+p]) {
p += 1;
if(p == Palavra.Length) {Console.Write("Palavra encontrada no Texto!");
t = Texto.Length;// Para sair do while
}
} else{ p = Palavra.Length;// Para sair do while}
}p = 0;
t += 1;
Console.Write("\n\n");
}
Fora Bruta Exemplificao
O pior caso Cdigo C# (1) Cdigo C# (2)
EXERCCIOALGORITMO DE
intt, p;
string[] Texto;
Texto = new string[14] { "O" " " "n" "o" "s" "s" "o" " " "t" "e" "x" "t" "o"
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
78/115
78
PROCURATexto = new string[14] { O , , n , o , s , s , o , , t , e , x , t , o ,
"!"};string[] Palavra = new string[4] { "o", "s", "s", "o"};
for(t=0; t != Texto.Length; t++) {
p = 0;
while(t + p != Texto.Length &&p != Palavra.Length &&
Texto[t + p] == Palavra[p]) {
p = p + 1;
if(p == Palavra.Length) {
Console.Write("\nEncontrou uma combinao");}
}
}
Fora Bruta Exemplificao
O pior caso Cdigo C# (1) Cdigo C# (2)
MTODOKnut-Morris-Pratt
Mtodo Knut-Morris-Pratt (KMP) Mtodo apresentado em 1970, acelera a
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
79/115
79
procura de cadeias porque, para cadadiscrepncia de caracteres entre a Palavra eo Texto, efectua deslocamentos sempre demais de um caracter. O deslocamentodepender de Palavra.
No algoritmo KMP, aps cada discrepncia, ociclo comea na posio mais favorvel daPalavra, mantendo-se o Texto na mesmaposio ou na seguinte. t nunca retrocede.
A reinicializao do ndice p depende apenasde Palavra, pois depende se existe umarepetio de uma sub-Palavra na prpriaPalavra.
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
MTODOKnut-Morris-Pratt
Estratgia1. Pr-compila a Palavra, isto , calcular uma
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
80/115
80
tabela D de nmeros associados sposies dos caracteres da Palavra. Cadanmero proporciona a localizao do ndiceda Palavra no prximo ciclo.
2. Efectua ciclos no Texto sequencialmenteenquanto houver coincidncias com aPalavra, e na ocorrncia de umadiscrepncia utiliza a tabela construda napr-compilao.
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
MTODOKnut-Morris-Pratt
Pr-compilao Exemplo 1
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
81/115
81
Ini e Fim representam respectivamente assub-Palavras no incio e no fim de Palavra.
Ini e Fim possuem o mesmo tamanho comtodos os caracteres correspondentes iguais.
Coin representa a subcadeia de coincidnciasno Texto.
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
PalavraIni Fim
...Texto
Coin
MTODOKnut-Morris-Pratt
Pr-compilao Primeira discrepncia: Palavra[p]Texto[t]
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
82/115
82
A sub-PalavraIni coincide com a sub-PalavraFim, excepto na posio p: Ini[a]Fim[p]
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
Palavra
0 a p
Ini Fim
...TextotCoin
MTODOKnut-Morris-Pratt
Pr-compilao A Palavra deve ser deslocada em relao ao
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
83/115
83
Texto de modo que Ini passe a ocupar aposio anterior de Fim. Pode-se justificar istocom a possibilidade de Palavra[a] poder serigual a Texto[t].
Para o prximo ciclo, o ndice t mantm omesmo valor e o ndice p o valor de a. Natabela D dever existir o valor de a associado
posio de p em Palavra.
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5
Palavra
0 a p
Ini Fim...Texto
t
0 p=a p
PalavraIni Fim
...Textot
MTODOKnut-Morris-Pratt
Pr-compilao Exemplo 2
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
84/115
84
Este exemplo mostra como ser feito odeslocao quando Ini no ocorre em Texto.
Este tambm o caso onde Ini e Fimcoincidem completamente (Ini=Fim=Palavra).
Palavra dever ser deslocado em ralao aoTexto para a primeira posio direitadaquela onde ocorreu a primeira discrepncia,reiniciando as comparaes a partir do
primeiro caracter da Palavra.
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
MTODOKnut-Morris-Pratt
Pr-compilao Primeira discrepncia: Palavra[p]Texto[t]
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
85/115
85
No existe Ini nem Fim
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
Palavra
0 p
Textot
cbxxgfeddcbx
c dbxxgfeddbx
MTODOKnut-Morris-Pratt
Pr-compilao O ndice t avana para t+1 e o ndice p
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
86/115
86
recomea na posio 0. D dever ter o valor 1 associado posio p
de Palavra. Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
Palavra0 p
Textot+1
cbxxgfeddcbx
d c bxxgfeddbx
MTODOKnut-Morris-Pratt
Pr-compilao Para cada caracter de Palavra est associado
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
87/115
87
um nmero que d a posio do ndice paraPalavra depois de cada discrepncia.
D ser a tabela associada a Palavra. Ocalculo dos valores de D tem o nome de Pr-
compilao.
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
Tabela D
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
88/115
88
Pr-compilao Para mostrar que a deslocao depende de Palavra vamos supor que a primeira
discrepncia acontece emPalavra[4].
Palavra[4] sempre diferente do ltimo caracter de Ini. Cada linha da tabela mostra adeslocao de Palavra de modo que Ini coincida com a posio anterior de Fim.
P[0]=P[1]=P[2]=P[3] e P[3]P[4] Sempre que Palavra[4] igual ao ultimo caracter de Ini, no faz sentido deslocar a
Palavra para a posio indicada em D, porque certamente a discrepncia ser mantida. Nestes casos Palavra deve ser deslocado para t+1 e p=0. Ini e Fim no ocorrem ou tm tamanho 0.
00P[4]P[3]P[2]P[1]P[0]
11P[4]P[3]P[2]P[1]P[0]
22P[4]P[3]P[2]P[1]P[0]
33P[4]P[3]P[2]P[1]P[0]D[4]TamP[4]P[3]P[2]P[1]P[0]
MTODOKnut-Morris-Pratt
Pr-compilao Exemplo 3
I i Fi
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
89/115
89
Ini e Fim de tamanho 2 (posio 0 e 1)
Texto = NESTE MOMENTO IDILICO
Palavra = IDILIO
O ciclo anterior comea com p=0 e t=14 etermina em p=5 e t=19 quandoPalavra[5]Texto[19].
O prximo ciclo recomea com p=1 e t=19.
Palavra desloca-se 4 posies. t mantm-se e p de Palavra posiciona-se em 1
(tamanho de Ini e Fim)
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
t=19
???OCILIDITexto
OILIDIPalavra (deslocao)
OILIDIPalavra
543210
p
MTODOKnut-Morris-Pratt
Pr-compilao Exemplo 4
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
90/115
90
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
11111110D[p]
UTACUTOBPalavra[p]
76543210p
MTODOKnut-Morris-Pratt
Pr-compilao Exemplo 5
76543210
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
91/115
91
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
30001110D[p]
ECBADCBAPalavra[p]
76543210p
MTODOKnut-Morris-Pratt
Desenvolvimento do Algoritmo D associa a cada posio de Palavra um valor
numrico que indica a nova posio do ndice p i i di i
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
92/115
92
numrico que indica a nova posio do ndice paps a primeira discrepncia.
d[0]=0;
i=1;
While(i
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
93/115
93
Objectivo: determinar o valor inicial do ndice p dePalavra para a prxima comparao aps ocorrerPalavra[p]Texto[t].
Entrada: Palavra (string), p (inteiro)
Sada: deslocamento (inteiro)function Deslocamento(Palavra, p){iniciob = 1;
deslocamento = 0;
do{
a = 0;b = iniciob;
while(Palavra[a]=Palavra[b] and bp)
}
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
MTODOKnut-Morris-Pratt
Desenvolvimento do Algoritmo Funo Precompilacao(m, Palavra, D)
Objectivo: construir a tabela de deslocamentos para
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
94/115
94
Objectivo: construir a tabela de deslocamentos paraPalavra.
Entrada: m (inteiro), Palavra (string)
Sada: D (array de inteiros)
function Precompilacao(Palavra, m){
D[0] = 0;
for (int p = 1; p < m; p++) {
D[p] = Deslocamento(Palavra, p);
}}
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
MTODOKnut-Morris-Pratt
Desenvolvimento do Algoritmo Algoritmo KMP
Objectivo: determinar o loca em Texto da primeira i d P l L l 0 P l
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
95/115
95
Objectivo: determinar o loca, em Texto, da primeiraocorrncia de Palavra. Local = 0 se a Palavra no ocorreno Texto.
Entrada: m e n (inteiro), Palavra e Texto (string)
Sada: local (inteiro)
Funes auxiliares: Deslocamento(Palavra, p) ePrecompilacao(m, Palavra, D)
function KMP(m, Palavra, n, Texto, local){
Precompilacao(m, Palavra, D);
int p = 0;int t = 0;
while(pm) {local = t-m;} else {local = 0;}
}
Mtodo KMP (Knut-Morris-Pratt) Estratgia
Pr-compilao Exemplo 1 Exemplo 2 Exemplo 3 Exemplo 4
Exemplo 5 Desenvolvimento do
Algoritmo
C# C# uma linguagem de programao
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
96/115
96
simples e orientada por objectos.
Visual C# proporciona ferramentas de
programao visual e suporte para odesenvolvimento de aplicaes
cliente/servidor e aplicaes web
atravs do Framework .NET (verso 2).http://www.microsoft.com/
http://msdn.microsoft.com/vstudio/express/
http://msdn2.microsoft.com/en-us/vcsharp/default.aspx
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
5. C#
C#Primitivas
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
97/115
97
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
5. C#
Int numero;String texto;Boolean verdadeiro_ou_falso;
VAR TIPO
Console.Write(Texto a escrever.);Funo do tipo VOID
Recebe como parmetro de entradavariveis como Int, String, DateTime,Boolean, etc.
OUTPUT
Console.Read();Funo do tipo INTConsole.ReadLine();
Funo do tipo STRING
INPUT
{ }Qualquer classe, funo, ciclo oucondio comea com { e terminam com}.
START - END
C#Primitivas
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
98/115
98
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
5. C#
do{
Console.Write(Valor: + numero);
numero = numero + 1;} while (numero < 10);
DO
WHILE
while (numero < 10){
Console.Write(Valor: + numero);
numero = numero + 1;
}
WHILE
END WHILE
if (numero == 1)Console.Write("Valor: " + numero);
else{
numero = numero + 1;Console.Write("Valor: " + numero);
}
IF THEN
ELSE
END IF
C#Primitivas
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
99/115
99
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
5. C#
for (int numero = 0; numero < 10; numero ++){
Console.Write(Valor: + numero);
}
FOR TO [STEP]
END FOR
C#Primitivas
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
100/115
100
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
5. C#
ola(mundo);CALL (parmetros)
static void ola(string texto){
Console.Write(Ol + texto);
}
FUNCTION (parmetros)
END FUNCTION
C#t i t t " l d "VAR ti
Variveis
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
101/115
101
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
5. C#
stringcharbool Boolean
byteDateTimeDecimalDoublefloatGuid
intInt16 shortInt32
Int64 long
const int numero = 0;const string texto = "Ol marte";CONST
string texto = "ol mundo";int num1 = 0, num2;num2 = 0;
VAR
C#Operador de soma ou de concatenao
Operadores
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
102/115
102
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
5. C#
Operadores aritmticos+, -, *, /
Operador e e ouif (num1 == 1 && num2 == 1)
Console.Write(Nmero 1 e nmero 2");
if (num1 == 1 || num2 == 1)Console.Write(Nmero 1 ou nmero 2");
&&, ||
Operadores de comparao==, >=,
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
103/115
103
1. Linguagem Natural
2. Fluxograma
3. Diagrama de Chapin
4. Pseudo-Cdigo
5. C#Boolean verdadeiro;verdadeiro = Convert.ToBoolean(1);
int numero;numero = Convert.ToInt16("16");
Converso para decimalToDecimal
Converso para inteiro (x = 16, 32, ou 64)ToIntX
Converso para true ou falseToBoolean
Converso para DateTimeToDateTime
Converso para stringToString
Converso para caracterToChar
Classe que permite converter variveis de umdeterminado tipo noutro
Convert
Ficha Prtica 1: C#
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
104/115
104
Cria um programa em C# que (cada alnea dever ser uma funo):1. Dados dois nmeros, escreva a sua mdia;2. Dados dois nmeros, identifique o maior;
3. Dado um nmero, escreva o seu valor absoluto;4. Dado um nmero, escreva o seu quadrado;5. Dado um nmero, indique se par ou impar;6. Dado um nmero, determine se menor, igual ou maior que zero;7. Dado um ano, determine se comum ou bissexto;8. Dados dois nmeros, escreva-os por ordem crescente;9. Dado trs nmeros, escreva-os por ordem crescente;10. Dados dois nmeros, indicar se o primeiro menor que 50 ou maior que
100, e ao mesmo tempo se o segundo for menor ou igual ao primeiro;11. Receber um tempo dado em horas, minutos e segundos e escrever o
total de segundos equivalentes;
12. Com base no ano de nascimento de algum, determinar a sua idadeactual;13. Criar um menu que represente todas estas funes.
Ficha Prtica 2: C#
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
105/115
105
Cria um programa em C# que permite obter os seguintes resultados(cada alnea dever ser uma funo):
1. Escrever todos os nmeros inteiros positivos de 1 a X. X dado peloutilizador;
2. Escrever todos os mpares inteiros positivos entre dois nmeros dadospelo utilizador;
3. Altera a funo 2 de modo a que o primeiro nmero no seja superior aosegundo;
4. Altera a funo 2 de modo a que caso o primeiro seja superior ao
segundo haja a troca de valores;5. Elabora uma funo que receba o valor de um limite positivo e umasequencia de nmeros inteiros positivos ou negativos at que o utilizadorescreva um zero ou at que o somatrio dos valores introduzidosultrapasse o limite fornecido;
6. Elabora uma funo que calcule o valor de 2e, sendo e fornecido pelo
utilizador;
Ficha Prtica 3: C#
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
106/115
106
Cria um programa em C# que (cada alnea dever ser uma funo):1. Factorial;2. Mquina de bilhetes;
3. Signos;
Funo RECURSIVA
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
107/115
107
Uma funo recursiva uma funo que se refere a siprpria.
A ideia consiste em utilizar a prpria funo queestamos a definir na sua definio.
Em todas as funes recursivas existe:
Um passo bsico (ou mais) cujo resultado imediatamenteconhecido. Um passo recursivo em que se tenta resolver um sub-problema
do problema inicial.
RECUSRIVIDADEAlgoritmo FactorialFuno no Recursiva
static int factorial(int n){
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
108/115
108
if (n 1);
return r;}
}
Algoritmo Factorial Funo no Recursiva Funo Recursiva
RECUSRIVIDADEAlgoritmo FactorialFuno Recursiva
O caso bsico o teste de igualdade a zero, onde oresultado imediato 1, e o passo recursivo :
(n * (factorial recursivo (n 1)))
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
109/115
109
(n (factorial_recursivo (n - 1))).
Uma funo recursiva dever possuir umaexpresso condicional.
A execuo de uma funo recursiva consiste em irresolvendo subproblemas sucessivamente maissimples at se atingir o caso mais simples de todos,cujo resultado imediato.
Desta forma, o padro mais comum para escreveruma funo recursiva :
Comear por testar os casos mais simples. Fazer chamada (ou chamadas) recursivas com
subproblemas cada vez mais prximos dos casos maissimples.
Dado este padro, os erros mais comuns
associados s funes recursivas so: No detectar os casos simples. A recursividade no diminuir a complexidade do
problema.
Algoritmo Factorial Funo no Recursiva Funo Recursiva
RECUSRIVIDADEAlgoritmo FactorialFuno Recursiva
No caso de erro em funo recursivas, o maiscomum a recursividade nunca parar.
O nmero de chamadas recursivas cresce
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
110/115
110
O nmero de chamadas recursivas cresceindefinidamente at esgotar a memria, e oprograma gera um erro.
A recursividade infinita o equivalente aos ciclosinfinitos do tipo do-while, whie e for.
static int factorial_recursiva(int n){
if (n
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
111/115
111
Elabora um programa que:
Leia valores de um array; Introduza valores num array numadeterminada posio;
Retire valores de uma dada posio.
Lista LinearLista Linear Conjunto de informaes de qualquer tipo,
organizadas sequencialmente;
As operaes bsicas em listas lineares so: Busca:
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
112/115
112
Tem por objectivo a localizao de elementos na lista; Insero:
Tem por objectivo acrescentar um novo elemento lista;
Remoo:Tempo por objectivo remover um elemento da lista;
Os elementos de uma lista so denominados dens;
Um elemento de uma lista pode conter uma oumais informaes:
a) Listas de elementos com uma nica informaoExemplo: Lista de nmeros inteiros, nmeros reais,caracteres, strings;
b) Listas de elementos com vrias informaes:
Exemplo: Lista de notas de DPM. Para cada alunoexistir um campo para o nome, o nmero e a nota,existindo assim 3 campos por n.
Lista Linear Exemplo 1
Exemplo 2 Lista de Registos Armazenamento
Lista LinearExemplo 1 As notas dos alunos da turma de DPM para a
cadeira de Algoritmos formam uma lista se forem
organizadas da seguinte maneira:
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
113/115
113
Cada registo da lista contm campos com as
seguintes informaes: Nmero de matrcula,nome do aluno e respectiva nota a Algoritmos.
Lista Linear Exemplo 1
Exemplo 2 Lista de Registos Armazenamento
N 3N 2N 1NotaNota
NomeNome
NmeroNmero
Lista LinearExemplo 2 Um polinmio de trs variveis x, y, e z descrito
por meio de uma sequencia de termos, em que
cada termo constituido por um coeficiente(nmero real) e os trs expoentes (nmerosi t i ) d t i i
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
114/115
114
inteiros) das trs variveis x, y, e, z.
Cada registo da lista contm 4 campos. Exemplo prtico:
P(x, y, z) = 4x5-3x3y+6x2y2+10y5-2xyz+5z5
Lista Linear Exemplo 1
Exemplo 2 Lista de Registos Armazenamento
Expoente XExpoente X
N 3N 2N 1
Expoente ZExpoente Z
Expoente YExpoente Y
CoeficienteCoeficiente
N 6N5N 4N 3N 2N 1
510000
015210
010235
5-2106-34
Lista LinearLista de Registos Um polinmio de trs variveis x, y, e z descrito
por meio de uma sequencia de termos, em que
cada termo constituido por um coeficiente(nmero real) e os trs expoentes (nmerosinteiros) das trs variveis x y e z
7/22/2019 Sebenta Algoritmos (sem resoluo de exercicios) (4)
115/115
115
inteiros) das trs variveis x, y, e, z.
Cada registo da lista contm 4 campos. Exemplo prtico:
P(x, y, z) = 4x5-3x3y+6x2y2+10y5-2xyz+5z5
Lista Linear Exemplo 1
Exemplo 2 Lista de Registos Armazenamento
Expoente XExpoente X
N 3N 2N 1
Expoente ZExpoente Z
Expoente YExpoente Y
CoeficienteCoeficiente
N 6N5N 4N 3N 2N 1
510000
015210
010235
5-2106-34