Informática para Ciências e Engenharias...

Informática para Ciências e Engenharias

2013/14

Teórica 7

2

Na aula de hoje... Controlo de execução

• ciclos condicionais while … end

• Exemplos• raiz quadrada while

• histograma while e matrizes

• fórmula química while e strings

Processamento de strings• comparação

• decompor URL findstr

3

«Algoritmo» da torrada Pegar no pão Se faca na bancada,

• Pegar na faca Caso contrário

• Ir buscar faca à gaveta Cortar fatia, pôr na torradeira, ligar Enquanto não está pronta

• Esperar

4

Controlo da execução Pegar no pão Se faca na bancada,

• Pegar na faca Caso contrário

• Ir buscar faca à gaveta Cortar fatia, pôr na torradeira, ligar Enquanto não está pronta

• Esperar

Sequência

5

Controlo da execução Pegar no pão Se faca na bancada,

• Pegar na faca Caso contrário

• Ir buscar faca à gaveta Cortar fatia, pôr na torradeira, ligar Enquanto não está pronta

• Esperar

condição

6

Controlo da execução Pegar no pão Se faca na bancada,

• Pegar na faca Caso contrário

• Ir buscar faca à gaveta Cortar fatia, pôr na torradeira, ligar Enquanto não está pronta

• Esperar

ciclo condicional

7

Controlo da execução

Controlo de execução• sequência

• ciclos for … end

• condições if … elseif … else … end• valores e operadores booleanos

• ciclos condicionais while … end

8

Ciclo condicional: while

Executa o bloco de instruções enquanto a condição for verdadeira (não for 0)

while condicao......

end

9

Ciclo condicional: while

Exemplo: dividir x por dois até ter um número menor que 5 (enquanto >=5)

while x>=5x=x/2;

end

10

Exemplo 1: cálculo da raiz quadrada

11

Exemplo 1, raiz quadrada

Calcular raiz quadrada • método babilónico

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

12

Exemplo 1, raiz quadrada

Calcular raiz quadrada • método babilónico

• quando parar?• infinito não é prático

• |xn-x

n+1| pequeno

• quão pequeno?

13

Exemplo 1, raiz quadrada

Calcular raiz quadrada • método babilónico

• quando parar?• infinito não é prático

• |xn-x

n+1| pequeno

• quão pequeno?

• argumento com precisão

14

Exemplo 1, raiz quadrada

Calcular raiz quadrada, assinatura function x=raiz(S,prec)

15

Exemplo 1: raiz (babilónico)

16

Exemplo 1: raiz (babilónico)

Primeira estimativa (x1)

metade de xPrimeiro x

2

média entre x1 e x/x

1

Precisamos de ambos para acondição do while

17

Exemplo 1: raiz (babilónico)

Enquanto os dois valoresforem demasiado diferentes: guardamos o corrente calculamos o próximo (nas mesmas duas variáveis)4

18

Exemplo 1: raiz (babilónico)

Quando o ciclo terminar, devolvemos o x corrente

.

19

