Lesson04

Exemplo: contagem de aprovações e ocorrências de notas

Objectivo:

1. Considere-se uma lista de inteiros que denota as notas dos alunos numa disciplina.
2. Ler uma lista de inteiros positivos introduzidos pelo utilizador.
3. Qualquer valor negativo determina o fim do conjunto de inteiros a ler.
4. No fim mostrar a seguinte informação:
   1. número de notas à disciplina;
   2. número de aprovações;
   3. número de reprovações;
   4. número de ocorrências de cada uma das notas entre 0 e 20.

Algoritmo

Input: notas introduzidas no stdin.
Output: contagens escritas no stdout.

1. Inicializa contadores de notas e contador de aprovações e reprovações a 0.
   aprovacoes = total = 0;
for (i=0; i<21; i++)
   $\ \ \ $notas[i]=0;
2. Lê nota.
   scanf(“%d”, &v);
3. Enquanto conseguir ler uma nota válida:
   while (v >= 0) {
   1. incrementa o contador da nota correspondente;
      total++;
   2. incrementa o contador da nota correspondente;
      notas[v]++;
   3. se a nota lida é positiva...
      if (v >= 10)
      1. incrementa contador de aprovações;
         aprovacoes++;
   4. lê nota seguinte. scanf(“%d”, &v);}
4. Escreve valor dos contadores.
   printf (“Total: %d, Aprovacoes: %d, Reprovacoes: %d\n”, total, aprovacoes, total - aprovacoes);
for (i=0; i<21; i++)
   $\ \ \ $printf (“%d %d\n”, i, notas[i]);

Implementação

#include <stdio.h>
#define DIM 21

int main () {
  int i, v, total = 0, aprovacoes = 0, notas[DIM];

  for (i = 0; i < DIM; i++)
      notas[i] = 0;	

  scanf("%d", &v);
  while (v >= 0) {
    total++;
    notas[v]++;

    if (v >= 10)
      aprovacoes++;
    scanf("%d", &v);
  }
  
  printf ("Total: %d, Aprovacoes: %d, Reprovacoes: %d\n", total,
           aprovacoes, total-aprovacoes);

  for (i = 0; i < DIM; i++)
    printf ("%d %d\n", i, notas[i]);

  return 0;
}

Neste programa utilizamos uma tabela unidimensional com capacidade para guardar 21 inteiros, declarada como int notas[DIM], em que DIM é a dimensão da tabela. A variável notas será utilizada para guardar o histograma das notas. Neste caso notas[i] é o inteiro no índice i da tabela notas, ou seja, no presente programa, o número de ocorrências da nota i. Dado que o índice i pode variar entre 0 e DIM-1, apenas podemos ler e atribuir valores a notas[0], notas[1], ..., notas[DIM-1]. Para atribuir um valor basta, por exemplo, realizar a instrução notas[i]=0, em que neste caso atribui o valor 0 ao inteiro na posição i da tabela.

Exemplo: número de aprovações e nota mais alta de um turno

Objectivo:

1. Considere-se uma lista de inteiros que denota as notas dos alunos inscritos em um turno prático com 25 alunos (assume-se que o tamanho do turno é fixo e que o mesmo está completo).
2. Ler uma lista de 25 inteiros positivos introduzidos pelo utilizador.
3. No fim mostrar a seguinte informação:
   1. número de aprovações;
   2. nota mais alta.

Algoritmo

Input: 25 notas introduzidas no stdin.
Output: contagem e nota mais alta escritas no stdout.

1. Inicializa contador de notas, aprovações e nota mais alta a 0.
2. Enquanto o contador de notas for inferior a 25:
   1. lê nota e guarda a mesma na tabela;
   2. incrementa contador de notas.
3. Inicializa contador de notas a 0.
4. Enquanto o contador de notas for inferior a 25:
   1. se a nota é positiva, então incrementa contador de aprovações;
   2. se a nota é maior que a nota mais alta já guardada, então atribui o valor da nota lida à nota mais alta;
   3. incrementa contador de notas.
