aulas.txt Seg Nov 28 17:00:12 2005 1 - ime.usp.brhitoshi/mac0122-2012/aulas/aulasJose.pdf · 1. leia instruções "NOVOS USUÁRIOS" 2. como nome e sobrenome use o seu nome e sobrenome,

aulas.txt Seg Nov 28 17:00:12 2005 1

MAC0122 - Princípios de Desenvolvimento de Algoritmos

Zé Augusto Sala 102 Bloco C IME - [email protected]

Página da disciplina: http://latin.ime.usp.br/moodle/Fazer inscrição:1. leia instruções "NOVOS USUÁRIOS"2. como nome e sobrenome use o seu nome e sobrenome, dividido arbitrariamente. Não use apelidos nem abreviaturas.

Depois da inscrição, fazer a matrícula na disciplina.

Avaliação: provas e exercícios-programa.

**********************************************************************Geral: - Técnicas de Programação - Análise de Algoritmos - Estrutura de Dados

Tópicos: - recursão - listas ligadas - backtracking - algoritmos de ordenação e busca - busca de padrão

**********************************************************************Linguagem C.

Linux: compilar com gccgcc -Wall -ansi -pedantic -O2 programa.c -o programa

Windows: - Dev-C++ - Ver páginas http://www.ime.usp.br/˜mac2166/devcpp/ http://www.ime.usp.br/˜mac2166/devcpp/devcppintro/

**********************************************************************EP0: teste de entregas de EPs**********************************************************************http://www.ime.usp.br/˜pf/mac122/aulas/temperatura.html

// Programa conversor de temperaturas// ----------------------------------// Este programa converte graus Fahrenheit// em graus Celsius e vice-versa.//////////////////////////////////////////

public class Conversor{ static double celsiusParaFahrenheit (double c) { return 9.0 * c / 5.0 + 32.0; }

static double fahrenheitParaCelsius (double f) { return 5.0 * (f - 32.0) / 9.0; }

public static void main (String[] args)

aulas.txt Seg Nov 28 17:00:12 2005 2

{ double far, cel;

System.out.print ("Temperatura em graus Fahrenheit: "); far = sc.nextDouble (); cel = fahrenheitParaCelsius (far); System.out.println ("igual a " + cel + " graus Celsius");

System.out.print ("Temperatura em graus Celsius: "); cel = sc.nextDouble (); far = celsiusParaFahrenheit (cel); System.out.println ("igual a " + far + " graus Fahrenheit"); }}

Eis o mesmo programa escrito em linguagem C:

/* Programa conversor de temperaturas// ----------------------------------// Este programa converte graus Fahrenheit// em graus Celsius e vice-versa./////////////////////////////////////// */

#include <stdio.h>float celsiusParaFahrenheit (float c);float fahrenheitParaCelsius (float f);

int main (){ float far, cel;

printf ("Temperatura em graus Fahrenheit: "); scanf ("%f", &far); cel = fahrenheitParaCelsius (far); printf ("igual a %.1f graus Celsius\n", cel);

printf ("\nTemperatura em graus Celsius: "); scanf ("%f", &cel); far = celsiusParaFahrenheit (cel); printf ("igual a %.1f graus Fahrenheit\n", far);

return 0;}

float celsiusParaFahrenheit (float c){ return 9*c/5 + 32;}

float fahrenheitParaCelsius (float f){ return 5*(f - 32)/9;}

**********************************************************************http://www.ime.usp.br/˜pf/mac122/aulas/java-c.html

Java versus C

Java | Cclasse |objeto |método | função

aulas.txt Seg Nov 28 17:00:12 2005 3

assinatura | protótipoatributo de classe | variável global | ponteiro | endereço (= address)interface | arquivo .h// ... | /* ... */boolean | intfalse, true | 0, 1null | NULLint[] x; | int *x;int[] x = new int[99]; | int x[99];int[] x = new int[99]; | int *x; x = malloc(99 * sizeof (int));byte | charSystem.out.print | printfSavitchIn.readLine | scanfString | char *"AB" + "CDE" | "AB" "CDE"p.x | p->x

**********************************************************************Programa em C:

includesdefinesprotótipo de funçõesmainfunções

Programa em C#include <stdio.h>#include <stdlib.h>definição de contantesint main(){ definição de variáveis comandos system("pause"); return 0;}

**********************************************************************

#include <stdio.h> - inclui as definições das funções padrão de entrada e saída do C (standard input/output)

defines: definições de constantes. Ex.#define TRUE 1#define FALSE 0

protótipo de função: cabeçalho da função, sem chaves, seguido de ;

**********************************************************************

Comando composto: 0 ou mais comandos agrupado por chaves

é um comando!{ comando1 comando2 ... comandok}

Significado: agrupa 0 ou mais comandos em um único comando.

aulas.txt Seg Nov 28 17:00:12 2005 4

Ex.: { soma = soma + num; num = 10*53; }---------------------------------------------------------------------Comando whilewhile (condição) comandoSignificado: enquanto a condição for verdadeira, executecomando. comando é executado 0 ou mais vezes.Ex. while (num != 0){ soma = soma + num; scanf("%d",&num); }---------------------------------------------------------------------Condição: usa os operadores >, >=. <, <=, ==, !=, &&, ||, !---------------------------------------------------------------------Expressão: usa os operadores +, -, *, /, %---------------------------------------------------------------------Comando if:

if (condição) comando

Significado: executa <comando> se e somente se <condição> é verdadeira.---------------------------------------------------------------------Comando if-else:

if (condição) comando1else comando2

Significado: executa comando1 se e somente se condição é verdadeira;executa comando2 se e somente se condição é falsa.---------------------------------------------------------------------Operadores / e %/ divisão % resto da divisão5/2 é 2 5%2 é 11/2 é 0 1%2 é 110/6 é 1 10%6 é 4

Cuidado com números negativos:-5/2 = -2 ou -3, dependendo do compilador-5%2 = -1 ou +1, dependendo do compilador

Sempre é verdade que a == (a/b)*b+a%b---------------------------------------------------------------------Comando for

for (atrib1; condição; atrib2) comandoatrib1 e atrib2: atribuições sem o ;(O comando de atribuição é id=expressão;)

Significado:atrib1;while (condição){ comando atrib2;}---------------------------------------------------------------------

aulas.txt Seg Nov 28 17:00:12 2005 5

Comando vazio;não faz nada

for (i=0; i < 5; i++) printf("%d ",i); for (i=0; i < 5; i++); printf("%d ",i);---------------------------------------------------------------------Prioridades de operadores:

Operador Associatividade() [] -> . esquerda para a direita! ˜ ++ -- - (tipo) * & sizeof direita para a esquerda* / % esquerda para a direita+ - esquerda para a direita<< >> esquerda para a direita< <= > >= esquerda para a direita== != esquerda para a direita& esquerda para a direita^ esquerda para a direita| esquerda para a direita&& esquerda para a direita|| esquerda para a direita?: direita para a esquerda= += -= *= /= %= &= ^= |= <<= >>= direita para a esquerda, esquerda para a direita

Operadore unários & +, -, and * têm maior prioridade do que na formabinária.---------------------------------------------------------------------abreviaturas:++ e --i++; equivale a i = i + 1;

+= *= /= -= %=a+=b; equivale a a=a+b;a+=(b+c)*d equivale a a = a + (b + c)*d;a*=b+c equivale a a = a*(b + c);x op=expressão; equivale a x = x op (expressão);

atribuição múltiplaa=b=c=0; equivale a a=0; b=0; c=0;a=b=c=x; equivale a a=x; b=x; c=x;

atribuição na definição das variáveis:int a=0;

Exemplo:São equivalentes:int a, b, c, d, e;a=0; b=0; c=0; d=1; e=2;

int a, b, c, d, e;a=b=c=0;d=1; e=2;

int a=0, b=0, c=0, d=1, e=2;---------------------------------------------------------------------

Constantes simbólicas: define

aulas.txt Seg Nov 28 17:00:12 2005 6

#include <stdio.h>#define TRUE 1#define FALSE 0#define CHAPEU 3.14protótipo de funçõesmainfunções

Usando o "#define nome valor" todas [quase] as ocorrências de "nome"no programa são substituídas por "valor".---------------------------------------------------------------------Comando de leitura: scanf("%d %d",&a,&b); [espaço não é necessário] leitura de dados via teclado. O programa pára e espera pela digitação de dois inteiros, separados por espaço em branco e seguidos de <enter> Cada %d corresponde a uma variável na ordem em que aparece.Comando printf("A soma e’ %d\n",soma); Imprime mensagem na tela do computador. Imprime ao invés do %d o valor da variável "soma" e ao invés de "\n" muda o cursor de linha.Ex.: printf("%d %d\n",a,b); printf("Valor de a = %d Valor de b = %d\n",a,b);Cada %d corresponde a uma variável na ordem em que aparece.

%d - inteiro base dez%f - float e impressão de double%lf - leitura de double%c - char---------------------------------------------------------------------Tipo real: float e double

definição: float x,y;No Dev-C++:Tamanhos de inteiros: entre -2^{31} e 2^{31}-1 (usa 4 bytes) entre -2.147.483.647-1 e 2.147.483.647

Tamanhos de double: (8 bytes)menor valor positivo: 2.2250738585072014e-308maior valor: 1.7976931348623157e+30815 dígitos de precisão

Tamanhos de float: (4 bytes)menor valor positivo: 1.175494351E-38maior valor: 3.402823466E+386 dígitos de precisão

Leitura: int n; float x; scanf("%f",&x); scanf("%f %d",&x,&n);

Impressão printf("%f",x); printf("x = %f e n = %d\n",x,n);

float x,y;

x = 1.23456789; y = 9.87654321; printf("%f %f\n",x,y);Imprime: 1.234568 9.876543 (6 casas depois da vírgula)

Operadores: +, -, *, /, >, ...

aulas.txt Seg Nov 28 17:00:12 2005 7

Operações envolvendo dois operandos float: resultado é um float, comoesperado.Operações envolvendo um operando int e um operando float: antes daoperação o operando int é convertido em float e o resultado daoperação é um float.

Atribuições:

int n;float x;

n=x; o valor de n será o valor de x truncado[n=-1.9; resulta em n == -1]x=n; produz o resultado esperado

Como fazer em C a atribuição x=1/4?Operador cast: (tipo) expressãoEfeito: o resultado de expressão é convertido ao tipo floatExemplo: x = (float) 1/4;Efeito: 1. o 1 é transformado em float 2. como 1 é float agora, o 4 é transformado em float antes da divisão 3. a divisão é executada com floats.Precedências: () (tipo) * / % + - < > <= >= != == && ||

O que acontece com (float)(1/4)?

**********************************************************************

Tipo char: elementos de um conjunto de "caracteres". São símbolos, letras, dígitos. Esse conjunto é codificado por uma tabela. Uma codificação bastante usada é o código ASCII (American Standard Code for Information Interchange). Tem 128 símbolos. Outras codificações: ISO-8859-1 (extensão do ASCII), Iso-latin-1, EBCDIC (Extended Binary Coded Decimal Interchange Code)

Definição: char s,t; Leitura: scanf("%c",&s); Impressão: printf("%c",s); atribuição: s=’a’; s=’t’; s=t;

Comparação: produz resultados de acordo com a codificação usada. NoASCII’A’ < ’B’ < ... < ’Z’ ’a’ < ’b’ < ... < ’z’ ’0’ < ’1’ < ... < ’9’

caractere posição na tabela’\n’ 10’ ’ 32’0’ 48’A’ 65’a’ 97

aulas.txt Seg Nov 28 17:00:12 2005 8

Imprimindo um caractere como inteiro, a ordem do caractere no conjunto(ASCII) é impresso:Ex.: s=’a’; printf("%d\n",s);Imprime 97E vice-versa: printf("%c\n",97);Imprime a

Aritmética com char: s=’a’+1; resulta em s com valor ’b’

’0’+3 é igual ao caractere ’3’

Somando um char x com um inteiro n resulta no char correspondente a n posições a frente do char x

