pc1-lista9

Prévia do material em texto

UNESP/FEG/DMA	
Programação	de	Computadores	I	-	Prof.	Senne	
Lista	de	Exercícios	9	
	
	
1. Escrever	uma	função	recursiva	int	procuraLinear(int	v[],	int	n,	int	k)	que	retorna	o	
índice	da	posição	em	que	o	valor	k	aparece	no	vetor	v	(de	n	elementos).	Caso	o	valor	
k	não	esteja	presente	em	v,	a	função	deve	retornar	-1.	
	
2. Mostrar	a	pilha	de	execução	e	o	valor	retornado	por	misterio(4),	considerando	que		
a	função	misterio	é	implementada	como:	
	
int misterio(int n) 
{ 
 if ((n == 1) || (n == 2)) 
 return n; 
 else 
 return misterio(n-1) + n*misterio(n-2); 
} 
	
3. A	procura	por	um	valor	k	 em	um	vetor	ordenado	 v	pode	 ser	 feita	eficientemente	
pelo	seguinte	algoritmo:	
	
Seja	m	o	valor	do	elemento	que	ocupa	a	posição	"central"	no	vetor.	
Se	k	=	m,	retornar	o	índice	de	m	no	vetor;	
Se	k	<	m,	continuar	a	procura	apenas	na	primeira	"metade"	do	vetor;	
Se	k	>	m,	continuar	a	procura	apenas	na	segunda	"metade"	do	vetor.	
	
Implementar	este	algoritmo	como	uma	função	recursiva.	
	
4. Escrever	 uma	 função	 recursiva	 que	 retorna	 a	 soma	 dos	 dígitos	 decimais	 de	 um	
inteiro	estritamente	positivo	n.	Por	exemplo,	para	n	=	1234,	a	função	deve	retornar	
10	(pois	1	+	2	+	3	+	4	=	10).	
	
5. Um	palíndrome	é	uma	palavra	ou	frase	que	pode	ser	lida	tanto	da	esquerda	para	a	
direita	 como	 ao	 contrário,	 da	 direita	 para	 a	 esquerda.	 Exemplos:	 "osso",	 "arara",	
"socorram-me,	subi	no	onibus	em	marrocos",	"a	grama	é	amarga",	"anotaram	a	data	
da	 maratona".	 Escrever	 a	 função	 recursiva	 int	 palindrome(char	 s[],	 int	 n),	 que	
retorna	1	se	o	string	s	for	um	palíndrome,	ou	retorna	0,	caso	contrário.	
	
6. Escrever	uma	função	recursiva	int	multiplica(int	x,	int	y)	que	retorna	x	*	y.	
	
7. A	 função	 de	 Ackermann	 é	 definida	 para	 valores	 inteiros	 não	 negativos	 m	 e	 n	 da	
seguinte	forma:	
	
 
€ 
A(m,n) =
n + 1 se m = 0
A(m−1,1) se m > 0 e n = 0
A(m−1, A(m,n−1)) se m > 0 e n > 0
⎧ 
⎨ 
⎪ 
⎩ 
⎪ 
	
	
Escrever	 uma	 função	 recursiva	 para	 implementar	 a	 função	 de	 Ackermann.	 Qual	 o	
valor	de	A(3,2)?	Quantas	chamadas	à	função	foram	necessárias	para	calcular	A(3,2)?