Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência de Computação
DCC003 -- Algoritmos e Estruturas de Dados 1 -- 2013/1 -- Turma F
Prática 7 -- Funções e recursividade
###############################################################################

INSTRUÇÕES:  Salve suas soluções num arquivo .c (o nome está indicado entre
parênteses no cabeçalho de cada exercício) e entregue no Moodle.  

IMPORTANTE:  Coloque um comentário na primeira linha do arquivo contendo o(s)
nome(s) do(s) aluno(s) que fizeram o código.  (Um comentário em C é qualquer
texto entre /* e */.)
###############################################################################

DICAS: Para ler uma string de até 127 caracteres do teclado, use o seguinte
código:

	char linha[128];
	printf("digite uma linha:\n");
	fgets(linha, 128, stdin);

Para gerar um número aleatório em C entre 0 e RAND_MAX use a função
rand() definida dentro de stdlib.h:

	#include <stdlib.h> /* no começo do arquivo */
	int aleatorio = rand(); /* em qualquer ponto no programa */

Para alocar um vetor de X elementos do tipo Y use:

	Y * vetor = malloc(X * sizeof(Y));
	/* Por exemplo: double * vetor = malloc(10 * sizeof(double)) */
	/* Não esquecer de liberar a memória depois com free(vector)! */

Lembre-se que nomes de arranjos, quando usados sem colchetes, são convertidos
em ponteiros.  Além disso, temos que exp1[exp2] é semânticamente idêntico à
*(exp1+exp2).

Funções para manipulação de arquivos incluem:

	FILE * fopen(char *nome, char *modo); /* abrir um arquivo */
	/* Use "r" para modo de leitura (read) e "w" para modo de escrita
	 * (write). */
	int fclose(FILE *arquivo); /* fechar um arquivo */

	long ftell(FILE *arquivo); /* encontrar posição atual no arquivo */
	int fseek(FILE *arquivo, long distancia, int base); /* mudar posição */

	fprintf e fscanf, igual printf e fscanf mas aceitam arquivo como
	parâmetro.



Exercício 1 -- Média e variância de um vetor (mediavar.c) #####################

Complete a função abaixo para calcular a média dos elementos em um vetor com N
elementos:

double calcula_media(int *v, int N) { }

Complete a função abaixo para calcular a variância dos elementos de um vetor
com N elementos:

double calcula_variancia(int *v, int N) { }

Complete a função abaixo para calcular a média e a variância dos elementos de
um vetor com N elementos:

void mediavar(int *v, int N, double *media, double *variancia) { }

Utilize o esqueleto abaixo para testar seu programa:

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

int main(int argc, char **argv) {
	if(argc < 2) {
		printf("uso: %s V1 V2 V3 ... VN\n", argv[0]);
		exit(EXIT_FAILURE);
	}
	int N = argc - 1;
	int *v = malloc(sizeof(int) * N);
	if(!v) { perror(NULL); exit(1); }
	int i;
	for(i = 0; i < N; i++) {
		v[i] = atoi(argv[i+1]);
	}
	double media;
	double var;
	mediavar(v, N, &media, &var);
	printf("a media eh %lf e a variancia eh %lf\n", media, var);
	exit(EXIT_SUCCESS);
}



Exercício 2 -- Exponenciação recursiva (exprec.c) #############################

Implemente uma funcao *recursiva* para calcular X elevado a Y, sendo que
Y deve ser maior ou igual a zero.

int potencia(int x, int y) { }

Para testar seu programa, use o esqueleto abaixo:

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

int main(int argc, char **argv) {
	if(argc < 3) {
		printf("uso: %s X Y\n", argv[0]);
		exit(EXIT_FAILURE);
	}
	int X = atoi(argv[1]);
	int Y = atoi(argv[2]);
	int potencia = potencia(X, Y);
	printf("%d^%d = %d\n", X, Y, potencia);
	exit(EXIT_SUCCESS);
}



Exercício 3 -- Contando chamadas (conta.c) #####################################

Modifique a função a seguir para que ela retorne (1) o número de chamadas
recursivas executadas e (2) o máximo de registros de ativação colocados na
memória simultaneamente. A recursão deve terminar quando 'N' for igual a 1.

void recursao(int N) {
	/* ... */
	recursao(N-1);
	recursao(N-1);
	/* ... */
}

Use o esqueleto a seguir para testar seu programa:

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

int main(int argc, char **argv) {
	if(argc < 2) {
		printf("uso: %s X\n", argv[0]);
		exit(EXIT_FAILURE);
	}
	int N = atoi(argv[1]);
	int chamadas = 0;
	int registros = 0;
	/* ... */
	recursao(N);
	/* ... */
	printf("foram executadas %d chamadas recursivas\n", chamadas);
	printf("no maximo %d registros foram colocados "
			"na memoria\n", registros);
	exit(EXIT_SUCCESS);
}