Tabela ASCII: Decimal/Character 0 NUL 1 SOH 2 STX 3 ETX 4 EOT 5 ENQ 6 ACK 7 BEL 8 BS 9 HT 10 NL 11 VT 12 NP 13 CR 14 SO 15 SI 16 DLE 17 DC1 18 DC2 19 DC3 20 DC4 21 NAK 22 SYN 23 ETB 24 CAN 25 EM 26 SUB 27 ESC 28 FS 29 GS 30 RS 31 US 32 SP 33 ! 34 " 35 # 36 $ 37 % 38 & 39 ’ 40 ( 41 ) 42 * 43 + 44 , 45 - 46 . 47 / 48 0 49 1 50 2 51 3 52 4 53 5 54 6 55 7 56 8 57 9 58 : 59 ; 60 < 61 = 62 > 63 ? 64 @ 65 A 66 B 67 C 68 D 69 E 70 F 71 G 72 H 73 I 74 J 75 K 76 L 77 M 78 N 70 O 80 P 81 Q 82 R 83 S 84 T 85 U 86 V 87 W 88 X 89 Y 90 Z 91 [ 92 \ 93 ] 94 ^ 95 _ 96 ‘ 97 a 98 b 99 c 100 d 101 e 102 f 103 g 104 h 105 i 106 j 107 k 108 l 109 m 110 n 111 o 112 p 113 q 114 r 115 s 116 t 117 u 118 v 119 w 120 x 121 y 122 z 123 { 124 125 } 126 ˜ 127 DEL**********************************************************************

comando switchExemplo: int mes; scanf("%d",&mes); switch (mes) { case 1: printf("janeiro\n"); break; case 2: printf("fevereiro\n"); break; ... case 12: printf("dezembro\n"); break; default: printf("nao sei\n"); break; }

Formato: switch(expressão){ case cte1: comandos1 case cte2: comandos2 ...

aulas.txt Seg Nov 28 17:00:12 2005 9

default: comandosk }

expressão: valor inteiro ou char

ctes: constantes distintas. Não podem ser expressões com variáveis.

Significado: o valor da expressão é calculado e uma constante com esse valor é procurada. Os comandos que seguem o case dessa constante são executado até o final do switch ou até um break ser encontrado. Caso nenhuma constante corresponda à expressão, os comandos do default são executados. O default é opcional e pode aparecer em qualquer posição. Caso não exista default e nenhuma constante corresponda a expressão, o comando switch não faz nada. Quando um break é encontrado é encerrada a execução do switch.

**********************************************************************#include <stdio.h>

/* Le numeros de um arquivo e imprime em outro */int main(){ int quantidade, n, i; char nome_ent[40], nome_sai[40]; FILE *arq_ent, *arq_sai;

printf("Digite nome de arquivo de entrada: "); scanf("%s", nome_ent);

printf("Digite nome de arquivo de saida: "); scanf("%s", nome_sai);

arq_ent = fopen(nome_ent, "r"); if (arq_ent == NULL) { printf("Arquivo %s nao pode ser aberto\n", nome_ent); return 1; }

arq_sai = fopen(nome_sai, "w"); if (arq_sai == NULL) { printf("Arquivo %s nao pode ser aberto\n", nome_sai); fclose(arq_ent); return 1; }

/* primeiro inteiro e’ o numero de inteiros no arquivo */ fscanf(arq_ent, "%d", &quantidade);

for (i = 0; i < quantidade; i++) { fscanf(arq_ent, "%d", &n); fprintf(arq_sai, "%d ", n); }

fclose(arq_ent); fclose(arq_sai);

return 0;}

**********************************************************************Recursão

aulas.txt Seg Nov 28 17:00:12 2005 10

/* Calcula n! para n >= 0 */int fat(int n){ if (n <= 1) return 1; else return n*fat(n-1);}______________________________________________________________________

1. Um ou mais casos simples são resolvidos diretamente

2. Outros caso podem ser redefinidos em termos de problemas "maispróximos" aos casos simples.

3. Pela aplicação sucessiva do processo de redefinição mais cedo oumais tarde o problema é reduzido inteiramente aos casos simples.

Se é um caso simples resolva o problema diretamentesenão redefina o problema usando recursão______________________________________________________________________

Simulação

fat(4) /24| -------------------- | n = 4 | | n <= 1 é falso | / | devolva 4*fat(3) | 6 ------------------ | ------------------ -- | n = 3 | | n <= 1 é falso | / | devolva 3*fat(2) | 2 ------------------ | ------------------ -- | n = 2 | | n <= 1 é falso | / | devolva 2*fat(1) | 1 ------------------ | --------------------- -- | n = 1 | | n <= 1 é verdadeiro | | devolva 1 | ---------------------______________________________________________________________________

/* Calcula o maior elemento dentre inteiros V[0], V[1], ..., V[n-1], para n >= 1*/int maxr(int v[], int n){ int max;

if (n == 1) max = v[0]; else { max = maxr(v,n-1); if (max < v[n-1])

aulas.txt Seg Nov 28 17:00:12 2005 11

max = v[n-1]; } return max;}______________________________________________________________________

/* Calcula valor da soma V[0] + V[1] + ...+ V[n-1], para n >= 1 */

int somar(int v[], int n){

if (n == 1) return v[0]; else return somar(v, n-1) + v[n-1];}______________________________________________________________________

Simulação para v = 4 5 6

somar(v,3) /15| ------------------------ \ | n == 1 é falso | | devolva 6 + somar(v,2) | / ------------------------ 9 ------------------------ \ - | n == 1 é falso | / | devolva 5 + somar(v,1) | 4 ------------------------ | --------------------- -- | n == 1 é verdadeiro | | devolva 4 | --------------------- ______________________________________________________________________

Algoritmo de Euclides

| 2 | 1 | 1 | 12315 | 125 | 65 | 60 | 5 65 | 60 | 5 | 0 |

| 2 | 3 | 1 | 2 <---- parte inteira da divisão275 | 121 | 33 | 22 | 11 33 | 22 | 11 | 0 | <---- resto da divisão

/* Calcula máximo divisor comum entre m e n com m e n inteiros não-negativos sendo um deles positivo*/int mdc(int m, int n){ if (n == 0) return m; else return mdc(n, m%n);}

mdc(24,210) -> mdc(210,24) -> mdc(24, 18) -> mdc(18,6) -> mdc(6,0) = 6______________________________________________________________________

Torres de Hanói

aulas.txt Seg Nov 28 17:00:12 2005 12

A B C ---|--- | | ----|---- | | -----|----- | | ------|------ | | -------|------- | | --------|-------- | |____________________________________________________________________

Mover n discos de diâmetros diferentes do pino A para o pino C usandopino B quando necessário. Os movimentos seguem as regras:1. Somente um disco pode ser movido por vez e esse disco precisar ser o disco no topo do pino.2. Um disco maior nunca pode ser colocado sobre um disco menor.

____________________________________________________________________

Idéia: para mover n discos do pino *origem* para o pino destino:se n é 0, não faz nadasenão 1. mova n-1 discos de *origem* para *auxiliar* usando *destino* como auxiliar 2. mova disco n de *origem* para *destino* 3. mova n-1 discos de *auxiliar* para *destino* usando *origem* como auxiliar

Inicialmente *origem* = ’A’, *auxiliar* = ’B’, *destino* = ’C’____________________________________________________________________

Simulação de Hanoi(3, ’A’, ’B’, ’C’)

-------- ------------------------ | n = 0 | | n = 1 | | | | origem = ’A’ | | | | aux = ’B’ | -------- | destino = ’C’ | -------- ------------------------- | Hanoi(0, ’A’, ’C’, ’B’) | | n = 0 | | n = 2 | | mova 1 de ’A’ para ’C’ | | | | origem = ’A’ | | Hanoi(0, ’B’, ’A’, ’C’) | | | | aux = ’C’ | ---------------------- -------- | destino = ’B’ | -------- | Hanoi(1, ’A’, ’B’, ’C’) | ------------------------- | n = 0 | | mova 2 de ’A’ para ’B’ | | n = 1 | | | | Hanoi(1, ’C’, ’A’, ’B’) | | origem = ’C’ | | | ------------------------- | aux = ’A’ | -------- | destino = ’B’ | -------- | Hanoi(0, ’C’, ’B’, ’A’) | | n = 0 | ------------------------- | mova 1 de ’C’ para ’B’ | | || n = 3 | | Hanoi(0, ’A’, ’C’, ’B’) | | || origem = ’A’ | ------------------------ --------| aux = ’B’ || destino = ’C’ | --------| Hanoi(2, ’A’, ’C’, ’B’) | ------------------------- | n = 0 || mova 3 de ’A’ para ’C’ | | n = 1 | | || Hanoi(2, ’B’, ’A’, ’C’) | | origem = ’B’ | | | ------------------------- | aux = ’C’ | -------- | destino = ’A’ | -------- ------------------------- | Hanoi(0, ’B’, ’A’, ’C’) | | n = 0 | | n = 2 | | mova 1 de ’B’ para ’A’ | | | | origem = ’B’ | | Hanoi(0, ’C’, ’B’, ’A’) | | | | aux = ’A’ | ------------------------- --------

aulas.txt Seg Nov 28 17:00:12 2005 13

| destino = ’C’ | | Hanoi(1, ’B’, ’C’, ’A’) | ------------------------- -------- | mova 2 de ’B’ para ’C’ | | n = 1 | | n = 0 | | Hanoi(1, ’A’, ’B’, ’C’) | | origem = ’A’ | | | ------------------------- | aux = ’B’ | | | | destino = ’C’ | -------- | Hanoi(0, ’A’, ’C’, ’B’) | -------- | mova 1 de ’A’ para ’C’ | | n = 0 | | Hanoi(0, ’B’, ’A’, ’C’) | | | ------------------------- | | --------

Seguindo as flechas:

mova 1 de ’A’ para ’C’mova 2 de ’A’ para ’B’mova 1 de ’C’ para ’B’mova 3 de ’A’ para ’C’mova 1 de ’B’ para ’A’mova 2 de ’B’ para ’C’mova 1 de ’A’ para ’C’----------------------Total de movimentos: 7Total de chamadas: 15

Em geral: para n discos: 2^{n} - 1 movimentos 2^{n+1} - 1 chamadas da função

/* Imprime movimento de torres de Hanoi para n discos para n >= 0*/

void Hanoi(int n, char origem, char auxiliar, char destino){ if (n > 0) { Hanoi(n-1, origem, destino, auxiliar); printf("Mova disco %d do pino %c para o pino %c\n", n, origem, destino); Hanoi(n-1, auxiliar, origem, auxiliar); }}______________________________________________________________________

Números de Fibonacci

filhote adultocasal1 -> casal1 -> casal1 -> casal1 -> casal1 -> casal1 |-> casal2 |-> casal3 |-> casal4 |-> casal6 \-> casal2 \-> casal3 \-> casal4 \-> casal2 \-> casal3 |-> casal5 |-> casal7 \-> casal2 |-> casal8 \-> casal5Geração 1 -> Gera 2 -> Gera 3 -> Gera 4 -> Gera 5 -> Gera 6

Fib(n) = n se n é 0 ou 1 Fib(n-1) + Fib(n-2) caso contrário

Fib(0) = 0, Fib(1) = 1, Fib(2) = 1, Fib(3) = 2, Fib(0) = 3

/* Calcula o n-esimo numero de Fibonacci para n >= 0*/

aulas.txt Seg Nov 28 17:00:12 2005 14

int Fib(int n){ if (n <= 1) return n; else return Fib(n-1) + Fib(n-2);}

______________________________________________________________________

Fib(5) / \ / \ Fib(4) Fib(3) / \ / \ Fib(3) Fib(2) Fib(2) Fib(1) / \ / \ / \ Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0) / \Fib(1) Fib(0)

razão áurea: (1+raiz(5))/2 aprox 1.6

Tempo para computar Fib(n+1)--------------------------- aprox 1.6Tempo para computar Fib(n)______________________________________________________________________

Versão iterativa: muito mais eficiente