Exemplo 1: raiz (babilónico)octave:22> help raiz`raiz' is a function from the file ...

raiz(S,prec) calcula a raiz quadrada de S a uma precisao determinada por prec

octave:23> raiz(4,0.001)ans = 2octave:24> raiz(9,0.001)ans = 3.0000octave:25> raiz(17,0.001)ans = 4.1231octave:26> ans^2ans = 17.000

20

Exemplo 1: raiz (babilónico)

octave:27> raiz(297,0.001)x = 75.250x = 39.598x = 23.549x = 18.081x = 17.254x = 17.234x = 17.234ans = 17.234octave:28> ans^2ans = 297.00

• Outro teste:• tiramos o ; das linhas x = ...

Raiz

21

Exemplo 2: presenças (histograma)

22

Exemplo 2: contar presenças

Numa matriz temos o registo de presenças dos 30 alunos de um turno prático• o número do aluno e o

número da aula

50014 1 50016 1 50019 1 ... 50014 4 50016 4 50019 4 50023 4 ... 50035 5 50049 5 50051 5 ...

23

Exemplo 2: contar presenças

Queremos obter• uma matriz com as

presenças dos alunos

50027 9 50028 10 50030 10 ... 50071 8 50077 10 50081 12 50084 10 50086 11 50090 11 50099 9 ...

24

Exemplo 2: contar presenças

Perceber o problema• Temos de contar as ocorrências de cada

aluno na primeira coluna da matriz de entrada

• O resultado será um histograma dos alunos, agrupado pelo número

25

Exemplo 2: contar presenças

Generalizar o problema• Resolve-se este problema, e outros

semelhantes, com uma função que calcule o histograma• basta calcular o histograma da primeira coluna da

matriz de entrada

26

Exemplo 2: contar presenças

Conceber o algoritmo• Queremos uma matriz com n linhas e 2

colunas:• elemento e número de ocorrências

• pode começar a zeros

• Para cada elemento do vector de entrada• verificar se já existe na matriz do histograma

• se existe somar uma ocorrência nessa linha

• se não existe acrescentar uma linha com uma ocorrência desse elemento

27

Exemplo 2: contar presenças

Conceber o algoritmo

50014 50016 50014 50016 50019 50023

50014 1 0 0 0 0 0 0 0 0 0 0

28

Exemplo 2: contar presenças

Conceber o algoritmo

50014 50016 50014 50016 50019 50023

50014 1 50016 1 0 0 0 0 0 0 0 0

29

Exemplo 2: contar presenças

Conceber o algoritmo

50014 50016 50014 50016 50019 50023

50014 2 50016 1 0 0 0 0 0 0 0 0

30

Exemplo 2: contar presenças

Conceber o algoritmo

50014 50016 50014 50016 50019 50023

50014 2 50016 2 0 0 0 0 0 0 0 0

31

Exemplo 2: contar presenças

Conceber o algoritmo

50014 50016 50014 50016 50019 50023

50014 2 50016 2 50019 1 0 0 0 0 0 0

32

Exemplo 2: contar presenças

Conceber o algoritmo

50014 50016 50014 50016 50019 50023

50014 2 50016 2 50019 1 50023 1 0 0 0 0

33

Exemplo 2: contar presenças

Conceber o algoritmo

50014 50016 50014 50016 50019 50023

50014 2 50016 2 50019 1 50023 1

34

Exemplo 2: contar presenças

Conceber o algoritmo• Tarefas:

• obter a posição na primeira coluna do histograma, ou zero se não existe

• generalizando: pesquisar elemento num vector

• criar o histograma, usando a função de pesquisar

35

Exemplo 2: contar presenças

Assinaturas:function pos=pesquisa(vector,elemento)

function hist=histograma(sequencia)

36

Exemplo 2: contar presenças

37

Exemplo 2: contar presenças

Começando do primeiro, enquanto não encontramos nem saímos do vector vamos incrementando posição.

38

Exemplo 2: contar presenças

Se não saímos do vector é porque encontrámos, caso contrário devolvemos 0.

Mas isto parece complicar desnecessariamente.

Podemos criar uma versão mais simples, pensando ao contrário.

39

Exemplo 2: contar presenças

Se começarmos do fim e formos decrementando a posição, fica automaticamente no 0 quando não encontra.

A única diferença é que devolve a posição do último elemento. Podemos avisar isso na documentação.

40

Exemplo 2: contar presenças

Moral da história: nem sempre a primeira implementação é a melhor...

41

Exemplo 2: contar presenças

Testar a função:

octave:15> help pesquisa`pesquisa' is a function from the file ...

pesquisa(vector,elemento) devolve a posicao do ultimo elemento no vector, ou 0 se nao existe

octave:16> pesquisa([1,2,3],2)ans = 2octave:17> pesquisa([1,2,3],4)ans = 0

42

Exemplo 2: contar presenças

43

Exemplo 2: contar presenças

