Departamento de Ciência da Computação - IME - USP

MAC122 Princípios de Desenvolvimento de Algoritmos

Prova 3

QUESTÃO 1

(a) A função valor_pol1 faz 1 soma e 2 multiplicações para cada execução do comando for. No total são n+1 somas e 2(n+1) multiplicações.

A função valor_pol2 faz 1 soma e 1 multiplicação para cada execução do comando for. No total são n+1 somas e n+1 multiplicações.

Portanto, a função valor_pol2 é mais eficiente.

(b) Primeira versão.

float valor_pol3 (int *a, int n, float x_0, int grau)
{
  if (grau == n) return a[n];
  return valor_pol3 (a, n, x_0, grau+1)*x_0 + a[grau];
}

     [...]
     valor = valor_pol3 (a, n, x_0, 0);
     [...]

Segunda versão

float valor_pol4 (int *a, int n, float x_0)
{
  if (n == 0) return a[0];
  return valor_pol4 (&a[1], n-1, x_0)*x_0 + a[0];
}

QUESTÃO 2

/* intercala listas ordenadas p e q */
/* supõe listas sem cabeça */

celula *intercala(celula *p, celula *q)
{
  celula *inicio, *corrente;

  if (p == NULL)
    return q;
  if (q == NULL)
    return p;

  /* determina o início da lista intercalada */
  if (p->valor < q->valor){
    inicio = p;
    p = p->prox;
  }
  else {
    inicio = q;
    q = q->prox;
  }

  /* endereço da última célula da lista intercalada */
  corrente = inicio;

  /* percorre as listas até uma delas terminar */
  while (p != NULL && q != NULL) {
    if (p->valor < q->valor){ /* insere célula de p */
      corrente->prox = p;
      p = p->prox;
    }
    else { /* insere célula de q */
      corrente->prox = q;
      q = q->prox;
    }
    corrente = corrente->prox;
  }

  /* insere sobra de uma das listas */
  if (p != NULL)
    corrente->prox = p;
  else
    corrente->prox = q;

  return inicio;
}

QUESTÃO 3

Lista CONJUNTO *Conj_Uniao(CONJUNTO *lista1, CONJUNTO *lista2)

/* Devolve a união de lista1 e lista2 */
/* supõe listas com cabeça */
CONJUNTO *Conj_Uniao(CONJUNTO *lista1, CONJUNTO *lista2)
{
  CONJUNTO *resp;

  resp = Conj_Cria();           /* conjunto novo, vazio */

  if (resp == NULL) {
    fprintf(stderr, "Sem memoria!\n");
    exit(1);
  }

  /* insere os elementos da lista1 */
  for (lista1 = lista1->prox; lista1 != NULL; lista1 = lista1->prox)
    if (!Conj_Insere(resp, lista1->val)) {
      fprintf(stderr, "Erro!\n);
      exit(1);
    }

  /* insere os elementos da lista2 */
  for (lista2 = lista2->prox; lista2 != NULL; lista2 = lista2->prox)
    if (Conj_Busca(lista1, lista2->val) == NULL)
      if (!Conj_Insere(resp, lista2->val)) {
        fprintf(stderr, "Erro!\n);
        exit(1);
      }

  return resp;
}

Protótipos das funções usadas:

/* construtor de conjuntos;
   devolve apontador para cabeça de lista ou NULL se não foi possível
   alocar memória
*/
CONJUNTO *Conj_Cria();

/* busca v em set;
   devolve apontador para conjunto contendo v ou NULL caso v não
   pertença a set
*/
CONJUNTO *Conj_Busca(CONJUNTO *set, Elem v);

/* insere v em set 
   devolve 1 se inserção foi bem sucedida ou 0 caso contrário
*/
int Conj_Insere(CONJUNTO *set, Elem v);

QUESTÃO 4

/* conta folhas da árvore com raiz x */
int conta_folhas(arvore *x)
{
  /* casos simples: árvore vazia ou com um única célula */
  if (x == NULL)
	return 0;
  if (x->esq == NULL && x->dir == NULL)
	return 1;

  /* caso geral */
  return conta_folhas(x->esq) + conta_folhas(x->dir);
}