5. Escreve número de aprovações e nota mais alta.

Implementação

#include <stdio.h>
#define DIM 25

int main () {
  int i, aprovacoes = 0, alta = 0, notas[DIM];

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

  for (i = 0; i < DIM; i++) {
    if (notas[i] >= 10)
      aprovacoes++;
    if (notas[i] > alta)
      alta = notas[i];
  }

  printf("Aprovacoes: %d, Mais alta: %d\n", aprovacoes, alta);

  return 0;
}

Exemplo: número de aprovações e nota mais alta num conjunto de turnos

Objectivo:

1. Considerem-se os 4 turnos práticos de uma disciplina e 4 listas de inteiros que denotam as notas dos alunos inscritos em cada um dos turnos práticos (assume-se que o tamanho do turno é fixo e igual a 25 alunos e todos os turnos estão completos).
2. Para cada turno, ler uma lista de 25 inteiros positivos introduzidos pelo utilizador.
3. No fim mostrar a seguinte informação para cada turno:
   1. número de aprovações;
   2. nota mais alta.

Tabelas bidimensionais (matrizes)

/*
 *     i   tab
 *
 *        +----+
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *     0  |  |   |   |   |   |   |   |   |     |   |
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *        +----+
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *     1  |  |   |   |   |   |   |   |   |     |   |
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *        +----+
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *     2  |  |   |   |   |   |   |   |   |     |   |
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *        +----+
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *     3  |  |   |   |   |   |   |   |   |     |   |
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *        +----+                   ^
 *        |    |                   |
 *         ...                     +------- tab[3][5]
 *        |    |
 *        +----+
 *        |  +---+---+---+---+---+---+---+ ... +---+
 * DIM1-1 |  |   |   |   |   |   |   |   |     |   |
 *        |  +---+---+---+---+---+---+---+ ... +---+
 *        +----+
 *         j   0   1   2   3   4   5   6       DIM2-1
 */

int tab[DIM1][DIM2];

No caso de um vector bidimensional tab, tab[i] é o vector de inteiros no índice i do vector tab e tab[i][j] é o inteiro no índice j do vector no índice i (linha i, coluna j). A instrução tab[i][j]=10 atribui neste caso o valor 10 ao inteiro no índice j do vector na posição i da tabela tab.

Algoritmo

Input: 25 notas para cada turno introduzidas no stdin.
Output: contagem e notas mais altas escritas no stdout.

1. Inicializa contador de turnos a 0.
2. Enquanto contador de turnos inferior a 4:
   1. lê e guarda na tabela as notas de um turno;
   2. incrementa contador de turnos.
3. Inicializa contador de turnos a 0.
4. Enquanto contador de turnos inferior a 4:
   1. inicializa contador de aprovações do turno a 0;
   2. inicializa nota mais alta do turno a 0;
   3. calcula e guarda número de aprovações do turno;
   4. calcula e guarda a nota mais alta do turno;
   5. incrementa o contador de turnos.
5. Escreve número de aprovações e nota mais alta de cada turno.

Implementação

#include <stdio.h>

#define TURNOS 4
#define ALUNOS 25

int main () {
  int i, j, aprovacoes[TURNOS], alta[TURNOS], notas[TURNOS][ALUNOS];
  for (i = 0; i < TURNOS; i++)
    for (j = 0; j < ALUNOS; j++)
      scanf("%d", &notas[i][j]);

  for (i = 0; i < TURNOS; i++) {
    aprovacoes[i] = alta[i] = 0;
    for (j = 0; j < ALUNOS; j++) {
      if (notas[i][j] >= 10)
        aprovacoes[i]++;
      if (notas[i][j] > alta[i])
        alta[i] = notas[i][j];
    }
  }

  for (i = 0; i < TURNOS; i++)
    printf("Turno: %d Aprovacoes: %d, Nota mais alta: %d\n",
           i, aprovacoes[i], alta[i]);
  return 0;
}

