MAC0122 Desenvolvimento de Algoritmos

Estruturas de Dados elementares

A vida imita o vídeo,
Garotos inventam um novo inglês,
Vivendo num país sedento
Um momento de embriaguez.
—Somos Quem Podemos Ser, Engenheiros do Hawaii

Este é um resumo da primeira parte do

capítulo 3 (Elementary Data Structures) do livro Algorithms in C, Third Edition de Robert Sedgewick e do
capítulo 2 (Data Types in C) do livro Programming Abstractions in C de Eric Roberts.

Todos os programas foram extraídos desses livros (alguns foram ligeiramente simplificados).

Exercícios preliminares

O seguinte trecho de código promete determinar se é verdade que todos os componentes do vetor a[0..n-1] são positivos.
```
i = 0;
while (a[i] > 0 && i < n) i++;
if (i >= n) printf ("Tudo positivo.");
else printf ("Nem tudo positivo.");
```
Critique o código.

Funções e documentação

Esta seção dá exemplos dos conceitos de função, documentação, e invariantes. Também menciona o mecanismo include da inguagem C. O material está no início da seção 3.1 (Building Blocks) do livro do Sedgewick, em particular no Programa 3.1.

No programa abaixo, a função lg recebe um número inteiro positivo N e devolve o número ⌊log₂ N⌋, ou seja, o piso do logaritmo de N na base 2.

#include <stdio.h>

int lg (int);

// A função main imprime uma tabela dos
// valores de lg(N) e N lg(N) para N = 10^2,
// 10^3, ..., 10^6.
//
int main (void) { 
   int i, N = 10; 
   for (i = 1; i <= 6; i++) {
      N = 10 * N;
      printf("%7d %2d %9d\n", N, lg(N), N * lg(N));
   }
   return 0;
}

// A função lg recebe um inteiro N > 0 e
// devolve piso(log_2 N).
//
int lg (int N) {  
   int i, n;
   i = 0;
   n = N;
   while (n > 1) {
      n = n / 2;
      ++i;
   }
   return i;    
}

`n`	`i`
10 5 2 1	0 1 2 3

Aplique a função lg ao argumento N = 10, por exemplo. A tabela registra os valores das variáveis no início de sucessivas iterações (o início de uma iteração fica imediatamente antes da comparação de n com 1):

Invariante: no começo de cada iteração temos

n = ⌊N/2ⁱ⌋ .

No começo da última iteração temos n = 1, donde 1 ≤ N/2ⁱ < 2, donde 2ⁱ ≤ N < 2ⁱ⁺¹, donde i ≤ log₂ N < i+1. Portanto, a função lg de fato faz o que promete fazer. (A propósito, seria muito útil acrescentar o comentário /* n = N/2^i */ logo depois do while, para ajudar o leitor a entender o que está acontecendo.)

O programa acima também serve para ilustrar o tipo-de-dados int.

Exercícios

O que fazem as seguintes funções? Escreva os invariantes dos processos iterativos.

int lg1 (int N) {  
   int i = 0, n;
   for (n = N; n > 1; n = n/2) 
      ++i;
   return i; }

int lg2 (int N) {  
   int i = 0, n = 1;
   while (n <= N) {
      n = 2 * n;
      ++i;
   }
   return i - 1; }

int lg3 (int N) {  
   int i = 0, n;
   for (n = 2; n <= N; n *= 2) 
      i++;
   return i; }

O que faz a função abaixo? Escreva os invariantes dos processos iterativos.

int lg4 (int N) {  
   int i = 0, n = 1;
   while (n < N) {
      n = 2 * n;
      ++i;
   }
   return i; }

A biblioteca math contém a função floor, que recebe um número real x e devolve o número ⌊x⌋, ou seja, piso de x. Analogamente, ceil(x) é o teto de x. Suponha agora que x é uma variável do tipo float e diga quais das seguinte afirmações são verdadeiras.
```
floor(x/2) == (int)x / 2
ceil(x/2) == (int)x / 2 + 1
```
Escreva uma função que faça a mesma coisa que floor e outra que faça a mesma coisa que ceil.

Moldes e números aleatórios

Esta seção ilustra os conceitos de tipo-de-dados e molde (= cast). Também usa a função rand da biblioteca padrão stdlib. A seção foi baseada no Programa 3.2 do livro do Sedgewick.

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