int Fib(int n){ int ant, atual, i;

if (n <= 1) return n;

ant = 0; atual = 1; for (i = 1; i < n; i++) { /* atual é Fib(i) */ atual = atual + ant; ant = atual - ant; } return atual;}

**********************************************************************

Curvas de Hilbert __ __ _ |_ |_| _| |_ _ __ _| _ | _ ||_ |_ |_| |__| ||_| |_| _| _ __ | _ _ |__| | |_ |_|| |_| | _| _ |_ _| |__| |__| |_

Ordem 1 Ordem 2 Ordem 3

_ _ _A |_ B | | C _| D |_|

aulas.txt Seg Nov 28 17:00:12 2005 15

A: D <- A | A -> BB: C ^ B -> B | AC: B -> C ^ C <- DD: A | D <- D ^ C

| flecha para baixo

#define BRANCO 255#define PRETO 0

int main(){ /* leitura de dados */ /* criação da imagem */ /* determinação do tamanho da aresta */ /* determinação da posição inicial do desenho */ a(imagem, ordem, &x, &y, tamanho_aresta); /* Gravação do arquivo */

return 0;}

/* A */void a (Imagem imagem, int k, int *x, int *y, int comprimento) { if (k > 0) { d(imagem, k - 1, x, y, comprimento); DesenhaeMove(imagem, x, y, -comprimento, 0, PRETO); a(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, 0, -comprimento, PRETO); a(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, comprimento, 0, PRETO); b(imagem, k-1, x, y, comprimento); }}

/* B */void b (Imagem imagem, int k, int *x, int *y, int comprimento) { if (k > 0) { c(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, 0, comprimento, PRETO); b(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, comprimento, 0, PRETO); b(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, 0, -comprimento, PRETO); a(imagem, k-1, x, y, comprimento); }}

/* C */void c (Imagem imagem, int k, int *x, int *y, int comprimento) { if (k > 0) { b(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, comprimento, 0, PRETO); c(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, 0, comprimento, PRETO); c(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, -comprimento, 0, PRETO); d(imagem, k-1, x, y, comprimento); }}

aulas.txt Seg Nov 28 17:00:12 2005 16

/* D */void d (Imagem imagem, int k, int *x, int *y, int comprimento) { if (k > 0) { a(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, 0, -comprimento, PRETO); d(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, -comprimento, 0, PRETO); d(imagem, k-1, x, y, comprimento); DesenhaeMove(imagem, x, y, 0, comprimento, PRETO); c(imagem, k-1, x, y, comprimento); }}

/* Desenha o segmento de (*x0, *y0) até (*x0+deltax, *y0+deltay), alterando o valor de *x0 e *y0 para *x0+deltax e *y0+deltay */void DesenhaeMove(Imagem imagem, int *x0, int *y0, int deltax, int deltay, int cor){ DesenhaSegmento(imagem, *x0, *y0, *x0 + deltax, *y0 + deltay, cor); *x0 = *x0 + deltax; *y0 = *y0 + deltay;}**********************************************************************

Variáveis tipo endereço:

Como fazer uma função que troca os valores de duas variáveis?

void TrocaErrada(int a, int b){ int temp;

temp=a; a=b; a=b; b=a; b=temp;}

Simulação:

x=1;y=2;TrocaErrada(x,y);printf("%d %d",x,y);**********************************************************************

Endereços:

int a,b,c;float x,y,z;char s,t,u;

a=10; b=15; c=32;x=1.5; y=0.7; z=4.3;s=’m’; t=’k’; u=’p’;

Fazer também "mapa de memória."

nome endereço conteúdoa 38 10b 39 15c 40 32x 72 1.5y 310 0.7z 420 4.3s 150 ’m’

aulas.txt Seg Nov 28 17:00:12 2005 17

t 280 ’k’u 1239 ’p’

Obs.: Vamos sempre pensar endereços como inteiros, embora o C nãoespecifique isso: não podemos manipular endereços como manipulamosinteiros.

Ocorrências de a,b,c,... no programam se referem ao conteúdo dasvariáveis. Como acessar os endereços?

Variáveis tipo endereço:int a, b, c, *end1, *end2, *end3;float x, y, z, *w;char s, t, u, *es, *et, *eu;

Atribuições:end1=&a; a=10;b=78; end2=&b;end3=&c;A seguinte atribuição, depois das atribuições acima, equivale a c=a+b;*end3 = *end1 + *end2;

Operadores * e &:&a - endereço da variável a*p - conteúdo do endereço armazenado em p. p também é conhecido como apontador ou ponteiro.

*end1, *end2 e *end3 devem ser pensadas como variáveis inteiras se end1, end2 e end3 são endereços de inteiros.

NãO VáLIDO:

w = &a; pois chapeu1 armazena endereço de float e a é inteiroend1 = chapeu; endereços de tipos distintos não se confundem&a = eb; NUNCA podemos mudar o endereço de uma variável

**********************************************************************

void troca(int *end1, int *end2){ int temp;

temp = *end1; *end2 = *end1; *end1 = temp;}

x=1;y=2;troca(&x,&y);printf("%d %d",x,y);

&&& Simulação com mapa da memória. Usar seta como apontadores.

Exemplo: escrever função que calcula soma e produto de dois inteiros.

int x,y,z,t;

x = 10; y = 8;

SomaMult(x,y,&z,&t); printf("%d %d %d %d\n", x,y,z,t); Imprime 10 8 18 80

aulas.txt Seg Nov 28 17:00:12 2005 18

SomaMult(x,y,&x,&y); printf("%d %d\n", x,y); Imprime ?? 18 80

CUIDADO: (*k)++;

**********************************************************************

Alocação Dinâmica de Memória

Na definição "int v[10];" v armazena o endereço de um inteiro

----------------------------------------------------------------------

Aloca memória para um vetor de inteiros com n posições.

int n, *v;

scanf("%d", &n);

v = malloc(n*sizeof(int));

----------------------------------------------------------------------

