A maior rede de estudos do Brasil

Grátis
Estruturas_de_Dados_e_Algoritmos_em_C.erivanildo- Blog - conhecimentovaleouro.blogspot.com by @viniciusf666

Pré-visualização | Página 38 de 50

parte). 
O número de movimentos necessários para mudar N discos é igual a 2N î 1. Pelo que, o 
número de invocações da função recursiva aumenta exponencialmente com o aumento do 
número de discos. Por isso, não se deve invocar o programa para um número de discos 
maior do que 10. A Figura 4.23 apresenta a execução do programa para três discos. 
 
 
Figura 4.23 - Execução do programa Torres de Hanói para 3 discos. 
---------------------------------
| Torres de Hanoi |
| Numero de discos = 3 |
---------------------------------
| TORRE A TORRE B TORRE C |
---------------------------------
 1 
 2 
 3 
---------------------------------
 2 
 3 1 
---------------------------------
 3 1 2 
---------------------------------
 1 
 3 2 
---------------------------------
 1 
 3 2 
---------------------------------
 1 3 2 
---------------------------------
 2 
 1 3 
---------------------------------
 1 
 2 
 3 
---------------------------------
void MUDAR_DISCOS (int ND, int TA[], int *NDA, int TB[], int *NDB,\ 
 int TC[], int *NDC); 
{ 
 if (ND == 1) /* condição de paragem */
 { /* mudar o disco da Torre A para a Torre B */
 (*NDB)++; TB[*NDB-1] = TA[*NDA-1]; (*NDA)--; 
 IMPRIMIR (); 
 } 
 else 
 { 
 /* mudar os N-1 discos de cima da Torre A para a Torre C */
 MUDAR_DISCOS (ND-1, TA, NDA, TC, NDC, TB, NDB); 
 /* mudar o último disco da Torre A para a Torre B */
 (*NDB)++; TB[*NDB-1] = TA[*NDA-1]; (*NDA)--; 
 IMPRIMIR (); 
 /* mudar os N-1 discos da Torre C para a Torre B */
 MUDAR_DISCOS (ND-1, TC, NDC, TB, NDB, TA, NDA); 
 } 
} 
17 CAPÍTULO 4 : RECURSIVIDADE 
 
 
4.9 Questões sobre a eficiência das soluções recursivas 
Alguns algoritmos recursivos desencadeiam um número arbitrariamente grande de 
invocações sucessivas da função, pelo que, nestes casos temos uma ineficiência acrescida 
associada à invocação de funções. Por outro lado, existem algoritmos recursivos que são 
computacionalmente ineficientes, porque calculam certos valores repetidamente devido às 
múltiplas invocações recursivas. No caso dos algoritmos em que a invocação recursiva 
explode rapidamente, existe ainda o perigo de a memória de tipo pilha esgotar e do 
programa terminar a sua execução abruptamente. Portanto, o programador deve ter sempre 
em conta estas ineficiências e limitações, antes de optar por uma solução recursiva em 
detrimento de uma solução iterativa, caso ela exista. 
 
Os algoritmos recursivos são apropriados para resolver problemas que são normalmente 
definidos de forma recursiva, ou seja, problemas que são por natureza recursivos. Por 
vezes, existem problemas que têm soluções recursivas que são simples, concisas, elegantes 
e para os quais é difícil esboçar soluções iterativas com a mesma simplicidade e clareza. 
Mas, tal como vimos nos exemplos apresentados, alguns algoritmos recursivos são menos 
eficientes que os algoritmos iterativos equivalentes. Pelo que, a verdadeira importância da 
recursividade consiste em resolver esses problemas para os quais não existem soluções 
iterativas simples. 
4.10 Exercícios 
1. Pretende-se escrever um programa que imprima no monitor, uma tabela em que se 
compara os valores da função co-seno calculada pela expansão em série de Taylor para 5, 
10 e 15 termos e pela função matemática cos. Os valores inicial e final da tabela, bem como 
o número de elementos da tabela são lidos do teclado. O termo geral da expansão em série 
de Taylor da função co-seno é dado pela seguinte expressão à esquerda, sendo apresentada 
à direita a sua expansão para os primeiros cinco termos da série. 
 