// O programa abaixo calcula a média e o
// desvio padrão de N números inteiros
// aleatórios.

int main (void) { 
   int i, N, x;
   float m1, m2;

   m1 = m2 = 0.0;
   printf("\nValor de N: ");
   scanf("%d", &N);
   for (i = 0; i < N; i++) {
      x = rand();
      m1 += ((float)x) / N; 
      m2 += ((float)x * x) / N;
   }
   printf("       Average: %f\n", m1);
   printf("Std. deviation: %f\n", 
          sqrt(m2 - m1 * m1));
   return 0;
}

Qual o invariante do processo iterativo no programa acima? Fácil: no começo de cada iteração, m1 é a soma dos i primeiros números aleatórios dividida por N. Analogamente, m2 é a soma dos quadrados dos i primeiros números aleatórios dividida por N.

Exercícios

No programa acima, o que acontece se a linha #include <stdlib.h> for trocada pela linha a seguir?
```
int rand(void);
```

Por que não fazer o cálculo da média como descrito a seguir?

int soma;
for (i = 0; i < N; i++) {
   x = rand();
   soma += x;
}
m1 = (float)x / N;

Veja minhas notas de aula sobre strings, caracteres e inteiros.

Endereços e ponteiros

Esta seção é baseada nas seções 2.2-2.3 do livro do Roberts. Ela introduz os conceitos de endereço (= address) e ponteiro (= pointer). Em particular, a seção introduz os operadores

& (endereço de ou address-of) e
* (conteúdo de ou dereference).

// Function SolveQuadratic.
// Usage: SolveQuadratic (a, b, c, &x1, &x2);
// ------------------------------------------
// This function solves the quadratic
// equation ax^2 + bx + c = 0. If the
// equation has no real solution, the
// function returns 0. Otherwise, the
// function returns 1 and places the
// solutions in x1 and x2.

int SolveQuadratic (float a, float b, float c, 
                    float *px1, float *px2) {
   float discr, sqrtDiscr;
   
   discr = b * b - 4 * a * c;
   if (discr < 0) return 0;
   sqrtDiscr = sqrt(discr);
   if (a == 0) return 0;
   *px1 = (-b + sqrtDiscr) / (2 * a);
   *px2 = (-b - sqrtDiscr) / (2 * a);
   return 1;
}

Exercícios

Escreva um programa que leia números A, B e C e imprima as soluções da equação Ax²+Bx+C = 0. O seu programa deve usar a função SolveQuadratic definida acima. Escreva também uma pequena função que verifique se as soluções produzidas por SolveQuadratic estão corretas. O programa principal (main) deve usar essa função de teste.