Neste exemplo utilizamos uma tabela bidimensional notas declarada como int notas[TURNOS][ALUNOS]. A dimensão desta tabela é 4x25: TURNOS é a primeira dimensão (#linhas); ALUNOS é a segunda dimensão (#colunas).

Strings (tabelas de caracteres)

/*
 *      +---+---+---+---+---+---+---+ ... +------+
 * tab  |   |   |   |   |   |   |   |     | '\0' |
 *      +---+---+---+---+---+---+---+ ... +------+
 *   i    0   1   2   3   4   5   6        DIM-1
 */

char tab[DIM];

Convenção C: qualquer string, ou cadeia de caracteres, termina com ’\0’. Por exemplo, a cadeia de caracteres "hello\n" tem os seguintes caracteres ’h’, ’e’, ’l’, ’l’, ’o’, ’\n’ e ’\0’. As função de C que recebem strings como argumento, como o printf, esperam em geral strings neste formato.

Exemplo: leitura, escrita e cópia de strings

Objectivo/convenções:

1. Ler uma sequência de caracteres introduzidos pelo utilizador.
2. Os caracteres EOF ou ’\n’ determinam o fim do conjunto de caracteres a ler
3. Mostrar a string lida.
4. Efectuar a cópia da string lida para uma string do mesmo tamanho e mostrar as duas.

Implementação de leitura e escrita de strings:

#include <stdio.h>

#define DIM 100

int main() {
  int c, i;
  char s[DIM];
  
  c = getchar();
  for (i = 0; i < DIM-1 && c != EOF && c != ’\n’; i++) {
    s[i] = c;
    c = getchar();
  }
  
  if (i < DIM-1 && c == ’\n’){
    s[i] = c;
    i++;
  }
  s[i] = ’\0’;
  
  printf("%s", s);
  return 0;
}

Implementação alternativa de leitura e escrita de strings:

#include <stdio.h>

#define DIM 100

int main() {
  int c, i;
  char s[DIM];

  for (i = 0; i < DIM-1 && (c=getchar())!= EOF && c != ’\n’; i++)
    s[i] = c;

  if (c == ’\n’){
    s[i] = c;
    i++;
  }
  
  s[i] = ’\0’;

  printf("%s", s);
  return 0;
}

Implementação de cópia de strings:

#include <stdio.h>

#define DIM 100

int main() {
  int c, i;
  char origem[DIM], destino[DIM];

  for (i = 0; i < DIM-1 && (c=getchar())!= EOF && c != ’\n’; i++)
    origem[i] = c;

  if (c == ’\n’){
    origem[i] = c;
    i++;
  }
  origem[i] = ’\0’;

  for(i = 0; origem[i] != ’\0’; i++)
    destino[i] = origem[i];
  destino[i] = ’\0’;

  printf("Origem: %s Destino: %s", origem, destino);
  return 0;
}

Implementação alternativa de cópia de strings:

#include <stdio.h>

#define DIM 100

int main() {
  int c, i;
  char origem[DIM], destino[DIM];

  for (i = 0; i < DIM-1 && (c=getchar())!= EOF && c != ’\n’; i++)
    origem[i] = c;

  if (c == ’\n’){
    origem[i] = c;
    i++;
  }
  origem[i] = ’\0’;

  i=0;
  while((destino[i] = origem[i]) != ’\0’)
    i++;

  printf("Origem: %s Destino: %s", origem, destino);
  return 0;
}

Algumas notas a reter: strings são vectores de caracteres; o programador é responsável por respeitar os limites dos vectores; o caracter ’\0’ indica o fim das strings; o formato de escrita para strings (por exemplo no printf) é %s; os vectores são copiados posição a posição.

Funções

Definição:

<tipo retorno> <nome> ( <declaracao argumentos> )
{
  <declaracoes>
  <instrucoes>
}

Protótipo:

<tipo retorno> <nome> ( <declaracao argumentos> );

Nota-se que nos protótipos podemos indicar apenas os tipos de dados nos argumentos.

A instrução return permite retornar um valor da função para uma outra função onde a primeira foi invocada. Para isso, a instrução return deve ser invocada da seguinte forma:

return <expressao>;

O valor de <expressao> é convertido para o valor de retorno da função. Ao executar a instrução return, a função termina de imediato.

Exemplo: função potência

Objectivo: escrever uma função que calcule o valor da função potência dados a base e o expoente, números inteiros.

Implementação:

#include <stdio.h>

int potencia(int base, int n);

int main() {
  int i;
  for(i = 0; i < 10; i++)
    printf("%d %d %d\n", i, potencia(2,i), potencia(-3,i));
  return 0;
}

int potencia(int base, int n) {
  int i, p = 1;
  for(i = 1; i <= n; i++)
    p = p * base;
  return p;
}

A implementação da função potência contém o código da função. Os parâmetros formais da função, neste caso base e n, são variáveis locais da função (inacessíveis a partir de outras funções). Como visto acima, a instrução return especifica o valor a retornar. Porém, uma função pode não retornar qualquer valor, caso em que o tipo de retorno é declarado como void.

O protótipo de uma função especifica os tipos dos argumentos e do tipo do valor a retornar. No exemplo acima o protótipo corresponde à declaração:

int potencia(int base, int n);

Uma vez que os argumentos podem ser omitidos na declaração do protótipo, basta colocar o tipo dos mesmos, podemos declarar o protótipo do exemplo da seguinte forma:

int potencia(int, int);

A invocação (chamada) da função potencia pode apenas ocorrer depois desta ser conhecida, seja através da declaração do protótipo seja através da sua implementação. Se a implementação da função ocorrer antes da invocação, não é necessário o protótipo:

#include <stdio.h>

int potencia(int base, int n) {
  int i, p = 1;
  for(i = 1; i <= n; i++)
    p = p * base;
  return p;
}

int main() {
  int i;
  for(i = 0; i < 10; i++)
    printf("%d %d %d\n", i, potencia(2,i), potencia(-3,i));
  return 0;
}

Passagem por valor

A passagem de parâmetros às funções em C são em geral por valor. Os parâmetros actuais são copiados para variáveis internas quando a função é executada. Deste modo, uma função não tem acesso aos parâmetros originais, mas sim a cópias dos mesmos, e portanto não os pode alterar. Esta característica da linguagem C é diferente em relação a outras linguagens, como por exemplo a linguagem Pascal, em que os parâmetros são passados por referência e, portanto, as alterações feitas aos parâmetros pela função são propagadas para fora do contexto da função.

Existem contudo excepções na linguagem C. Se o parâmetro actual é uma tabela, então não é efectuada a cópia da tabela e, se a função alterar o conteúdo da tabela, essa alteração tem efeitos fora do contexto da função. Neste caso uma tabela é referenciada em C pelo endereço da primeira posição da mesma, pelo que o parâmetro que é passado (por valor) às funções é precisamente a referência, e não a tabela em si. Mais tarde vamos ver em detalhe como funcionam as referências em C.

Na implementação da função potencia do exemplo anterior tinhamos:

int potencia(int base, int n) {
  int i, p = 1;
  for(i = 1; i <= n; i++)
    p = p * base;
  return p;
}

No entanto, uma vez que a variável n é local à função e contém apenas uma cópia do argumento original, podemos utilizar esta variável da mesma forma que qualquer outra variável declarada no contexto da função, sem o risco de propagar alterações para fora do contexto da função. Desta forma podemos ter uma implementação da função potencia com menos variáveis:

int potencia(int base, int n) {
  int p;
  for(p = 1; n > 0; n--)
    p = p * base;
  return p;
}

Quando estudarmos funções recursivas veremos como é importante este tipo de estratégia uma vez que, quantas mais variáveis utilizarmos na implementação recursiva, maior será a quantidade de memória necessária na execução da mesma, o que no caso da recursão pode levar à exaustão da stack.

Notamos que em alguns dos exemplos anteriores já utilizámos passagem de parâmetros por referência de forma explícita. Por exemplo, vejamos a seguinte implementação:

#include<stdio.h>

int potencia(int base, int n) {
  int i, p = 1;
  for(i = 1; i <= n; i++)
    p = p * base;
  return p;
}

int main() {
  int base, ex;
  scanf("%d%d", &base, &ex);
  printf("%d %d %d\n", base, ex, potencia(base, ex));
  return 0;
}

O segundo e terceiro parâmetros na função scanf são passados por referência e, portanto, a função scanf pode propagar modificações nestes parâmetros para fora do seu contexto.

Exemplo: número de aprovações, nota mais alta e média de um turno (usando funções)

Objectivo:

1. Considere-se uma lista de inteiros que denota as notas dos alunos inscritos em um turno prático com 25 alunos (assume-se que o tamanho do turno é fixo e o turno está completo).
2. Ler uma lista de 25 inteiros positivos introduzidos pelo utilizador.
3. No fim mostrar a seguinte informação:
   1. número de aprovações, nota mais alta e média.

Funções a implementar:

1. Ler notas do turno para um vector.
2. Calcular número de aprovações.
3. Calcular nota mais alta.
4. Calcular média.

Implementação

#include <stdio.h>
#define DIM 25

/* Prototipos das funcoes */
void lerNotas (int v[], int tam);
int calcularAprov (int v[], int tam);
int calcularMaisAlta (int v[], int tam); 
float calcularMedia (int v[], int tam); 

int main () {
  int notas[DIM];

  lerNotas(notas, DIM);
  printf("Aprovacoes: %d, Mais alta: %d Media: %f\n", 
	      calcularAprov(notas, DIM), calcularMaisAlta(notas, DIM),
         calcularMedia(notas, DIM));
  return 0;
}

/* Implementacao das Funcoes */
void lerNotas (int v[], int tam) {
  int i;
  for (i = 0; i < tam; i++)
    scanf("%d", &v[i]);
}

int calcularAprov (int v[], int tam) {
  int i, aprovacoes = 0;
  for (i = 0; i < tam; i++)
    if (v[i] >= 10)
      aprovacoes++;
  return aprovacoes;
}

int calcularMaisAlta (int v[], int tam) {
  int i, alta = 0;
  for (i = 0; i < tam; i++)
    if (v[i] > alta)
      alta = v[i];
  return alta;
}

float calcularMedia (int v[], int tam) {
  int i, soma= 0;
  for (i = 0; i < tam; i++)
    soma += v[i];
  return soma / (float) tam;
}

Neste exemplo:

1. a função lerNotas não retorna nada;
2. a tabela não é copiada e a alteração no conteúdo do vector v tem efeitos fora da função;
3. soma += v[i] equivale a soma = soma + v[i];
4. no retorno da função calcularMedia ocorre uma conversão explícita de tipos para evitar a divisão inteira.

Exemplo: número de aprovações, nota mais alta e média num conjunto de turnos (usando funções)

Objectivo:

1. Considere-se os 4 turnos práticos de uma disciplina e 4 listas de inteiros que denotam as notas dos alunos inscritos em cada um dos turnos práticos (assume-se que o tamanho do turno é fixo e igual a 25 alunos e todos os turnos estão completos).
2. Para cada turno ler uma lista de 25 inteiros positivos introduzidos pelo utilizador.
3. No fim mostrar a seguinte informação para cada turno:
   1. número de aprovações, nota mais alta e média.

Neste exemplo vamos utilizar as funções já implementadas no exemplo anterior:

1. Ler notas do turno para um vector.
2. Calcular número de aprovações.
3. Calcular nota mais alta.
4. Calcular média.

Implementação

#include <stdio.h>
#define TURNOS 4
#define ALUNOS 25

void lerNotas (int v[], int tam);
int calcularAprov (int v[], int tam);
int calcularMaisAlta (int v[], int tam); 
float calcularMedia (int v[], int tam); 

int main () {
  int i, aprovacoes[TURNOS], alta[TURNOS], notas[TURNOS][ALUNOS];
  float media[TURNOS];
  
  for (i = 0; i < TURNOS; i++)
    lerNotas(notas[i], ALUNOS);
  for (i = 0; i < TURNOS; i++) {
    aprovacoes[i] = calcularAprov(notas[i], ALUNOS);
	 alta[i] = calcularMaisAlta(notas[i], ALUNOS);
	 media[i] = calcularMedia(notas[i], ALUNOS);
  } 
  for (i = 0; i < TURNOS; i++)
    printf("Turno: %d Aprovacoes: %d, Nota mais alta: %d Media: %f \n",
           i, aprovacoes[i], alta[i], media[i]); 
  return 0;
}

Exemplo: ler linhas de texto e mostrar a maior

Objectivo:

1. Ler um conjunto de linhas de texto e escrever a mais comprida (linhas terminam com ‘\n’ ou EOF).

Funções a implementar:

1. Ler linha (que para além de guardar a linha, retorna o seu comprimento).
2. Copiar linha: origem --> destino.

Algoritmo

Input: linhas introduzidas no stdin.
Output: linha mais comprida escrita no stdout.

1. Lê linha.
   comprimento = lelinha(linha, MAXLINHA);
2. Enquanto houver linhas para ler:
   while (comprimento > 0) {
   1. se a linha lida é maior que a anterior maior linha, então...
      if (comprimento > max) {
      1. guarda o comprimento da linha e ...
         max = comprimento;
      2. guarda a linha;
         copia(maiscomprida, linha);}
   2. lê linha.
      comprimento = lelinha(linha, MAXLINHA); }
3. Mostra a maior linha.
   if (max > 0) printf("%s", maiscomprida);

Implementação

#include <stdio.h>
#define MAXLINHA 100

int lelinha(char s[], int lim);
void copia(char destino[], char origem[]);

int main() {
  int comprimento, max = 0;
  char linha[MAXLINHA];
  char maiscomprida[MAXLINHA];

  comprimento = lelinha(linha, MAXLINHA);
  while (comprimento > 0) {
    if (comprimento > max) {
      max = comprimento;
      copia(maiscomprida, linha);
    }
    comprimento = lelinha(linha, MAXLINHA);
  }
  if (max > 0)
    printf("%s", maiscomprida);
  return 0;
}

int lelinha(char s[], int lim) {
  int c, i;

  for (i = 0; i < lim-1 && (c=getchar())!= EOF && c != ’\n’; i++)
    s[i] = c;
  if (c == ’\n’){
    s[i] = c;
    i++;
  }
  s[i] = ’\0’;
  return i;
}

void copia(char destino[], char origem[]) {
  int i;
  for(i = 0; origem[i] != ’\0’; i++)
    destino[i] = origem[i];
  destino[i] = ’\0’;
}

Notamos que, para se copiar uma tabela não basta igualar as variáveis, é necessário copiar cada elemento da tabela origem, um a um, para a tabela destino.

Outros exercícios

Defina uma função que recebe um vector de inteiros e devolve o maior valor no vector.

int maior(int vec[], int vec_size)
{
  int i, max;

  max = vec[0];

  for (i=1; i<vec_size; i++)
    if (vec[i]>max)
      max = vec[i];

  return max;
}

Defina uma função que recebe uma string e substitui as letras minúsculas por letras maiúsculas.

#include<stdio.h>
#define N 100

void LinhaMaiusculas(char v[])
{
  int i=0;

  for (i=0 ; v[i]!='\0' ; i++)
    if (v[i]>='a' && v[i]<='z')
      v[i] -= 'a'-'A';
}

int main() {
  char s[N];

  scanf("%s",s);
  LinhaMaiusculas(s);
  printf("%s\n",s);

  return 0;                            
}