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 9 -- Cálculo de raiz quadrada
###############################################################################

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 -- Raiz quadrada 1 (raiz1.c) ######################################

Neste exercício iremos implementar uma função para calcular a raiz quadrada de
um número X com precisão de N casas decimais (claro, sem usar a função sqrt()
da biblioteca matemática do C).

O primeiro algoritmo a utilizar é bem simples.  A ideia está sintetizada nas
etapas abaixo.  As etapas abaixo são um pouco abstratas propositalmente, para
você exercitar a construção de algoritmos.

0. Inicialize Q com um valor positivo.

1. Inicie escolhendo (chutando) um número Y para a raiz quadrada de X.

2. Se Y*Y < X, vá para o passo 3; se Y*Y > X, vá para o passo 6.

3. Faça Y = Y + Q.

4. Se Y*Y < X, volte ao passo 3; se Y*Y > X, vá para o passo 5.

5. Diminua o valor da quantidade Q.

6. Faça Y = Y - Q.

7. Se Y*Y > X, volte ao passo 6; se Y*Y < X, vá para o passo 8.

8. Diminua o valor da quantidade Q.  Vá para o passo 3.

Recomendamos você desenhar X, Q, e Y à medida que as etapas são executadas para
facilitar o entendimento do algoritmo; chame o professor ou o monitor em caso
de dúvida. Antes de passar para a implementação do código, duas partes
importantes do algoritmo foram deixadas em aberto para você decidir: (a) como
diminuir o valor de Q, (b) quando parar o algoritmo para garantir a precisão de
N casas decimais e (c) o que fazer caso Y fique negativo.  (Explique suas
decisões num comentário no início do seu código.)

Sua função deve ter a seguinte declaração:

double raiz(double X, int N);

Use a função main() abaixo para testar o seu código:

int main(int argc, char **argv) {
        if(argc < 3) {
                fprintf(stdout, "uso: %s NUMERO PRECISAO\n", argv[0]);
                exit(EXIT_FAILURE);
        }
        double x = atof(argv[1]);
        int precisao = atoi(argv[2]);
        double r = raiz(x, precisao);
        fprintf(stdout, "raiz de %lf = %.15lf\n", x, r);
        fprintf(stdout, "raiz de %lf = %.15lf\n", x, sqrt(x));
        return EXIT_SUCCESS;
}



Exercício 2 -- Raiz quadrada 2 (raiz2.c) ######################################

O algoritmo acima é simples, mas muito lento porque pode fazer várias iterações
até aproximar Y da raiz quadrada de X.  Uma versão muito mais rápida pode ser
feita usando a ideia a seguir:

1. Inicie escolhendo (chutando) um número Y < X para a raiz quadrada de X.

2. Faça Z = X/Y.

3. Faça Y = (Y + Z)/2.

4. Volte ao passo 2.

Explique por que esse algoritmo é mais rápido que o anterior em um comentário
no início do seu código.  Note que o algoritmo acima nunca termina; explique em
um comentário como você decide se a raiz quadrada calculada já tem precisão de
N casas decimais.

Use a mesma função main() mostrada no algoritmo 1 para testar o seu código.