[Roberts #17] Qual o efeito do segmento de código abaixo?

   int v1, v2, *p1, *p2;
   v1 = 10; v2 = 25;
   p1 = &v1; p2 = &v2;
   *p1 += *p2;
   p2 = p1;
   *p2 = *p1 + *p2;

O que faz a função SomaVetor abaixo?

int SomaVetor(int *p, int n) {
   int i, s = 0;
   for (i = 0; i < n; i++) {
      s += *p;
      p++; 
   }
   return s; }

Reescreva a função de modo que ela fique mais de acordo com o protótipo

int SomaVetor(int vetor[], int n) ;

Qual o efeito do seguinte trecho de programa?
```
   int x;
   scanf("%d %d", &x, x);
```

Veja minhas notas de aula sobre endereços e ponteiros.

Vetores (= arrays)

Esta seção introduz o conceito de vetor. Ela corresponde à primeira parte da seção 3.2 (Arrays) do livro do Sedgewick. O programa abaixo é essencialmente o mesmo que o Programa 3.5 no Sedgewick.

#include <stdio.h>
#define N 10000

// Este programa imprime uma lista de todos
// os números primos menores que N. O método
// usado é o do crivo de Eratóstenes (veja
// Programa 3.5 no Sedgewick).

int main (void) {
   int i, j, a[N];

   for (i = 2; i < N; i++) 
      a[i] = 1;
   for (i = 2; i < N; i++)
      if (a[i] == 1) {
         printf("%5d\n", i);
         for (j = i; i*j < N; j++) 
            a[i*j] = 0;
      }
   return 0;
}

É claro que cada elemento do vetor a[2..N-1] vale 0 ou 1. Podemos então formular o invariante principal do programa assim: no começo de cada iteração do segundo for, para cada h em 2..N-1, a[h] == 1 se e somente se

h não é divisível por nenhum dos números do intervalo 2..i-1.

Portanto, para h = 2, … , i-1, o número h é primo se e só se a[h] == 1.

Exercícios

Por que j começa em i e não em 2?
Quanto tempo o programa consome em função de N?

[Sedg 3.15] Que acontece se o programa for trocado pelo seguinte?

for (i = 2; i < N; i++) a[i] = 1;
for (i = 2; i < N; i++)
   for (j = i; i*j < N; j++) a[i*j] = 0;
for (i = 2; i < N; i++)
   if (a[i] == 1) 
      printf("%4d ", i);

Faça testes para comparar o consumo de tempo da versão original com o desta nova versão.

[Sedg 3.14] Use o crivo de Eratóstenes para traçar um gráfico (ou histograma) da quantidade de números primos menores N para N variando de 1 até 1000.
[Sedg 3.11] Diga (sem usar o computador) qual o conteúdo do vetor a depois dos seguintes comandos?
```
int a[99];
for (i = 0; i < 99; ++i) a[i] = 98 - i;
for (i = 0; i < 99; ++i) a[i] = a[a[i]];
```
Qual o conteúdo do vetor a depois dos seguintes comandos?
```
int a[99];
for (i = 0; i < 99; ++i) *(a+i) = 98 - i;
```

Qual a diferença entre as duas expressões C abaixo?

for (i = 0; i < 10; ++i) . . . 
for (i = 0; i < 10; i++) . . .

Qual a diferença entre as três expressões C abaixo?

while (i <= n && a[++i] < 0) {}
while (i <= n && a[i++] < 0) {}
while (i <= n && a[i] < 0) ++i ;

Problema: Dado um inteiro x e um vetor a[0..n-1], encontrar j tal que a[j] == x. As funções abaixo prometem resolver o problema. Discuta. Depois, escreva a sua própria solução para o problema.

int func1 (int x, int a[], int n) { 
   int achou = 0, j = 0;
   while (j < n && !achou) {
      if (a[j] == x) achou = 1;
      else j++; }
   if (!achou) j = 0;
   return j; }

int func2(int x, int a[], int n) {
   int j, k;
   for (k = 0; k < n; k++) 
      if (a[k] == x) j = k;
   return j; }

Um segmento horizontal de um vetor a[0..n-1] é um subvetor a[i..k] tal que a[i] == a[i+1] == . . . == a[k]. O comprimento de um tal subvetor é k-i+1. Escreva uma função que receba um vetor inteiro não vazio a[0..n-1] e devolva o comprimento de um segmento horizontal máximo no vetor. (Um segmento horizontal é máximo se não existe segmento horizontal de comprimento maior.) Procure escrever uma função simples e limpa.

Alocação dinâmica de memória

Esta seção introduz o conceito de alocação dinâmica de memória e a função malloc da biblioteca padrão stdlib. Também introduz o operador sizeof. O programa abaixo é uma cópia do Programa 3.6 do livro do Sedgewick.

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

// Este programa imprime uma lista de todos
// os números primos menores que N. O método
// usado é o do crivo de Eratóstenes.

int main (void) {
   int i, j, N;
   int *a;

   printf("\nValor de N: ");
   scanf("%d", &N);
   a = malloc(N * sizeof (int));
   for (i = 2; i < N; i++) 
      a[i] = 1;
   for (i = 2; i < N; i++)
      if (a[i] == 1) {
         printf("%5d\n", i);
         for (j = i; i*j < N; j++) 
            a[i*j] = 0;
      }
   return 0;
}

Há uma relação estreita entre ponteiros, endereços e vetores porque os elementos de um vetor têm endereços consecutivos. Assim, no exemplo acima, as expressões

a[i] e *(a+i)

são equivalentes.

Exercícios

[Sedg 3.13] Escreva uma função que diga quantos números primos são (estritamente) menores que N.

Veja minhas notas de aula sobre alocação dinâmica de memória.

Veja também as funções de alocação de memória na biblioteca genlib de Eric Roberts: o arquivo-interface da biblioteca é genlib.h e implementação está em genlib.c.

Caras e coroas

O programa abaixo é uma cópia do Programa 3.7 de Sedgewick.

#include <stdlib.h>

int heads (void);

// Este programa faz M experimentos. Cada
// experimento consiste em contar o número de
// caras (= heads) em N jogadas de uma moeda. 
// O programa imprime um histograma dos
// resultados. 
//
int main (void) {
   int i, j, cnt, N, M;
   int *f;

   printf("\nValor de N: ");
   scanf("%d", &N);
   printf("\nValor de M: ");
   scanf("%d", &M);
   f = malloc((N+1) * sizeof (int));
   if (a == NULL) {
      printf("A memória está esgotada!\n");
      return 1;
   }
   for (j = 0; j <= N; j++) f[j] = 0;
   for (i = 0; i < M; i++) {
      cnt = 0;
      for (j = 0; j < N; j++) 
         if (heads()) cnt++;
      f[cnt]++;
   }
   for (j = 0; j <= N; j++) {
      printf("%2d ", j);
      for (i = 0; i < f[j]; i += 10) 
         printf("*");
      printf("\n");
   }
   free(f);
   return 0;
}

// A função heads devolve um elemento
// aleatório do conjunto {0,1}.
//
int heads (void) {
   return rand() <= RAND_MAX / 2;
}

[Sedgewick diz < RAND_MAX/2, mas eu acho que isso está errado. Mesmo <= RAND_MAX/2 só está certo porque RAND_MAX é ímpar. A propósito, veja a aula sobre números aleatórios.]

Pontos no plano

Esta seção introduz o conceito de registro (= struct) e a ideia de tipo-de-dados criado pelo usuário (typedef). Esse material está na parte final da seção 3.2 do livro do Sedgewick.

typedef struct {
   float x; 
   float y;
} point;

// Esta função devolve a distância entre os
// points A e B. O tipo point é um ponto no
// plano: A.x e A.y são as coordenadas
// cartesianas do point A. 

float distance (point A, point B) { 
   float dx, dy;

   dx = A.x - B.x;
   dy = A.y - B.y;
   return sqrt(dx * dx + dy * dy);
}

O programa abaixo gera N pontos no quadrado unitário fechado [0,1]×[0,1] e em seguida conta quantos pares de pontos estão à distância menor que d um do outro. Esse material está em Programs 3.3, 3.4, 3.8 do livro do Sedgewick.

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

typedef struct {
   float x; 
   float y;
} point;

float distance (point A, point B) { 
   float dx = A.x - B.x, dy = A.y - B.y;
   return sqrt(dx * dx + dy * dy);
}

float randFloat (void) {
   return 1.0 * rand() / RAND_MAX;
}

int main (void) { 
   float d,
   int i, j, cnt, N;
   point *a;

   printf("\nValor de N: ");
   scanf("%d", &N);
   printf("\nValor de d: ");
   scanf("%f", &d);
   a = malloc(N * sizeof (point));
   // deveria ter verificado se a != NULL 
   cnt = 0;
   for (i = 0; i < N; i++) {
      a[i].x = randFloat(); 
      a[i].y = randFloat(); 
   }
   for (i = 0; i < N; i++)
      for (j = i+1; j < N; j++)
         if (distance(a[i], a[j]) < d) cnt++; 
   printf("%d pares de pontos mais próximos que %f\n",
          cnt, d);
   free(a);
   return 0;
}

Consumo de tempo: proporcional a N². Assim, quando N dobra, o consumo de tempo é multiplicado por 4. Quando N é multiplicado por 10, o consumo de tempo é multiplicado por 100.

Exercícios

Escreva uma função que decida se dois objetos do tipo point são iguais.
[Sedg 3.22] Modifique o programa para que ele imprima as coordenadas de um par de pontos mais próximos.
[Sedg 3.23] Gere N pontos aleatórios em um cubo unitário. Calcule o número de pontos que estejam à distância menor que d um do outro.

Qual o valor de k no fim do seguinte trecho de programa?

k = 0;
for (i = 2; i < n-2; i++)
   for (j = n; j > i; j--)
      k++;

[Sedg 3.6] Defina um struct que seja apropriado para representar cartas de baralho.

Veja minhas notas de aula sobre structs.