Introdução e contextualização: algoritmos e estruturas de dados

Introdução e contextualização: algoritmos e estruturas de dados. O editor e compilador de C. Hiperligações. Referências e avaliação.

Trabalhar com vectores Vectores (arrays, em Inglês) são conjuntos de elementos que estão guardados sequencialmente em memória. Descarrega os exemplos da aula de hoje (explicados na aula). Eles exemplificam os seguintes processos: • Pesquisa: varres o vector do primeiro elemento ao último. Se no meio encontras o item que estavas à procura, paras o processo indicando sucesso. Só indicas que o item não existe no vector depois de varrer todos os elementos. • Inverter: varres o vector do início até metade. A ideia é trocar cada elemento com o elemento no “lado” oposto do vector. Repara que para efectuar essa troca precisas de uma variável temporária. Faz agora os seguintes exercícios: • procura-2.c – Pesquisar por múltiplas ocorrências do mesmo item. Altera a pesquisa para mostrar a posição em que o item é encontrado. Se ele for encontrado em múltiplas posições, deves exibi-las todas. Se ele não for encontrado no vector, deve ser exibida uma mensagem especial a indicar essa situação. • inverte-2.c – Faz outro programa de inversão que usa dois vectores, criando uma versão invertida do primeiro vector, no segundo. Como será que podes fazê-lo funcionar?*

* Varres o primeiro vector do inicio ao fim. Cada elemento do primeiro vector é copiado para o segundo, mas na posição oposta. A ultima pergunta é: como calculas a “posição oposta”?

© 2010 Pedro Freire // Algoritmia pág. 8 www.pedrofreire.com •

mistura.c. Cria dois vectores de 10 elementos e um terceiro de 20 elementos. Faz o teu programa preencher o 3º vector com os elementos intercalados dos dois primeiros vectores. Exemplo:

vector1[10] = { 100, 200, 300, ... }; vector2[10] = { 1, 2, 3, ... };

vector3[20] = { 100, 1, 200, 2, 300, 3, ... }; •

mistura-inversa.c. Repete o exercício anterior, mas onde o 2º vector é misturado no 3º do fim para o início. Exemplo:

vector1[10] = { 100, 200, 300, ... }; vector2[10] = { ... , 8, 9, 10 };

vector3[20] = { 100, 10, 200, 9, 300, 8, ... };

Tira as dúvidas com o professor, nas aulas.

Sentinelas A pesquisa é um processo relativamente comum e que precisa de ser efectuado o mais rapidamente possível. A pesquisa sequencial em vectores que vimos até agora não tem remédio senão repetir-se até se encontrar o que procurávamos, ou repetir até ao fim do vector, dependendo da situação. Mas podemos melhorar o que acontece em cada iteração (repetição) do ciclo interno da pesquisa. Até agora precisamos de fazer duas comparações neste ciclo: • Comparar o elemento do vector onde nos encontramos com o item que estamos à procura, • Verificar se chegámos ao final do vector para pararmos. Podemos eliminar uma destas operações (tornando o ciclo mais rápido) se soubermos que o item de que estamos à procura existe sempre. Isto pode-se garantir criando mais um elemento ao final do vector que preenchemos com o item que vamos procurar antes de começar a procura. Assim sabemos que vamos sempre encontrar o item, e podemos eliminar a segunda comparação. Chamamos a este elemento adicional, a “sentinela”. Ou seja passamos disto: for( i=0; i<tam; i++ ) { if(vct[i]==n) return 1; } para: for( i=0; vct[i]!=n; i++ );

© 2010 Pedro Freire // Algoritmia pág. 9 www.pedrofreire.com

Para saber se o item que estávamos à procura existia no vector original ou não, só temos de comparar a posição onde ele foi encontrado, com a posição da sentinela. Se for igual, encontrámos a sentinela e exibimos no ecrã “não encontrado”. Como exercício, altera a pesquisa original dos exemplos para funcionar com sentinela (procura-sentinela.c).

Recursividade Recursividade é o que se chama a algoritmos que funcionam fazendo uma função chamar-se a si mesma. Em Matemática diz-se que uma definição é recursiva quando se define recorrendo a si mesma. Exemplo: n! = { 1 se n = 0 { n × (n-1)! caso contrário Ou em linguagem C: int factorial( int n ) { if( n == 0 ) return 1; return n * factorial( n-1 ); } Exercícios: • Cria uma função recursiva que calcula a sequência Fibonacci. A função main() deve exibir os primeiro 10 números de Fibonacci. Fibonacci de 0 e 1 são eles mesmos. Acima de 1, o número Fibonacci é a soma dos dois anteriores Fibonacci (n-1 e n-2). • Cria uma função recursiva que exibe um vector de teste no ecrã (do primeiro elemento para o ultimo)*. • Cria uma função recursiva que exibe um vector de teste pela ordem inversa (do ultimo elemento para o primeiro). Tira as dúvidas com o professor, nas aulas.

* Dica: usa uma função exibe(int vct[], int tam, int posicao_a_exibir).

© 2010 Pedro Freire // Algoritmia pág. 10 www.pedrofreire.com

Aula 02

Introdução às ordenações: Bubble sort.

Bubble sort O bubble sort (“ordenação por bolhas”) é uma forma simples de ordenar vectores que deves ter aprendido nas aulas teóricas. O exemplo bubblesort.c será explicado na aula.

Exercícios Completa os seguintes exercícios: • bubblesort-invertido.c – Mostra que compreendeste bem como funciona a ordenação, alterando-a para que funcione ao contrário (i.e., que resulte em números ordenados do maior para o mais pequeno). • Aplica estas duas funções de ordenação no programa ordenar5.c cujo esqueleto tens disponível. Testa-o e confirma que funcionam bem. • Cria um bubblesort-double.c que em vez de inteiros, usa doubles (números reais) no vector. • bubblesort-intercalado.c – Altera o bubblesort.c para só ordenar os elementos das posições pares (0, 2, 4, etc.) de um vector de 20 elementos. Os elementos das posições ímpares (1, 3, 5, etc.) devem ficar onde estão. Exemplo:

v[20] = { 2,9,4,0,4,8,2,3,1,1,3,9,2,6,7,5,8,2,9,0 };

Depois do bubblesort_intercalado():

v[20] = { 1,9,2,0,2,8,2,3,3,1,4,9,4,6,7,5,8,2,9,0 }; •

Cria um programa de ordenação que ordena os elementos das posições