Algoritmos em c

ALGORITMOS em linguagem C
Paulo Feofiloff
Instituto de Matemática e Estatística Universidade de São Paulo

Campus/Elsevier

.

“Algoritmos em linguagem C” Paulo Feofiloff editora Campus/Elsevier, 2009

www.ime.usp.br/ pf/algoritmos-livro/

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

2 / 162

“Ciência da computação não é a ciência dos computadores, assim como a astronomia não é a ciência dos telescópios.”
— E. W. Dijkstra

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

3 / 162

Leiaute

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

4 / 162

Leiaute

Bom

Bom leiaute int Funcao (int n, int v[]) { int i, j; i = 0; while (i < n) { if (v[i] != 0) i = i + 1; else { for (j = i + 1; j < n; j++) v[j-1] = v[j]; n = n - 1; } } return n; }

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

5 / 162

Leiaute

Mau

Mau leiaute int Funcao (int n, int v[]) { int i, j; i = 0; while (i < n) { if (v[i] != 0) i = i + 1; else { for (j = i + 1; j < n; j++) v[j-1] = v[j]; n = n - 1; } } return n; }

Use fonte de espaçamento fixo!
P. Feofiloff (IME-USP) Algoritmos em C Campus/Elsevier 6 / 162

Leiaute

Mau

Péssimo leiaute int Funcao ( int n,int v[] ){ int i,j; i=0; while(i v[n-1]) return x; else return v[n-1]; } }
P. Feofiloff (IME-USP) Algoritmos em C Campus/Elsevier 23 / 162

Recursão

Exemplo

Outra solução recursiva int Máximo (int v[], int n) { return MaxR (v, 0, n); } int MaxR (int v[], int i, int n) { if (i == n-1) return v[i]; else { int x; x = MaxR (v, i + 1, n); if (x > v[i]) return x; else return v[i]; } } /* A função MaxR recebe v, i e n tais que i < n e devolve o valor de um elemento máximo de v[i..n-1]. */

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

24 / 162

Vetores

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

25 / 162

Vetores

Busca

Problema da busca Dado x e vetor v[0 . . n−1], encontrar um índice k tal que v[k]