Criamos a matriz do histograma, toda a zeros (basta depois somar 1 a cada ocorrência)ultimaLinha indica a última linha que contém uma entrada (a partir daí a matriz está vazia)

44

Exemplo 2: contar presenças

Para cada elemento da sequencia vamos pedir a posição na primeira coluna

45

Exemplo 2: contar presenças

Se ainda não existe (pesquisa devolveu 0), então vamos acrescentar uma linha ao histograma e marcar lá o elemento na primeira coluna.Vamos apontar a linha para essa linha também.

46

Exemplo 2: contar presenças

Assim garantimos que, em qualquer dos casos, linha está a apontar para a linha certa. Basta então somar 1 na segunda coluna (porque a matriz começa a 0).

47

Exemplo 2: contar presenças

No final amputamos o que não interessa da matriz do histograma, guardando só até à última linha.

48

Exemplo 2: contar presenças

Testar:octave:19> histograma([1,2,1,2,1,2,4,5,4])ans = 1 3 2 3 4 2 5 1

octave:20> help histograma ... hist = histograma( sequencia ) Devolve o histograma da sequencia numa matriz com uma linha por cada elemento diferente da sequencia, e nas colunas o elemento e o numero de ocorrencias.

49

Exemplo 2: contar presenças

Resolver o problema

octave:21> presencas=histograma(aulas(:,1))presencas =

50014 10 50016 10 50019 11 50023 9 50035 9 50049 10 ...

50014 1 50016 1 50019 1 ... 50014 4 50016 4 50019 4 50023 4 ... 50035 5 50049 5 50051 5 ...

50

Exemplo 3: fórmula química

51

Exemplo 3: fórmula química

Decompor uma fórmula química (string):• e.g. CH3COOC6H4COOH

Numa tabela de caracteres com os elementos diferentes (vector coluna):

C

H

O

Simplificação: assumimos que os símbolos químicos presentes têm apenas uma letra.

52

Exemplo 3: fórmula química

1º passo: perceber o que se pede• identificar cada elemento

• elemento é uma letra

• o que não é letra não é elemento

• (assumimos só um carácter)

• acrescentar à tabela• mas só se não existe

• a tabela será um vector coluna de caracteres

53

Exemplo 3: fórmula química

2º passo: decompor o problema• Para cada carácter na fórmula

• verificar se é elemento

• se for, verificar se já está na tabela

• se não está, acrescentar

54

Exemplo 3: fórmula química

3º passo: algoritmo e assinaturas• verificar se está na tabela

• já está feita:

function pos = pesquisa(vector,elemento)

• tanto faz se o vector é string ou não, horizontal ou vertical. A função pesquisa não distingue isso

• criar a tabelafunction tabela = elementos(formula)

55

Exemplo 3: fórmula química

A tabela começa vazia e vamos percorrer a fórmula.

56

Exemplo 3: fórmula química

Para cada carácter da fórmula, se for maiúscula e não estiver na tabela, acrescenta-se numa nova linha.

57

Exemplo 3: fórmula química

Testar e aplicar ao nosso problemaoctave:70> elementos('CH4')ans =CHoctave:71> elementos('H3PO4')ans =HPOoctave:72> elementos('CH3COOC6H4COOH')ans =CHO

58

processar strings

59

Processar strings

Na próxima aula vamos ver como ler e escrever ficheiros• vamos precisar de processar strings para

separar o seu conteúdo quando for mais complexo do que o str2num processa

60

Exemplo 4: comparar strings

Vamos comparar 2 strings• função strcmp já faz isto

• mas nós queremos considerar que ? conta como igual a qualquer carácter

octave:30> compara('abc','a?c')ans = 1octave:31> compara('abc','a?d')ans = 0octave:32> compara('abc','???')ans = 1

61

Exemplo 4: comparar strings

Assinatura da função:

function igual=compara(s1,s2)

62

Exemplo 4: comparar strings

63

Exemplo 4: comparar strings