Função malloc - biblioteca stdlib.h (usar #include <stdlib.h> )

malloc(expressão inteira) - devolve um apontador (endereço) para umbloco de memória com _expressão_ bytes, ou devolve NULL se não foipossível alocar a memória

sizeof(tipo) - devolve o tamanho em bytes do tipo

normalmente sizeof(int) - 4 sizeof(float) - 4 sizeof(char) - 1 sizeof(double) - 8 sizeof(int *) - 4 (apontador)----------------------------------------------------------------------

/* Aloca vetor para n elementos inteiros *//* Devolve NULL se não foi possível alocar a memória */int *AlocaVetor(int n){ int *v;

v = malloc(n*sizeof(int));

return v;}

No main: usado normalmente como vetor

int *vetor, i, k;

vetor = AlocaVetor(3); if (vetor == NULL) { printf("Sem memória\n); return 1; }

scanf("%d", &k);

for (i = 0; i < k; i++) scanf("%d", &vetor[i]);

for (i = 0; i < k; i++)

aulas.txt Seg Nov 28 17:00:12 2005 19

printf("%d ", vetor[i]);

free(vetor); /* Libera memória apontada por vetor */

----------------------------------------------------------------------

int a, *p, **z; /* z armazena endereço de endereço de inteiro */

a = 5; p = &a; printf("%d\n", *p); /* imprime 5 */scanf("%d", p); /* digitamos 12 */printf("%d\n", a); /* imprime 12 */

z = &p; | endereço (inventado) | conteúdoprintf("%d\n", **z); a | 5224 | 5**z = 12; p | 5232 | 5224printf("%d\n", a); z | 5236 | 5232 ^ __| estes endereços não podem ser mudados----------------------------------------------------------------------

Matrizes:

int **a;

a = malloc(8*sizeof(int *));

_ [_] --> |_|_|_|_|_| ... |_| [_] --> |_|_|_|_|_| ... |_| [_] --> |_|_|_|_|_| ... |_| [_] --> |_|_|_|_|_| ... |_| [_] --> |_|_|_|_|_| ... |_| [_] --> |_|_|_|_|_| ... |_| [_] --> |_|_|_|_|_| ... |_| [_] --> |_|_|_|_|_| ... |_| ^a -----|

a é um vetor de apontadores para inteiros

for (i = 0; i < 8; i++) a[i] = malloc(30*sizeof(int));

cada a[i] é um vetor de inteiros

/* Aloca memória para uma matriz mXn de inteiros *//* Devolve NULL se não foi possível alocar a memória */int **AlocaMatriz(int m, int n){ int **a; int i, j;

a = malloc(m*sizeof(int *)); if (a == NULL) return NULL;

for (i = 0; i < m; i++){ a[i] = malloc(n*sizeof(int)); if (a[i] == NULL){ for (j = 0; j < i; j++) free(a[j]);

aulas.txt Seg Nov 28 17:00:12 2005 20

free(a); return NULL; } }

return a;}

/* Libera (free) a memória alocada para uma matriz de inteiros com m linhas */void LiberaMatriz(int **A, int m){ int i;

for (i = 0; i < m; i++) free(A[i]);

free(A);}

No main:

int **matriz, m, n;

matriz = AlocaMatriz(m, n); if (matriz == NULL) { printf("Sem memória\n); return 1; }

for (i = 0; i < m; i++) for (j = 0; i < n; j++) scanf("%d", &matriz[i][j]);

for (i = 0; i < m; i++) { for (j = 0; i < n; j++) printf("%d ", matriz[i][j]); printf("\n"); }

LiberaMatriz(A, m);**********************************************************************

Estruturas

Declaração de tipo

typedef struct { int numero; char nome[80]; float nota;} aluno;

Alternativas

typedef struct alun { int numero; char nome[80]; float nota;} aluno;

struct { int numero;

aulas.txt Seg Nov 28 17:00:12 2005 21

char nome[80]; float nota;} aluno1, aluno2;

struct alun { int numero; char nome[80]; float nota;};

struct alun aluno1, aluno2;aluno aluno1, aluno2;----------------------------------------------------------------------

#include <stdio.h>#include <string.h>

typedef struct { int numero; char nome[80]; float nota;} aluno;

/* Imprime os valores dos campos da estrutura al */void imprime(aluno al);

/* Devolve uma estrutura preenchida com os valores dados */aluno monta(int numero, char nome[], float nota);

int main(int argc, char **argv){ aluno aluno1, aluno2;

aluno1 = monta(40, "Paulo", 7.8); aluno2 = monta(41, "Pedro", 6.8);

imprime(aluno1); imprime(aluno2);

scanf("%f", &aluno1.nota); aluno1.numero++;

imprime(aluno1);

aluno2 = aluno1;

imprime(aluno2);

printf("Tamanho em bytes: %d\n", sizeof(aluno)); /* Imprime 88 */

return 0;}

aluno monta(int numero, char nome[], float nota){ aluno al;

al.numero = numero; strcpy(al.nome, nome); al.nota = nota; return al;}

aulas.txt Seg Nov 28 17:00:12 2005 22

void imprime(aluno al){ printf("Numero = %d\n", al.numero); printf("Nome = %s\n", al.nome); printf("Nota = %f\n", al.nota);}

Obs:

Operadores == e != não se aplicam a variáveis do tipo estrutura.

Estruturas, bem como variáveis simples, são copiadas quando passadascomo parâmetros de função. Só a cópia é alterada pela função.

Não funciona:void monta(aluno al){ al.numero = 5; al.nome[0] = ’\0’; al.nota = 6.6;}

Vetores de estruturas

aluno alunos[70];

Uso: alunos[0].numero = 10;

Alocação dinâmica

aluno *alunos;

alunos = malloc(100*sizeof(aluno));

**********************************************************************Listas Ligadas

Estrutura

|_| célula

|___|___| -> |___|___| -> |___|___| -> |___|___|

Flechas são apontadores

Motivação: comparação com vetores [imaginando listas como vetoresexplodidos]

* tamanho de vetores é fixo.* inserção e remoção no meio do vetor precisa empurrar os elementos.* possibilidade de representar estruturas tipo árvore

Declaração de uma célula

----------------------------------------------------------------------

#include <stdio.h>#include <stdlib.h>

typedef struct cel { int valor; struct cel *prox;} celula;

aulas.txt Seg Nov 28 17:00:12 2005 23

int main(){ celula *no; /* |no|->? */

no = malloc(sizeof(celula)); /* |no| -> |_?_|_?_| */

if (no == NULL) { printf("Sem memoria\n"); return 1; }

(*no).valor = 15; (*no).prox = NULL; /* |no| -> |_15_|_\_| */

free(no); return 0;}

---------------------------------------------------------------------- (*no).valor = 15; Parênteses obrigatório

Simplificação no->valor = 15;----------------------------------------------------------------------

Inserção de uma célula no início da lista

celula *nova, *primeira; /* |?| |?| */

primeira = malloc(sizeof(celula)); /* |primeira| -> |_?_|_?_| */

if (primeira == NULL) { printf("Sem memoria\n"); return 1; }

primeira->valor = 15; primeira->prox = NULL; /* |primeira| -> |_15_|_\_| */

nova = malloc(sizeof(celula)); /* |nova| -> |_?_|_?_| */

if (nova == NULL) { printf("Sem memoria\n"); return 1; }

nova->valor = 20; /* |nova| -> |_20_|_?_| */

/* Queremos primeira -> |_20_|-| -> |_15_|_\_| */

nova->prox = primeira; /* |nova| -> |_20_|-| -> |_15_|_\_| |primeira| /> */

primeira = nova;

/* |nova| -> |_20_|-| -> |_15_|_\_| |primeira| /> */----------------------------------------------------------------------

aulas.txt Seg Nov 28 17:00:12 2005 24

#include <stdio.h>#include <stdlib.h>


celula *insere(celula *inicio, int n);void LiberaLista(celula *inicio);void LiberaListaR(celula *inicio);void imprime(celula *inicio);celula *busca(celula *inicio, int n);celula *buscaR(celula *inicio, int n);celula *Remove(celula *inicio, int n); /* remove e’ funcao do stdio.h */

int main(){ celula *inicio, *p; int n;

inicio = NULL; /* lista vazia */

/* Le inteiros ate um 0 ser digitado */ printf("Digite um inteiro (0 para terminar): "); scanf("%d", &n); while (n != 0) { inicio = insere(inicio, n); if (inicio == NULL) { printf("Sem memória\n"); return 1; } printf("Digite um inteiro (0 para terminar): "); scanf("%d", &n); }

imprime(inicio);

printf("Digite numero a ser procurado: "); scanf("%d", &n);

p = busca(inicio, n);

if (p != NULL) printf("Inteiro %d encontrado\n", n); else printf("Inteiro %d nao encontrado\n", n);

printf("Digite numero a ser removido: "); scanf("%d", &n);

inicio = Remove(inicio, n); imprime(inicio);

LiberaLista(inicio);

return 0;}

/* Insere celula com valor n no inicio da lista devolve endereco do início da nova lista ou NULL se nao foi possivel fazer a insercao*/

aulas.txt Seg Nov 28 17:00:12 2005 25

celula *insere(celula *inicio, int n){ celula *nova;


if (nova == NULL) return NULL;

nova->valor = n; nova->prox = inicio;

return nova;}

/* Libera memoria alocada para lista */void LiberaLista(celula *inicio){ celula *ant;

while (inicio != NULL) { ant = inicio; inicio = inicio->prox; free(ant); }}

/* Libera memoria alocada para lista */void LiberaListaR(celula *inicio){ celula *ant;

if (inicio != NULL) { ant = inicio; inicio = inicio->prox; free(ant); LiberaListaR(inicio); }}

/* Imprime valores armazenados na lista */void imprime(celula *inicio){ while (inicio != NULL) { printf("%d ", inicio->valor); inicio = inicio->prox; } printf("\n");}

/* Devolve endereco de celula com valor n ou NULL caso esse valor nao apareca na lista*/celula *busca(celula *inicio, int n){ while (inicio != NULL) { if (inicio->valor == n) return inicio; inicio = inicio->prox; } return NULL;}

aulas.txt Seg Nov 28 17:00:12 2005 26

/* Devolve endereco de celula com valor n ou NULL caso esse valor nao apareca na lista*/celula *buscaR(celula *inicio, int n){ if (inicio == NULL || inicio->valor == n) return inicio; return busca(inicio->prox,n);}

/* Remove, se existir, celula com valor n Devolve lista sem a celula, com valor de inicio possivelmente alterado*/celula *Remove(celula *inicio, int n){ celula *corrente, *ant;

/* ant -\ corrente -\ |inicio| -> |_30_|-| -> |_40_|-| -> |_20_|-| -> |_10_|_/_| */

corrente = inicio; ant = NULL;

while (corrente != NULL && corrente->valor != n) { ant = corrente; corrente = corrente->prox; }

if (corrente == NULL) /* n nao foi encontrado */ return inicio;

if (ant == NULL) /* n esta no inicio */ inicio = inicio->prox; else ant->prox = corrente->prox;

free(corrente); return inicio;}**********************************************************************

Fila

|ini| |fim|

|___|___| -> |___|___| -> |___|___| -> |___|___|

Inserção: no fim da filaRemoção: no início da fila

typedef struct no { int valor; struct no *prox;} celula;

/* Insere célula com valor n numa fila */void insere_fila(celula **ini, celula **fim, int n){ celula *nova;

aulas.txt Seg Nov 28 17:00:12 2005 27

nova = malloc(sizeof(celula));

if (nova == NULL) { printf("Sem memória\n"); exit(1); /* abandona programa */ } nova->valor = n; nova->prox = NULL; if (*fim == NULL) { *ini = nova; *fim = nova; } else { (*fim)->prox = nova; /* parentêses necessário */ *fim = nova; }}

/* Remove primeiro da fila, devolvendo seu valor. Não pode ser usado com fila vazia*/int remove_fila(celula **ini, celula **fim){ int valor; celula *prim;

prim = *ini; valor = prim->valor;

*ini = (*ini)->prox; if (*ini == NULL) *fim = NULL;

free(prim);

return valor;}**********************************************************************

Pilha

|topo|

|___|___| -> |___|___| -> |___|___| -> |___|___|

Inserção: no topo da pilhaRemoção: no topo da pilha

typedef struct no { int valor; struct no *prox;} celula;

/* Insere célula com valor n numa pilha Devolve apontador para novo topo*/

celula *empilha(celula *topo, int n){ celula *nova;

nova = malloc(sizeof(celula));

aulas.txt Seg Nov 28 17:00:12 2005 28

if (nova == NULL) { printf("Sem memória\n"); exit(1); /* abandona programa */ } nova->valor = n; nova->prox = topo; return nova;}

/* Remove topo da pilha, alterando valor do topo Devolve valor armazandado no topo Não pode ser usado com pilha vazia*/int desempilha(celula **topo){ int valor; celula *aux;

aux = *topo; valor = aux->valor; *topo = (*topo)->prox; free(aux);

return valor;}**********************************************************************

Cálculo de Expressões

Posfixa (polonesa) Infixa

5 6 * 5*65 6 1 + * 5*(6+1)5 6 * 9 - (5*6)-914 5 6 * 3 / + 14+((5*6)/3)

Células

Fila Pilhastruct posfixa_ { struct valores_ { char s[D+1]; int valor; struct posfixa_ *prox; struct valores_ *prox;} posfixa; } valores;

----------------------------------------------------------------------

string - Expressão posfixa dada \ [inicio] -> [_14_|-] -> [_5_|-] -> [_6_|-] -> [_*_|-] -> [_3_|-] -> [_/_|-] -> [_+_|\]

Pilha para cálculo de expressão posfixa

[inicio] [inicio] -> [_14_|\] [inicio] -> [_5_|-] -> [_14_|\]

[inicio] -> [_6_|-] -> [_5_|-] -> [_14_|\]

[inicio] -> [_30_|-] -> [_14_|\]

[inicio] -> [_3_|-] -> [_30_|-] -> [_14_|\]

[inicio] -> [_10_|-] -> [_14_|\]

aulas.txt Seg Nov 28 17:00:12 2005 29

[inicio] -> [_24_|\]

----------------------------------------------------------------------

Transformação de infixa para posfixa

/* Pilha auxiliar */

struct pilha_aux_{ char simbolo; struct pilha_aux_ *prox;} pilha_aux;

1 + 2 - 3*4/5*(6 + 7) + 8 <---- string

O que fazer quando encontrar

número ( ) * / + - | brancoInsere fila | empilha | desempilha inserindo | desempilha inse- | desempilha inse- | nada | | na fila até econtrar | rindo na fila até| rindo na fila até| | | ’(’; desempilha ’(’ | encontrar ’(’ | encontrar ’(’ | | | | ou ’+’ ou ’-’ ou | ou acabar pilha; | | | | acabar pilha; | empilha ’+’ ou | | | | empilha ’*’ ou | ’-’ | | | | ’/’ | |

No final, desempilha inserindo na fila até a pilha ficar vazia

Fila posfixa Pilha auxiliar

1 |1 | +1 2 | +1 2 + | -1 2 + 3 | -1 2 + 3 | * -1 2 + 3 4 | * -1 2 + 3 4 * | / -1 2 + 3 4 * 5 | / -1 2 + 3 4 * 5 / | * -1 2 + 3 4 * 5 / | ( * -1 2 + 3 4 * 5 / 6 | ( * -1 2 + 3 4 * 5 / 6 | + ( * -1 2 + 3 4 * 5 / 6 7 | + ( * -1 2 + 3 4 * 5 / 6 7 + | * -1 2 + 3 4 * 5 / 6 7 + * - | +1 2 + 3 4 * 5 / 6 7 + * - 8 | +1 2 + 3 4 * 5 / 6 7 + * - 8 + |

Cálculo da expressão posfixa

Pilha1 # 2 1 # 3 # 3 3 # 4 3 3 # 12 3 # 5 12 3 # 2 3 # 6 2 3 # 7 6 2 3 #13 2 3 # 26 3 # -23 # 8 -23 # 15

----------------------------------------------------------------------

Cálculo de valor de expressão infixa

infixa_para_posfixa calcula_posfixaexpressão infixa ----------------> posfixa ------------------> valor

aulas.txt Seg Nov 28 17:00:12 2005 30

string pilha auxiliar fila pilha de valores

#include <stdio.h>#include <stdlib.h>#include <string.h>

#define D 10 /* numero maximo de digitos de um numero */#define TAMANHO 80 /* numero maximo de caracteres na expressao infixa */

/* Pilha de caracteres para auxiliar montagem da expressao posfixa a partir da expressao infixa */typedef struct pilha_aux_ { char simbolo; struct pilha_aux_ *prox;} pilha_aux;

/* Fila para armazenar expressao posfixa */typedef struct posfixa_ { char s[D+1]; struct posfixa_ *prox;} posfixa;

/* Pilha para armazenar valores no calculo da expressao posfixa */typedef struct valores_ { int valor; struct valores_ *prox;} valores;

/* Empilha e desempilha caracteres */pilha_aux *emp_char(pilha_aux *topo, char c);char des_char(pilha_aux **topo);

/* Insercao e remocao na fila representando a expressao posfixa*/void insere_pos(posfixa **ini, posfixa **fim, char *s);char *remove_pos(posfixa **ini);

/* Empilha e desempilha valores */valores *emp_val(valores *topo, int n);int des_val(valores **topo);

posfixa *infixa_para_posfixa(char *s);int calcula_posfixa(posfixa *ini);

int main(){ posfixa *ini; char infixa[TAMANHO+1]; int i;

printf("Digite expressão infixa: "); /* scanf("%s", infixa) pára leitura no primeiro espaço */ i = -1; do { i++; scanf("%c", &infixa[i]); } while (i <= TAMANHO && infixa[i] != ’\n’); infixa[i] = ’\0’;

ini = infixa_para_posfixa(infixa);

aulas.txt Seg Nov 28 17:00:12 2005 31

printf("Valor = %d\n",calcula_posfixa(ini));

return 0;}

posfixa *infixa_para_posfixa(char *s){ posfixa *ini, *fim; pilha_aux *topo; char simbolos[D+1]; int i, j;

ini = fim = NULL; topo = NULL; /* examina cada posicao da expressao infixa */ for (i = 0; s[i] != ’\0’; i++){ if (’0’ <= s[i] && s[i] <= ’9’){ j = 0; while (’0’ <= s[i] && s[i] <= ’9’){ simbolos[j] = s[i]; i++; j++; } simbolos[j] = ’\0’; insere_pos(&ini,&fim,simbolos); i--; } else if (s[i] == ’(’) { topo = emp_char(topo,’(’); } else if (s[i] == ’)’) { while (topo != NULL && topo->simbolo != ’(’){ simbolos[0] = des_char(&topo); simbolos[1] = ’\0’; insere_pos(&ini,&fim,simbolos); } des_char(&topo); /* joga fora ’(’ */ } else if (s[i] == ’*’ || s[i] == ’/’) { while (topo != NULL && topo->simbolo != ’(’ && topo->simbolo != ’+’ && topo->simbolo != ’-’){ simbolos[0] = des_char(&topo); simbolos[1] = ’\0’; insere_pos(&ini,&fim,simbolos); } topo = emp_char(topo,s[i]); } else if (s[i] == ’+’ || s[i] == ’-’) { while (topo != NULL && topo->simbolo != ’(’){ simbolos[0] = des_char(&topo); simbolos[1] = ’\0’; insere_pos(&ini,&fim,simbolos); } topo = emp_char(topo,s[i]); } else if (s[i] == ’ ’); else { printf("Expressão infixa inválida!\n"); exit(1); } }

/* desempilha todos os operadores que restaram */ while (topo != NULL){

aulas.txt Seg Nov 28 17:00:12 2005 32

simbolos[0] = des_char(&topo); simbolos[1] = ’\0’; insere_pos(&ini,&fim,simbolos); }

return ini;}

int calcula_posfixa(posfixa *ini){ valores *topo; int valor1, valor2, valor; char *s;

topo = NULL; while (ini != NULL){ s = remove_pos(&ini); switch (s[0]){ case ’+’: valor1 = des_val(&topo); valor2 = des_val(&topo); topo = emp_val(topo, valor1+valor2); break; case ’*’: valor1 = des_val(&topo); valor2 = des_val(&topo); topo = emp_val(topo, valor1*valor2); break; case ’-’: valor1 = des_val(&topo); valor2 = des_val(&topo); topo = emp_val(topo, valor2-valor1); break; case ’/’: valor1 = des_val(&topo); valor2 = des_val(&topo); topo = emp_val(topo, valor2/valor1); break; default: /*sscanf(ini->s,"%d",&valor);*/ valor = atoi(s); topo = emp_val(topo,valor); break; } free(s); } valor = des_val(&topo); if (topo != NULL){ printf("Erro em expressao posfixa\n"); exit(-1); } return valor;}

valores *emp_val(valores *topo, int n){ valores *nova; nova = malloc(sizeof(valores)); if (nova == NULL){ printf("Erro Memoria\n"); exit(-1); } nova->valor = n;

aulas.txt Seg Nov 28 17:00:12 2005 33

nova->prox = topo; return nova;}

int des_val(valores **topo){ valores *aux; int valor;

if (*topo == NULL){ printf("Erro na pilha de valores\n"); exit(-1); } aux = *topo; valor = aux->valor; *topo = (*topo)->prox; free(aux); return valor;}

void insere_pos(posfixa **ini, posfixa **fim, char *s){ posfixa *nova;

nova = malloc(sizeof(posfixa)); if (nova == NULL){ printf("Erro Memoria\n"); exit(-1); } strcpy(nova->s,s); nova->prox = NULL; if (*ini == NULL){ *ini = nova; } else (*fim)->prox = nova; *fim = nova;}

char *remove_pos(posfixa **ini){ posfixa *aux; char *s;

if (*ini == NULL){ printf("Erro em expressao posfixa\n"); exit(-1); } s = malloc(strlen((*ini)->s)*sizeof(char)); strcpy(s,(*ini)->s); aux = *ini; *ini = (*ini)->prox; free(aux);

return s;}

pilha_aux *emp_char(pilha_aux *topo, char c){ pilha_aux *nova;

nova = malloc(sizeof(pilha_aux)); if (nova == NULL){

aulas.txt Seg Nov 28 17:00:12 2005 34

printf("Erro Memoria\n"); exit(-1); } nova->simbolo=c; nova->prox = topo; return nova;}

char des_char(pilha_aux **topo){ pilha_aux *aux; char c;

if (*topo == NULL){ printf("Erro na expressao infixa\n"); exit(-1); } aux = *topo; c = aux->simbolo;

*topo = (*topo)->prox; free(aux); return c;}

**********************************************************************

Listas com cabeça

O valor da primeira célula é irrelevante: ela serve apenas para marcaro início da lista. O endereço da primeira célula nunca muda. Issofacilita a implementação de algumas funções.

typedef struct _celula_ { int valor; struct cel *prox;} celula;

Lista com 3 células:

|_|

|___|___| -> |___|___| -> |___|___| -> |___|___| cabeçavalor faz parte da lista

Exemplos:

Inicialização da lista (vazia)

celula *inicio;

inicio = malloc (sizeof (celula)); if (inicio == NULL) { printf("Sem memoria\n"); exit(1); } inicio->prox = NULL;

/* Insere celula com valor n no inicio da lista devolve endereco do início da nova lista ou NULL se nao foi possivel fazer a insercao

aulas.txt Seg Nov 28 17:00:12 2005 35

*/celula *insere(celula *inicio, int n){ celula *nova;


if (nova == NULL) return NULL;

nova->valor = n; nova->prox = inicio;

return nova;}

/* Lista sem cabeça Remove, se existir, celula com valor n Devolve lista sem a celula, com valor de inicio possivelmente alterado*/celula *Remove(celula *inicio, int n){ celula *corrente, *ant;

corrente = inicio; ant = NULL;


if (corrente == NULL) /* n nao foi encontrado */ return inicio;

if (ant == NULL) /* n esta no inicio */ inicio = inicio->prox; else ant->prox = corrente->prox;

free(corrente); return inicio;}

/* Lista com cabeça Remove, se existir, celula com valor n*/void Remove(celula *inicio, int n){ celula *corrente, *ant;

corrente = inicio->prox; ant = inicio;


if (corrente != NULL) {/* n foi encontrado */ ant->prox = corrente->prox; free(corrente);

aulas.txt Seg Nov 28 17:00:12 2005 36

}}**********************************************************************

/* Inverte lista */celula *inverte(celula *inicio){ celula *ant, *cor, *prox;

if (inicio == NULL || inicio ->prox == NULL) return inicio;

ant = inicio; cor = ant->prox; prox = cor->prox; ant->prox = NULL;

while (prox != NULL) { cor->prox = ant; ant = cor; cor = prox; prox = prox->prox; } cor->prox = ant;

return cor;}

celula *inverteR(celula *inicio){ celula *aux, *fim;

if (inicio == NULL || inicio ->prox == NULL) return inicio;

fim = inicio;

aux = inicio ->prox;

inicio = inverteR(inicio->prox);

aux->prox = fim; fim->prox = NULL;

return inicio;}

**********************************************************************

Exercício:

Concatenar duas listas com valores ordenados, mantendo a listaresultante ordenada

**********************************************************************

Busca em vetor [Intro a Análise de Algoritmos]

Dados x e um vetor v[0], v[1], ..., v[n-1], determinar se x ocorre novetor e, em caso positivo, qual índice i para o qual v[i] = x

Busca sequencial

aulas.txt Seg Nov 28 17:00:12 2005 37

/* devolve i se existe i tal que v[i] = x devolve -1 caso contrário.*/int ocorre(int x, int n, int v[]){ int i; i = 0; while (i < n && v[i] != x) i++; if (i < n) return i; else return -1;}

Número de operações no pior caso --- x não ocorre no vetor: 1 (atribuição) i = 0 n+1 comparações i < n (while) n comparações v[i] != x n atribuições i++ 1 comparação i < n (if)

Total: n+1 atribuições 2n+1 comparações

Número de operações proporcional a n

Busca binária: vetor ordenado

/* devolve i se existe i tal que v[i] = x devolve -1 caso contrário.*/

int buscabinaria(int x, int n, int v[]){ int e, m, d;

e = 0; d = n-1; while (e <= d) { m = (e + d)/2; if (v[m] == x) return m; if (v[m] < x) e = m+1; else d = m-1; } return -1;}

Cada vez que o while é executado, o valor de "d-e" é no máximo ametade do valor anterior. O valor inicial de "d-e" é n-1. Onúmero de vezes que n pode ser dividido por 2 a ainda se manter maiorou igual a 1 é aproximadamente log n. Portanto, o número de operaçõesexecutadas pela função é proporcional a log n.Uma análise detalhada é mais confusa e, como veremos, desnecessária.

**********************************************************************

Análise de Algoritmos

Queremos prever o comportamento de algoritmos em função do tamanhoda entrada. O importante é considerar entradas do tamanho "grande":

aulas.txt Seg Nov 28 17:00:12 2005 38

para entradas de tamanho pequeno qualquer solução é rápida.

Tamanho da entrada: torres de hanói: número de discos busca em vetores: número de elementos no vetor curvas de Koch: ordem e tamanho da figura

----------------------------------------------------------------------

Notação assintótica

Elimina constantes multiplicativas e termos com contribuiçãodesprezível quando n se torna grande

log_2 n n n^2/2 n/2 (n^2+n)/2 2^n

3,3 10 50 5 55 1.024 6,6 100 5.000 50 5.050 1,3x10^{30} 10,0 1.000 500.000 500 500.500 1,1x10^{301} 13,3 10.000 50.000.000 5.000 50.005.000 infinito 16,6 100.000 5.000.000.000 50.000 5.000.050.000 ^ computacionalmente inviável ___/

Dizemos que (n^2+n)/2 é O(n^2)

Eliminamos constantes multiplicativas: (a) padrão de crescimento é o mesmo (b) na análise de tempo as constantes podem ser alteradas pelo aumento de velocidades das CPU’s (c) velocidades são diferentes para operações diferentes

Eliminamos termos com contribuição assintótica desprezível: estamosenteressados em valores grandes de n.

IMPORTANTE: esse tipo de análise tem se mostrado útil

Definição formal:

Dizemos que g(n) é O(f(n)) se existem constantes positivas c e n_0tal que g(n) <= c.f(n) para todo n >= n_0

Notação: g(n) = O(f(n))

Exemplo: Para n >= 1

(n^2+n)/2 <= (n^2+n^2)/2 = n^2

(n_0 = 1 e c = 1)

**********************************************************************

Ordenação

Ordenação por seleção: 1. seleciona o maior e coloca na última posição do vetor. 2. seleciona o segundo maior e coloca na penúltima posição do vetor. ..../* Rearranja o vetor v[0..n-1] em ordem crescente.*/

void selecao(int n, int v[])

aulas.txt Seg Nov 28 17:00:12 2005 39

{ int i, indice;

for (i = n; i > 1; i--) { indice = maior(i, v); troca(v, indice, i-1); }}

/* Devolve o indice do maior elemento de v */int maior(int n, int v[]){ int i, indice;

indice = 0;

for (i = 1; i < n; i++) if (v[i] > v[indice]) indice = i;

return indice;}

/* troca v[i] com v[j] */void troca(int v[], int i, int j){ int aux;

aux = v[i]; v[i] = v[j]; v[j] = aux;}

Número de operações:

-- O número de operações da função maior é proporcional a n -- O número de operações da função troca é constante -- Número de operações da função seleção: em cada execução do "for" o número de operações é proporcional a i (função maior) mais uma constante (função troca) O total de operações, considerando i = n, n-1, ..., 2, 1 é proporcional a n + n-1 + n-2 + n-3 + ... + 2 + 1 = (n+1)n/2 = O(n^2)

----------------------------------------------------------------------

Ordenação por inserção:

1. ordenamos uma segmento inicial do vetor 2. fazemos a inserção do próximo elemento em sua posição correta

void insercao(int n, int v[]){ int i, j, x;

for (i = 1; i < n; i++) { /* segmento v[0], v[1], ..., v[i-1] já ordenado */ x = v[i]; j = i - 1; while (j >= 0 && x < v[j]) { v[j+1] = v[j]; j--; } v[j+1] = x; }}

aulas.txt Seg Nov 28 17:00:12 2005 40

Número de operações: -- O número de operações do "for" mais externo é proporcional a i -- O número total de operação é proporcional a 1 + 2 + 3 + .. + n-2 + n-1 + n = (n+1)n/2 = O(n^2)

Já ordenados_________________|3 7 9 16 17 | 8 -2 5 12-----------------**********************************************************************

Mergersort

Ordenação por intercalação

início = fim = 5 --\

[56] [25] [37] [58] [95] [19] [73] [30]

inicio = 4 fim = 5 [25 56] [37 58] [19 95] [30 73]

inicio = 0 fim = 3 inicio = 4 fim = 7 [25 37 56 58] [19 30 73 95]

inicio = 0 fim = 7 [19 25 30 37 56 58 73 95]

void mergesort(int *v, int inicio, int fim){ int meio;

if (inicio < fim){ meio = (inicio + fim)/2; mergesort(v, inicio, meio); mergesort(v, meio+1, fim); intercala(v, inicio, meio, fim); }}

/* Copia v[inicio], ...,v[meio] em w[0], ..., w[meio-inicio] e depois intercala w[0], ..., w[meio-inicio] com v[meio+1], ..., v[fim] colocando o resultado da intercalacao em v[inicio], ..., v[fim]*/void intercala(int *v, int inicio, int meio, int fim){ int *w; int i, j, k, n;

n = meio - inicio + 1; w = alocavetor(n);

for (i=0; i < n; i++) w[i] = v[i+inicio];

k = inicio; i = 0; j = meio+1;

while (i < n && j <= fim){ if (w[i] < v[j]) v[k++] = w[i++];

aulas.txt Seg Nov 28 17:00:12 2005 41

else v[k++] = v[j++]; }

while (i < n) v[k++] = w[i++];

free(w);}

inicio --\ /-- meio /-- fimEntrada [ ] [ ] [ ] [ ] ordenado ordenado

inicio --\ /-- fimSaída [ ] [ ] [ ] ordenado

----------------------------------------------------------------------

Análise do Mergesort

Análise do intercala: número de operações proporcional a fim - início + 1

___________________________________________________________| |----------------------------------------------------------- n O(n)_____________________________ _____________________________| | | |----------------------------- ----------------------------- 2n/2 O(n)______________ ______________ _______________ _____________| | | | | | | |-------------- -------------- --------------- ------------- 4n/4 O(n)

8n/8 O(n) . . .

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | - - - - - - - - - - - - - - -

O(log_2 n) níveis: número total de operações O(nlog n)

********************************************************************** n Tempos de ordenacao selecao insercao mergesort quicksort 2000 0.04 0.02 0.01 0.00 4000 0.16 0.10 0.01 0.01 8000 0.68 0.44 0.03 0.01 16000 2.83 1.90 0.05 0.02 32000 11.53 8.05 0.10 0.04 64000 48.58 35.22 0.20 0.09 128000 261.17 183.23 0.42 0.19**********************************************************************

Quicksort

[25 37 58 95 19 73 30 56]

aulas.txt Seg Nov 28 17:00:12 2005 42

[25 37 19 30 | 56 58 95 73]

menores maiores

[19 25 30 37 | 56 58 73 95]

menores maiores ordenados ordenados

[25 37 19 30 | 56 | 58 95 73] <= 56 pivô >= 56

Quicksort

1. Escolha um pivô2. Rearranje ios elementos do vetor de forma a deixar os menores do que o pivô no início e os maiores no fim.3. Ordene o início e fim do vetor

----------------------------------------------------------------------

Partição

i j pivô 25 37 58 95 19 73 30 | 56 |

i j 25 | 37 58 95 19 73 30 | 56 |

i j 25 37 | 58 95 19 73 30 | 56 |

i j 25 37 | 58 95 19 73 30 | 56 |

i j 25 37 | 58 95 19 73 30 | 56 |

i j 25 37 19 | 95 58 73 30 | 56 |

i j 25 37 19 | 95 58 73 30 | 56 |

i 25 37 19 30 | 58 73 95 | 56 |

i 25 37 19 30 | 56 | 73 95 58 | ^ limite -/

/* ordena crescentemente v[inicio], ..., v[fim] */void quicksort(int *v, int inicio, int fim){ int limite;

if (inicio < fim){ limite = particiona(v, inicio, fim); quicksort(v, inicio, limite-1); quicksort(v, limite+1, fim);

aulas.txt Seg Nov 28 17:00:12 2005 43

}}

/* Escolhe v[fim] como pivô, rearranja vetor e devolve limite tal que v[limite] = pivo e para k < limite vale que v[k] <= pivô e para k > limite vale que v[k] > pivo*/int particiona(int *v, int inicio, int fim){ int pivo, i, j, aux;

i = inicio - 1; pivo = v[fim]; for (j = inicio; j < fim; j++) { if (v[j] <= pivo) { i++; aux = v[i]; v[i] = v[j]; v[j] = aux; } }

v[fim] = v[i+1]; v[i+1] = pivo; return i+1;}

i j fim 2 8 7 1 3 5 6 4

i j fim 2 8 7 1 3 5 6 4

i j fim 2 8 7 1 3 5 6 4

i j fim 2 8 7 1 3 5 6 4

i j fim 2 1 7 8 3 5 6 4

i j fim 2 1 3 8 7 5 6 4

i j fim 2 1 3 8 7 5 6 4

i fim 2 1 3 8 7 5 6 4

i fim 2 1 3 4 7 5 6 8

----------------------------------------------------------------------

Número de operações do quicksort

- pior caso: O(n^2) [seqüência ordenada] - caso médio: O(nlog n) - melhor algoritmo prático conhecido para ordenação

aulas.txt Seg Nov 28 17:00:12 2005 44

**********************************************************************

Heapsort

16 Índices do vetor começam no 1 / \ 14 10 vetor [16 14 10 8 7 9 3 2 4 1] / \ / \ 8 7 9 3 / \ /3 4 1

Propriedade: v[i] >= v[2i] v[i] >= v[2i+1]

Conseqüência: maior elemento é v[1]

Correção da propriedade do heap:

16 / \ 4 10 / \ / \ 14 7 9 3 / \ /3 4 1

/* Subárvores nas posições 2i e 2i+1 são heaps A função rearranja o vetor de forma que a subárvore na posição i é um heap*/

void acerta_heap(int v[], int i, int n){ int maior, aux;

if (2*i <= n && v[2*i] > v[i]) maior = 2*i; else maior = i; if (2*i + 1 <= n && v[2*i+1] > v[maior]) maior = 2*i + 1; if (maior != i) { aux = v[i]; v[i] = v[maior]; v[maior] = aux; acerta_heap(v, maior, n); }}

void heapsort(int v[], int n){ int i, aux;

for (i = n/2; i >= 2; i--) acerta_heap(v, i, n);

for(i = n; i >= 2; i--) { acerta_heap(v, 1, i); aux = v[i];

aulas.txt Seg Nov 28 17:00:12 2005 45

v[i] = v[1]; v[1] = aux; }}

----------------------------------------------------------------------

Análise do heapsort

Número de operações do acerta_heap: proporcional a log n operações

Número de chamadas do acerta_heap: proporcional a n

Total: O(nlogn)

Melhor que o mergesort e pior que o quicksort na prática e melhor queo quicksort no pior caso do quicksort.

**********************************************************************

Árvore binária

A A pai de B e C / \ B e C filhos de A sub-árvore B Ccom raiz B / \ \ D E F <--- folha

typedef struct _arvore_ { int valor; struct _arvore_ *pai, *esq, *dir;} arvore;

----------------------------------------------------------------------

Visita E-R-D

5 / \ 3 8 / \ / \ 1 4 6 9 / \ \0 2 7

/* Imprime valores da arvore na ordem esquerda-raiz-direita */void erd(arvore *raiz){ if (raiz != NULL){ erd(raiz->esq); printf("%d ",raiz->valor); erd(raiz->dir); }}----------------------------------------------------------------------

Altura de uma árvore: maior comprimento da raiz até alguma folha

aulas.txt Seg Nov 28 17:00:12 2005 46

5 altura 0 5 altura = 3 / \ 3 8 / / \ 1 6 9 \ 7

/* devolve altura de uma arvore */int altura(arvore *raiz){ int he, hd; if (raiz == NULL) return (-1); /* altura de árvore vazia é -1 */ else { he = altura (raiz->esq); hd = altura (raiz->dir); if (he < hd) return (hd + 1); else return (he + 1); }}

----------------------------------------------------------------------

Número mínimo de células numa árvore de altura h:

O \ O n = h + 1 \ 0 . 0 \ 0

Máximo: 2^{h+1} - 1

0 / \ s1 s2

n = n1 + n2 = 2^{h} - 1 + 2^{h} - 1 + 1 = 2^{h+1} - 1

h ˜ log_{2}n

----------------------------------------------------------------------

Árvore de busca binária

5 2 / \ x \ 3 7 / \ 3 / \ \ todos > x todos < x \ 2 4 8 7 / \ 5 8 Valores distintos / 4

aulas.txt Seg Nov 28 17:00:12 2005 47

----------------------------------------------------------------------

Busca

/* Busca celula com valor n em uma arvore de busca binaria; * devolve NULL caso nao exista tal celula */arvore *busca(arvore *raiz, int n){ if (raiz == NULL || n == raiz->valor) return raiz; if (n < raiz->valor) return busca(raiz->esq,n); else return busca(raiz->dir,n);}

----------------------------------------------------------------------

Mínimo e máximo

/* Acha a celula de valor minimo de uma arvore de busca binaria */arvore *minimo(arvore *x){ if (x == NULL) return NULL; while (x->esq != NULL) x = x->esq; return x;}

/* Acha a celula de valor maximo de uma arvore de busca binaria */arvore *maximo(arvore *x){ if (x == NULL) return NULL; while (x->dir != NULL) x = x->dir; return x;}

----------------------------------------------------------------------

Sucessor de uma célula x: célula y com menor y->valor tal quey->valor > x->valor

15 / \ 6 18 / \ / \ 3 7 17 20 / \ \2 4 13 / 9

sucessor(x): mínimo de x->dir ou (caso x->dir == NULL) primeiroancestral y com y->valor > x->valor

/* Encontra a célula sucessora da celula x em uma arvore de busca binaria * devolve NULL se a x->valor é máximo */arvore *sucessor(arvore *x);

aulas.txt Seg Nov 28 17:00:12 2005 48

{ arvore *y;

if (x == NULL) return NULL; if (x->dir != NULL) return minimo(x->dir); y = x->pai;---------------------------------------- while (y != NULL && x == y->dir){ x = y; y = y->pai; }---------------------------------------- while (y != NULL && y->valor < x->valor){ (alternativa) y = y->pai;---------------------------------------- return y;}

----------------------------------------------------------------------

Inserção

/* Insere nova celula com valor n em uma arvore de busca binaria * devolve nova raiz da arvore */arvore *insercao(arvore *raiz, int n){ arvore *nova, *ant, *aux;

nova = malloc(sizeof(arvore)); if (nova == NULL){ printf("Erro memoria\n"); exit(-1); } nova->valor = n; nova->pai = nova->esq = nova->dir = NULL; if (raiz == NULL) return nova; /* arvore estava vazia; nova agora e’ a raiz */ aux = raiz; while (aux != NULL){ ant = aux; if (n < aux->valor) aux = aux->esq; else aux = aux->dir; } nova->pai = ant; if (n < ant->valor) ant->esq = nova; else ant->dir = nova; return raiz; /* raiz nao mudou */}

----------------------------------------------------------------------

Remoção 3 casos

Caso 1: z não tem filhos

15 15

aulas.txt Seg Nov 28 17:00:12 2005 49

/ \ / \ 5 16 5 16 / \ / \ 3 12 ------> 3 12 / \ / 10 13 z 10

Caso 2: z tem apenas 1 filho

15 15 / \ / \ 5 16 z 5 20 / \ \ / \ / \ 3 12 20 ------> 3 12 18 23 / \ 18 23

Caso 3: z tem dois filhos - y, sucessor de z, tem no máximo 1 filho (o direito) y é removido e seu valor copiado em z

y - célula a ser removidaCasos 1 e 2: y é o próprio zCaso 3: sucessor de zx - filho de y; pode ser NULL

/* Remove celula apontada por z de uma arvore de busca binaria * devolve nova raiz da arvore */arvore *remocao(arvore *raiz, arvore *z){ arvore *y, *x;

/* determinacao de y que sera’ removido */ if (z->esq == NULL || z->dir == NULL) /* z tem 0 ou 1 filho; y é o proprio z */ y = z; else{ y = sucessor(z); /* z tem 2 filhos; y é o sucessor de z */ z->valor = y->valor; } Situações possíveis /* determinacao do filho de y */ if (y->esq != NULL) y->pai O O y->pai x = y->esq; / \ else y O 0 y y 0 raiz x = y->dir; / / / /* acerta o apontador de x, o filho de y */ x x x if (x != NULL) tanto faz se x->pai = y->pai; x é filho esq ou dir /* acerta o apontador do pai de y */ if (y->pai == NULL) raiz = x; /* y é raiz e sera’ removido */ else /* y nao é raiz */ if (y == y->pai->esq) /* y é filho esquerdo? */ y->pai->esq = x; else y->pai->dir = x;

free(y); return raiz;}

**********************************************************************

aulas.txt Seg Nov 28 17:00:12 2005 50

Backtracking

Para muitos problemas o processo de solução consiste em a cada passotomar uma decisão dentre um certo número de possibilidade. Se asdecisões são boas, uma solução é encontrada. Se ficar claro que algumadecisão errada foi tomada, essa decisão é alterada e se tentanovamente encontrar a solução.

Labirinto

----------- ----------- ----------- ----------- ----------- | ----- | | ----- | | ----- | | ----- | | ----- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- | | | -- X| | | -- | | | -- | | | -- | | | X| | | 0| | | 0X | | 0| | | X0| | | _ | | _ | | _ | | _ X | | _ | | | | | | | | | | | | | | | | | ------ | ------ | ------ | ------ | ------

Objetivo: sair do labirintoDecisões: andar Norte, Leste, Sul ou Oeste.

A posição marcada com ’0’ indica uma posição já visitada.

Casos simples: 1. A posição está fora do labirinto: a saída foi encontrada. 2. A posição é parede 3. A posição já está marcada com ’0’

Caso Geral: 1. Marque a posição com ’0’ 2. Tente cada um dos 4 possíveis movimentos 3. Se algum movimento der certo, pare com a solução e devolva 1 (recursão) 3. Caso nenhum movimento leva à solução, desmarque a posição e devolva 0

Função recursiva para Labirinto

1. Se a posição está fora do labirinto, deolva 1 (solução encontrada) 2. Se a posiçã0 está marcada ou é parede, devolva 0 (solução impossível) 3. Marque a posição com ’0’ 4. Chame a função recursivamente para movimento ao Norte (depois Leste, Sul e Oeste); se 1 é devolvido, então devolva 1 5. Desmarque a posição 6. Devolva 0

Exemplo de funcionamento para o labirinto acima

----------------------------------------------------------------------

Problemas das n rainhas

Colocar, se possível, n rainhas em um tabuleiro nXn sem que duas delasse ataquem

Idéia: uma rainha para cada linha. Na linha, todas as colunas são tentadas.

Exs para n=2, n=3, n=4

aulas.txt Seg Nov 28 17:00:12 2005 51

Representação do tabuleiro: matriz de char com ’ ’ ou ’R’ em cada entrada.

/* Programa para resolver o problema das n rainhas num tabuleiro nXn */#include <stdio.h>#include <stdlib.h>

char **alocamatriz(int m, int n);void libera(char **tab, int m);int colocarainhas(char **tab, int x, int y, int n);int atacada(char **tab, int x, int y, int n);void impressao(char **tab, int m, int n);

int main(){ int n, i, j; char **tab;

printf("Tamanho do tabuleiro: "); scanf("%d",&n); tab = alocamatriz(n, n); if (tab == NULL){ printf("Leitura nao pode ser feita\n"); return 1; }

for (i = 0; i < n; i++) for (j = 0; j < n; j++) tab[i][j] = ’ ’;

if (colocarainhas(tab, 0, 0, n)) impressao(tab,n,n); else printf("problema sem solucao\n");

libera(tab,n); return 0;}

void impressao(char **tab, int m, int n){ int i, j;

for (i = 0; i < m; i++){ for (j = 0; j < n; j++) printf("|%c", tab[i][j]); printf("|\n"); }}

/* Tenta colocar as rainhas x, x+1, ..., n-1 nas linhas x, x+1, ..., n-1 * a partir da posicao (x,y) * Devolve 1 se deu para colocar * Devolve 0 caso contrario */int colocarainhas(char **tab, int x, int y, int n){ /* coluna válida? */ if (y == n) return 0;

/* posição atacada? */ if (atacada(tab,x,y,n)) return colocarainhas(tab,x,y+1,n);

aulas.txt Seg Nov 28 17:00:12 2005 52

tab[x][y] = ’R’;

/* última rainha? */ if (x == n-1) return 1;

/* Faltam rainhas... */ if (colocarainhas(tab,x+1,0,n)) return 1;

/* Não deu. Vamos tentar próxima coluna */ tab[x][y] = ’ ’;

return colocarainhas(tab, x, y+1, n);

}

char **alocamatriz(int m, int n){ char **tab; int i, j;

tab = malloc(m*sizeof(char *)); if (tab == NULL) return NULL;

for (i = 0; i < m; i++){ tab[i] = malloc(n*sizeof(char)); if (tab[i] == NULL){ for (j = 0; j < i; j++) free(tab[j]); free(tab); return NULL; } } return tab;}

void libera(char **tab, int m){ int i;

for (i=0; i < m; i++) free(tab[i]); free(tab);}

/* Verifica se a posicao (x,y) esta’ atacada por alguma das rainhas colocadas nas * linhas 0, 1, .., x-1 * Devolve 1 caso a posicao esteja atacada; devolve 0 caso contrario */int atacada(char **tab, int x, int y, int n){ int i;

/* Verifica coluna */ for (i = 0; i < x; i++) if (tab[i][y] == ’R’) return 1;

/* Verifica uma diagonal */ for (i = 0; x-i >= 0 && y-i >= 0; i++) if (tab[x-i][y-i] == ’R’) return 1;

aulas.txt Seg Nov 28 17:00:12 2005 53

/* Verifica outra diagonal */ for (i = 0; x - i >= 0 && y+i < n; i++) if (tab[x-i][y+i] == ’R’) return 1;

return 0;}

********************************************************************** Busca de palavras em texto

Determinar o número de ocorrências de uma palavra em um texto.

Dados: um vetor p com m caracteres um vetor t com n caracteres

Exemplo: p = ANA t = ANA E MARIANA GOSTAM DE BANANA

Número de ocorrências: 4

Idéia: 1. Compara p com cada posição de t, da esquerda para a direita.2. Para comparar p com uma posição k de t, compara da direita para aesquerda. Ou seja, compara p[m-1] com t[k-1], depois p[m-2] com t[k-2]etc.

_____________________________________________________________________

/* Recebe vetores p com m >= 1 caracteres e vetor t com n >= 0 caracteres e devolve o número de ocorrências de p em t.*/

int trivial (unsigned char p[], int m, unsigned char t[], int n){ int i, k, ocorre = 0; for (k = m; k <= n; k++) { for (i = 1; i <=m && p[m-i] == t[k-i]; i++); if (i == m+1) ocorre++; } return ocorre;}

Número de comparações O(mn)

_____________________________________________________________________

Algoritmo de Boyer-Moore (primeira versão)

Comparar posição k com e depois a posição k+d para algum d.

Exemplo: p = B C B A

t = X C B A B X C B A A X B C B A B X ^ ^ ^ ^ ^ ^valores de d 2 3 1 5 2

Idéia: olhar t[k] e encontrar o último caractere em p que casa comt[k].

aulas.txt Seg Nov 28 17:00:12 2005 54

No exemplo: p= 0 1 2 3 B|C|B|A

t = X C B A B X ... ^ k-1 t[k] casa com p[2]: avança 2_____________________________________________________________________

t = ... B A B X C B ... ^ k-1

t[k] casa com p[1]: avança 3

_____________________________________________________________________

t = ...X C B A A X B ... ^ k-1

t[k] casa com p[3]: avança 1

_____________________________________________________________________

t = ... C B A A X B ... ^ k-1 t[k] não casa com nada em p: avança 5____________________________________________________________________

Se t[k] casa com p[i] avança m - i posições

Se t[k] não aparece em p avança, fazemos i = -1_____________________________________________________________________

0 1 2 3 B|C|B|A

l ... > ? @ A B C D E F ... <- ASCIIult[l] ... -1 -1 -1 -1 3 2 1 -1 -1 ...

_____________________________________________________________________

O uso do unsigned garante que código ASCII usará valore de 0..255[poderia ser de -128..127]

/* Recebe vetores p com m>= 1 caracteres e vetor t com n >= 0 caracteres e devolve o número de ocorrências de p em t.*/int boyermoore1 (unsigned char p[], int m, unsigned char t[], int n){ int ult[256]; int i, k, ocorre;

/* pré-processamento do padrão p */ for (i = 0; i < 256; ++i) ult[i] = -1; for (i = 0; i < m; ++i) ult[p[i]] = i;

/* busca do padrão p no texto t */

aulas.txt Seg Nov 28 17:00:12 2005 55

ocorre = 0; k = m; while (k <= n) { for (i = 1; i <=m && p[m-i] == t[k-i]; i++); if (i == m+1) ocorre++;

if (k < n) k += m - ult[t[k]]; else k++; /* sai do while */ } return ocorre;}

Número de comparações O(mn)

_____________________________________________________________________

Algoritmo de Boyer-Moore (segunda versão)

Comparando posição k de t com p, podemos tirar proveito se já sabemosque as últimas posições de p casam na posição k de t.

Exemplo: p = D E S C A S C A

t = F U I À C A S A D E S C A S C A R B A T A T Acomparação D E S C A S C Apróxima D E S C A S C A

comparação D E S C A S C Apróxima D E S C A S C A

Como computar esses pulos?

pulo[i] = número de posições que pode ser avançado se os últimos i+1 são iguais: p[m-1] == t[k-1], p[m-2] == t[k-2], ..., p[m-i+1] == t[k-i+1]

0 1 2 3 4 5 i 0 1 2 3 4 5C A A B A A pulo[i] 1 3 6 6 6 6

0 1 2 3 4 5 6 7 i 0 1 2 3 4 5 6 7B A - B A . B A pulo[i] 3 3 6 6 6 6 6 6

0 1 2 3 4 5 6 7 8 9 10 i 0 1 2 3 4 5 6 7 8 9 10B A - B A * B A * B A pulo[i] 3 3 3 3 3 9 9 9 9 9 9

/* pulo[i] = número de posições que pode ser avançado se os últimos i+1 são iguais: p[m-1] == t[k-1], p[m-2] == t[k-2], ..., p[m-i-1] == t[k-i-1]

pulo[i] = menor inteiro j tal que

... p[m-i-1] p[m-i] ... p[m-3] p[m-2] p[m-1] ... p[m-i-1-j] p[m-i-j] ... p[m-3-j] p[m-2-j] p[m-1-j] ...ou ... p[m-i+1] p[m-i+2] ... p[m-k] ... p[m-2] p[m-1] p[0] ... p[m-2-j] p[m-1-j] ...ou

aulas.txt Seg Nov 28 17:00:12 2005 56

pulo[i] = m se não existe j nas condições acima*/

int *calcula_pulo(unsigned char p[], int m){ int *pulo; int i, j, k;

pulo = alocavetor(m); if (pulo == NULL) { printf("Sem memoria\n"); exit (1); }

for (i = 0; i < m; i++) { /* determina p[i] */ pulo[i] = m; j = 1; while (j < m) { /* j e’ candidato a p[i] */ for (k = 0; m-i-1 <= m-1-k && m-1-j-k >= 0 && p[m-1-k] == p[m-1-j-k]; k++); if (m-i-1 > m-1-k || m-1-j-k < 0) { pulo[i] = j; break; } j++; } }

for (i = 0; i < m; i++) printf("Pulo[%d] = %d\n", i, pulo[i]);

return pulo;}

/* Recebe uma palavra a[1..m] com 1 <= m <= MAXm e um texto b[1..n] e devolve o número de ocorrências de a em b.*/

int boyermoore2 (unsigned char p[], int m, unsigned char t[], int n){ int *pulo; int i, k, ocorre;

/* pré-processamento do padrão p */ pulo = calcula_pulo(p, m);

/* busca do padrão p no texto t */ ocorre = 0; k = m; while (k <= n) { for (i = 1; i <=m && p[m-i] == t[k-i]; i++); if (i == m+1) ocorre++;

if (k < n && i > 1) k += pulo[i-2]; else k++; } return ocorre;}

aulas.txt Seg Nov 28 17:00:12 2005 57

**********************************************************************

Algoritmos de Enumeração

Geração dos subconjuntos de {1,2,3}{}, {1}, {2}, {3}, {1,2}, ...11 21 2 31 322 33

Estratégia: - subconjuntos representados em um vetor s - tamanho corrente do vetor: i+1 - soma 1 em s[i]. Se s[i] <= n, imprime o subconjunto e coloca mais um elemento no vetor com valor igual ao s[i]; senão, diminui valor de i

s = (0)i = 0, s = (1) imprime e altera s para (1 1)i = 1, s = (1 2) imprime e altera s para (1 2 2)i = 2, s = (1 2 3) imprime e não altera si = 2, s = (1 2 4) diminui valor de ii = 1, s = (1 3) imprime e não altera si = 1, s = (1 4) diminui valor de ii = 0, s = (2) imprime e altera s para (2 2)i = 1, s = (2 3) imprime e altera s para (2 3 3)i = 2, s = (2 3 4) diminui ii = 1, s = (2 4) diminui ii = 0, s = (3) imprime altera s para (3 3)i = 1, s = (3 4) diminui i1 = 0, s = (4) diminui ii = -1, pára

---------------------------------------------------------------------

/* Imprime vetor s com n inteiros */void imprime(int *s, int n){ int i; for(i=0; i < n; i++) printf("%d ",s[i]); printf("\n");}

/* Imprime todos os subconjuntos de {1, 2, ..., n} */void sub(int n){ int *s, i;

s = malloc(n*sizeof(int)); if (s == NULL) { printf("Sem memoria\n"); exit(1); } s[0] = 0; i = 0;

while (i >= 0){ s[i]++;

aulas.txt Seg Nov 28 17:00:12 2005 58

if (s[i] <= n){ imprime(s,i+1); if (i+1 < n){ i++; s[i] = s[i-1]; } } else i--; } free(s);}

---------------------------------------------------------------------

Aplicação: dados um inteiro k>0 e um conjunto de inteiros v = {v_{0},v_{1}, v_{n-1}} imprimir todos os subconjuntos de v cuja soma é k.

/* Imprime o subconjunto de v representado por s se a soma dos elementos do subconjunto é igual a k*/void verifica(int *v, int *s, int m, int k){ int soma, i;

soma = 0;

for(i=0; i < m; i++) soma += v[s[i]-1];

if (soma == k){ for(i=0; i < m; i++) printf("%d ", v[s[i]-1]); printf("\n"); }}

/* Gera os subconjuntos de v e testa para soma igual a k */void soma_sub(int k, int *v, int n){ int *s, i;

s = malloc(n*sizeof(int)); if (s == NULL) { printf("Sem memoria\n"); exit(1); } s[0] = 0; i = 0;

while (i >= 0){ s[i]++; if (s[i] <= n){ verifica(v, s, i+1, k); if (i+1 < n){ i++; s[i] = s[i-1]; } } else i--; }

aulas.txt Seg Nov 28 17:00:12 2005 59

free(s);}

---------------------------------------------------------------------

Geração de Combinações

Dados m e n, imprimir todos os subconjuntos de {1, 2, ..., m} com nelementos.m = 4, n = 2 m = 5 n = 31 2 1 2 31 3 1 2 41 4 1 2 52 3 1 3 42 4 1 3 53 4 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

Estratégia: gerar a próxima combinação a partir da anterior

/* Gera proxima combinacao de m n-a-n, representada no vetor v * Pos: devolve 1 se existe proxima combinacao; 0 caso contrario */int geraproxima(int *v, int m, int n){ int i;

i = n-1; /* encontra v[i] que pode ser aumentado */ while(i >= 0 && v[i] == m-n+i+1) i--;

/* nenhum v[i] pode ser aumentado */ if (i < 0) return 0;

/* aumenta v[i] */ v[i]++; /* preenche resto da combinação */ for (i++; i < n; i++) v[i] = v[i-1]+1;

return 1;}

void comb(int m, int n){ int *v, i,cont=0;

v = malloc(n*sizeof(int)); if (v == NULL) { printf("Sem memória\n"); exit(1); }

/* prepara primeira combinação */ for (i = 0; i < n; i++) v[i] = i+1; printf("%2d: ",++cont);

aulas.txt Seg Nov 28 17:00:12 2005 60

imprime(v,n);

while (geraproxima(v,m,n)){ printf("%2d: ",++cont); imprime(v,n); } free(v);}

void imprime(int *s, int n){ int i; for(i=0; i < n; i++) printf("%d ",s[i]); printf("\n");}

---------------------------------------------------------------------

Geração de permutações

ABC --> ABC ACB BAC BCA CAB CBA

Permutações de "ABCDE"consistem de

- ’A’ seguido de permutações de "BCDE"- ’B’ seguido de permutações de "ACDE"- ’C’ seguido de permutações de "ABDE"- ’D’ seguido de permutações de "ABCE"- ’E’ seguido de permutações de "ABCD"

Estratégia: (para "ABC")

Fixe ’A’ na primeira posição Fixe ’B’ na segunda posição Fixe ’C’ na terceira posição Imprime "ABC" Fixe ’C’ na segunda posição Fixe ’B’ na terceira posição Imprime "ACB"Fixe ’B’ na primeira posição ....Fixe ’C’ na primeira posição ....

Para gerar todas as permutações considerando k caracteres fixos: - para cada possível caractere fixo na posição k+1 gere todas as permutações considerando-se k+1 caracteres fixos

n - número total de caracteresk - número de caracteres fixo

void permutacao(char *v, int n, int k){ se (n == k) imprima v senão { para cada possível caractere fixo na posição k+1 permutação(v, n, k+1) }}

for (i = k; i < n; i++){

aulas.txt Seg Nov 28 17:00:12 2005 61

troca(v, i, k); /* v[k] é o caractere na posição k+1 */ perm(v, n, k+1); troca(v, k, i); }

---------------------------------------------------------------------

/* Imprime as permutacoes de n caracteres, considerando-se os primeiros k caracteres fixos*/

int perm(char v[], int n, int k){

int i, cont;

cont = 1;

if (n == k) { imprima(v,n); return cont; } else for (i=k; i<n; i++){ troca(v,i,k); cont = cont + perm(v,n,k+1); troca(v,k,i); } return cont;}

No programa principal, depois de inicializar v e n: perm(v, n, 0);

**********************************************************************

Outubro Novembro DezembroDo Se Te Qu Qu Se Sá Do Se Te Qu Qu Se Sá Do Se Te Qu Qu Se Sá 1 X 2 X 4 5 P 2 3 2 3 4 5 6 7 8 6 7 X 9 X 11 12 4 5 6 7 P 9 10 9 10 11 12 13 14 15 13 14 15 16 X 18 19 11 12 13 14 15 16 1716 17 18 19 X 21 22 20 21 X 23 X 25 26 18 19 20 21 22 23 2423 24 X 26 X 28 29 27 28 X 30 25 26 27 28 29 30 3130 31

Dezembro 9 ENCERRAMENTO DAS AULAS. 15 Data máxima para cadastro e/ou entrega, pelos docentes, das Listas de Avaliação Final do 2º semestre, nas Unidades.

Minha sugestão:

EP4 - correção até 22/11EP5 - correção até 3/12EP6 - entrega 30/11 correção até 12/12

**********************************************************************

aulas.txt Seg Nov 28 17:00:12 2005 62

Dada uma lista ligada que armazena números inteiros, escreva umafunção que transforma a lista dada em duas listas ligadas: aprimeira contendo os elementos com valores pares e a segunda comvalores ímpares. A função não deve alocar mais células, mas usar asexistentes na lista dada.


/* separa lista em duas lista: com ímpares e com pares */void separa(celula *inicio, celula **impar, celula **par){ celula *aux, *inicimpar, *inicpar;

inicimpar = inicpar = NULL; while (inicio != NULL) { if (inicio->valor % 2 == 0) { aux = inicio; inicio = inicio->prox; aux->prox = inicpar; inicpar = aux; } else { aux = inicio; inicio = inicio->prox; aux->prox = inicimpar; inicimpar = aux; } } *impar = inicimpar; *par = inicpar;}

Chamada no main:

celula *inicio, *par, *impar;

separa(inicio, &impar, &par);

**********************************************************************

Escreva uma função que determina se duas árvores binárias são iguais.

/* A celula da arvore */typedef struct _arvore_ { int valor; struct _arvore_ *pai, *esq, *dir;} arvore;

/* Devolve 1 se as árvores têm os mesmos valores e 0 caso contrário */

int iguais(arvore *x, arvore *y){

if (x == NULL && y == NULL) return 1;

if (x == NULL || y == NULL) return 0;

aulas.txt Seg Nov 28 17:00:12 2005 63

if (x->valor != y->valor) return 0;

return iguais(x->esq, y->esq) && iguais(x->dir, y->dir);

}

**********************************************************************Escreva uma função que recebe um apontador para uma árvorebinária e troca os filhos direito e esquerdo de cada nó.

void troca(arvore *x){ arvore *aux;

if (x != NULL) { troca(x->esq); troca(x->dir); aux = x->esq; x->esq = x->dir; x->dir = aux; }}

**********************************************************************

O vetor abaixo é um heap? Justifique.

i 1 2 3 4 5 6 7 8 9 10 11 v 15 16 32 27 25 30 13 11 39 7 6

Se não for, transforme-o num heap, exibindo o conteúdo do vetor após cadaalteração.

SOLUÇÃO.

Não é um heap pois v[i/2] < v[i] para i = 9, 5, 4, 3 e 2

Construção do heap:

i 1 2 3 4 5 6 7 8 9 10 11 v 15 16 32 27 25 30 13 11 39 7 6 15 16 32 27 25 30 13 11 39 7 6 acerta_heap(v, 5, 11) 15 16 32 39 25 30 13 11 27 7 6 acerta_heap(v, 4, 11) 15 16 32 39 25 30 13 11 27 7 6 acerta_heap(v, 3, 11) 15 39 32 27 25 30 13 11 16 7 6 acerta_heap(v, 2, 11) 39 27 32 16 25 30 13 11 15 7 6 acerta_heap(v, 1, 11)

/* Subárvores nas posições 2i e 2i+1 são heaps A função rearranja o vetor de forma que a subárvore na posição i é um heap*/

void acerta_heap(int v[], int i, int n);

Documents

aulas.txt Seg Nov 28 17:00:12 2005 1 - ime.usp.brhitoshi/mac0122-2012/aulas/aulasJose.pdf · 1. leia instruções "NOVOS USUÁRIOS" 2. como nome e sobrenome use o seu nome e sobrenome,