Algoritmos em c

Disponível somente no TrabalhosFeitos
  • Páginas : 34 (8438 palavras )
  • Download(s) : 0
  • Publicado : 22 de abril de 2012
Ler documento completo
Amostra do texto
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 aastronomia 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

LeiauteMau

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]= x.

x v

987

0 n−1 222 555 111 333 444 666 555 888 777 987 654

o problema faz sentido com qualquer n ≥ 0 se n = 0, o vetor é vazio e essa instância não tem solução como indicar que não há solução?

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

26 / 162

Vetores

Busca

Algoritmo de busca
Recebe um número x e um vetor v[0 . . n−1] com n ≥ 0 e devolve k nointervalo 0 . . n−1 tal que v[k] = x. Se tal k não existe, devolve −1.

int Busca (int x, int v[], int n) { int k; k = n - 1; while (k >= 0 && v[k] != x) k -= 1; return k; }

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

27 / 162

Vetores

Busca

Deselegante e/ou ineficiente!
int k = n - 1, achou = 0; while (k >= 0 && achou == 0) { if (v[k] == x) achou = 1; else k -= 1; }return k;

int k; if (n == 0) return -1; k = n - 1; while (k >= 0 && v[k] != x) k -= 1; return k;

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

28 / 162

Vetores

Busca

Deselegante, ineficiente e/ou errado!
int k = 0; int sol = -1; for (k = n-1; k >= 0; k--) if (v[k] == x) sol = k; return sol; int k = n - 1; while (v[k] != x && k >= 0) k -= 1; return k;

P. Feofiloff(IME-USP)

Algoritmos em C

Campus/Elsevier

29 / 162

Vetores

Busca

Algoritmo recursivo de busca
Recebe x, v e n ≥ 0 e devolve k tal que 0 ≤ k < n e v[k] = x. Se tal k não existe, devolve −1.

int BuscaR (int x, int v[], int n) { if (n == 0) return -1; if (x == v[n-1]) return n - 1; return BuscaR (x, v, n - 1); }

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

30 /162

Vetores

Busca

Deselegante!
int feio (int x, int v[], int n) { if (n == 1) { if (x == v[0]) return 0; else return -1; } if (x == v[n-1]) return n - 1; return feio (x, v, n - 1); }

P. Feofiloff (IME-USP)

Algoritmos em C

Campus/Elsevier

31 / 162

Vetores

Remoção

Problema de remoção Remover o elemento de índice k de um vetor v[0 . . n−1]. Decisões de projeto:...
tracking img