Se as strings têm o mesmo comprimento, vale a pena compará-las.Caso contrário, então é falso que sejam iguais.

64

Exemplo 4: comparar strings

Avançamos do primeiro carácter enquanto não ultrapassámos o fim do vector e os elementos são iguais ou algum é um ?

65

Exemplo 4: comparar strings

As strings são iguais se o ciclo while acabou por ultrapassarmos o fim do vector.Nota: o operador > devolve true ou false

66

Exemplo 4: comparar strings

Teste

octave:33> compara('xpto','xptt')ans = 0octave:34> compara('xpto','xpt?')ans = 1octave:35> compara('xpto','??b?')ans = 0octave:36> compara('xpto','??t?')ans = 1octave:37> compara('xp?o','??x?')ans = 1

67

Exemplo 5: decompor URL

68

Exemplo 5: decompor URL

Queremos decompor um URL• e.g. http://ssdi.di.fct.unl.pt/ice/b/index.html

• nestes componentes• protocolo: http

• máquina: ssdi.di.fct.unl.pt

• caminho: ice/b

• ficheiro: index.html

69

Exemplo 5: decompor URL

Queremos decompor um URL• e.g. http://ssdi.di.fct.unl.pt/ice/b/index.html

• nestes componentes• protocolo: http

• máquina: ssdi.di.fct.unl.pt

• caminho: ice/b

• ficheiro: index.html

• Função útil: findstr

70

Exemplo 5: decompor URL

findstr:

octave:23> findstr('aaaaxaaaxaaa','x')ans = 5 9

octave:24> findstr('x','aaaaxaaaxaaa')ans = 5 9

octave:25> findstr('axa','aaaaxyaaxaaa')ans = 8

71

Exemplo 5: decompor URL

72

Exemplo 5: decompor URL

Guardar em barras a posição das barras '/'

73

Exemplo 5: decompor URL

O protocolo é a parte do início à primeira barra menos 2 caracteres

http://ssdi.di.fct.unl.pt/ice/b/index.html

74

Exemplo 5: decompor URL

A máquina está especificada na parte a seguir à segunda barra até antes da terceira.

http://ssdi.di.fct.unl.pt/ice/b/index.html

75

Exemplo 5: decompor URL

O caminho começa a seguir à terceira barra e acaba antes da última.Nota: poderia incluir a última barra também..

http://ssdi.di.fct.unl.pt/ice/b/index.html

76

Exemplo 5: decompor URL

O ficheiro começa a seguir à última barra e acaba no final do URL

http://ssdi.di.fct.unl.pt/ice/b/index.html

77

Exemplo 5: decompor URL

Teste

octave:39> [protocolo,maquina,caminho,ficheiro]= ...> decompoeurl('http://ssdi.di.fct.unl.pt/ice/b/index.html')protocolo = httpmaquina = ssdi.di.fct.unl.ptcaminho = ice/bficheiro = index.html

78

Resumindo...

79

Resumo

while• ciclo para repetir instruções enquanto uma

condição se verifica

• para quando não sabemos à partida quantas iterações são necessárias, mas sabemos verificar se é necessário continuar

Processamento de strings• findstr, isupper (islower, ischar, isalpha, ...)

80

Exemplo: 1º Teste 2012/13

> F('http://www.abc.edu/geology/tectonics.html', '/')

81

Teste

> F('http://www.abc.edu/geology/tectonics.html', '/')ans = tectonics.html

82

Para estudar esta aula

Tentar fazer os exemplos• e alterações ao código

Consultar o manual Octave• while, 10.3

• funções para caracteres, 5.7

83

Cálculo da massa molecular O que já sabemos fazer

• operações e variáveis (números e strings)

• decompor problemas• funções, scripts, código fonte

• manipular vectores e matrizes • números e texto

• controlar a execução• sequência, condições (if … elseif … else)

• ciclos for se sabemos quantas vezes iterar

• ciclos while se sabemos a condição

84

Dúvidas