� � � � !2 1 ),coseno(
21
0 n
x
Nx
n
n
N
n
u� ¦�
 
 ... 
!8
 
!6
 
!4
 
!2
 1 )5,(coseno
8642
xxxx
x ���� 
 
Desenhe a tabela com o formato que a seguir se apresenta. 
 
---------------------------------------------------------------------- 
| x | coseno(x,5) | coseno(x,10) | coseno(x,15) | cos(x) | 
---------------------------------------------------------------------- 
| ##.#### | #.######### | #.######### | #.######### | #.######### | 
---------------------------------------------------------------------- 
... 
---------------------------------------------------------------------- 
| ##.#### | #.######### | #.######### | #.######### | #.######### | 
---------------------------------------------------------------------- 
 
Faça duas versões do programa. Na primeira versão, implemente a expansão da série de 
Taylor da função co-seno com uma função iterativa, e na segunda versão com uma função 
recursiva. 
PROGRAMAÇÃO ESTRUTURAS DE DADOS E ALGORITMOS EM C 18 
2. Pretende-se escrever um programa que escreva no monitor as permutações da cadeia 
de caracteres composta pelos caracteres numéricos de ‘0’ a ‘9’. Altere o programa para 
escrever apenas as permutações que são compostas alternadamente por caracteres 
numéricos pares e ímpares. 
 
3. Pretende-se escrever um programa que lê do teclado dois números inteiros positivos, 
que calcula e imprime no monitor o seu máximo divisor comum. O máximo divisor 
comum de dois números inteiros positivos pode ser calculado de forma repetitiva, 
utilizando para o efeito o método de Euclides, cujo algoritmo é dado pela seguinte 
expressão. 
 
®¯­ z
 
 0 n se n)),mod(m,mdc(n, 
0 n se m, 
 n)mdc(m, 
 
Faça duas versões do programa. Na primeira versão, implemente o cálculo do máximo 
divisor comum com uma função iterativa, e na segunda versão com uma função recursiva. 
 
4. Pretende-se escrever um programa que lê do teclado dois números inteiros positivos, 
que calcula e imprime no monitor o valor da função de Ackermann, que se apresenta na 
seguinte expressão. 
 
°¯
°®
­
!!
 
 �
 
 0m e 0n com , 1))-nm,Ackermann(1,-(m Ackermann
0 n se 1,1),-(m Ackermann
0 m se 1,n 
 n)m,Ackermann( 
 
Faça duas versões do programa. Na primeira versão, implemente o cálculo da função de 
Ackermann com uma função recursiva, e na segunda versão com uma função iterativa 
dinâmica, usando um agregado bidimensional. 
4.11 Leituras recomendadas 
x 3º capítulo do livro “Data Structures, Algorithms and Software Principles in C”, de 
Thomas A. Standish, da editora Addison-Wesley Publishing Company, 1995. 
 
Capítulo 5 
MEMÓRIAS 
Sumário 
Neste capítulo começamos por introduzir o paradigma da programação modular e a 
construção de módulos na linguagem C, apresentando as suas características e a 
necessidade de criação de módulos genéricos. A título de exemplo, desenvolvemos um 
exemplo de um módulo abstracto com múltipla instanciação para operações sobre números 
complexos. 
 
Seguidamente mostramos a organização da Memória de Acesso Aleatório (RAM), da 
Memória Fila (Queue/FIFO), da Memória Pilha (Stack/LIFO) e da Memória Associativa 
(CAM) e os seus ficheiros de interface. 
 
Depois de descrevermos as particularidades e limitações dos tipos de implementação de 
memórias, fazemos uma abordagem às estruturas de dados que servem de suporte à 
implementação estática e semiestática da Memória de Acesso Aleatório, e à implementação 
estática, semiestática e dinâmica da Memória Fila, da Memória Pilha e da Memória 
Associativa. 
 
Finalmente, apresentamos as funções da biblioteca de execução ANSI stdlib que permitem a 
atribuição e libertação de memória, durante a execução do programa. 
 
 
PROGRAMAÇÃO ESTRUTURAS DE DADOS E ALGORITMOS EM C 2 
5.1 Programação modular 
O paradigma