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 8 -- Pilha, modularização, vetores e torres de Hanoi ############################################################################### 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 /* 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 -- Pilha (pilha.c pilha.h testapilha.c) ########################### Uma pilha é uma estrutura de dados simples que suporta duas operações básicas. A operação de /empilhar/ coloca um novo elemento no topo da pilha, e a operação de /desempilhar/ remove e retorna o elemento no topo da pilha. Note que numa pilha, o primeiro elemento a "entrar" é o último a "sair". Neste exercício iremos implementar uma pilha; começe baixando o esqueleto da pilha de http://www.dcc.ufmg.br/~cunha/teaching/20131/aeds1/pratica8.pilha.zip. Descompacte este zip num diretório. Ele contém os arquivos testapilha.c (não precisa modificar), pilha.h (não precisa modificar) e pilha.c (que você deve completar). Depois de completar o pilha.c, use o testa pilha.c para verificar o seu código. Exercício 2 -- Elementos duplicados (dup.c) ################################### Faça um programa que lê um arranjo ordenado de números e cria um novo arranjo sem os elementos duplicados. Por exemplo, se seu programa ler: 1 2 2 2 3 4 4 4 4 5 6 8 12 12 12 13 Ele deve retornar e imprimir: 1 2 3 4 5 6 8 12 13 Aloque espaço para os dados (de entrada e a saída) dinamicamente. Desafio P1 -- Hanoi iterativo (hanoii.c) ###################################### Use seu módulo pilha implementado no exercício 1 para implementar um algoritmo iterativo (sem recursão) para resolver o problema das torres de Hanoi. Se necessário, consulte a implementação recursiva vista em sala. DICA: O algoritmo iterativo é simples e corresponde ao algoritmo recursivo. Para mover X discos do pino P para o pino Q, é preciso realizar três tarefas: 1. Mover X-1 discos do pino P para o pino temporário. 2. Mover 1 disco (o maior) do pino P para o pino Q. 3. Mover X-1 discos do pino temporário para o pino Q. Crie uma "struct tarefa" para representar o movimento de X discos de um pino P para um pino Q. Depois use uma pilha para saber quais tarefas precisam ser executadas e em qual ordem. Empilhe novas tarefas na pilha quando necessário; termine quando não houver mais tarefas na pilha.