Lista de Exercícios 3 Prof. Marcelo UFMA

Prévia do material em texto

Fundamentos da Computac¸a˜o: Lista 3
Preparac¸a˜o para Prova 3, marcada para 17 de Julho de 2014
Prof. Marcelo - BCT
1
Fundamentos da Computac¸a˜o (Prof. Marcelo - BCT ): Lista 3
Ex. 1 Recursa˜o
(1) Explique com suas pro´prias palavras o que e´ recursa˜o;
(2) Escreva uma func¸a˜o que fac¸a a soma de dois inteiros a + b, de forma recur-
siva, retornando um inteiro como resultado. Utilize o seguinte proto´tipo: int
soma(int,int);
(3) Escreva uma func¸a˜o que fac¸a a subtrac¸a˜o de dois inteiros a − b, de forma
recursiva, retornando um inteiro como resultado. Utilize o seguinte proto´tipo:
int subtracao(int,int);
(4) Escreva uma func¸a˜o que fac¸a a multiplicac¸a˜o de dois inteiros a× b, de forma
recursiva, retornando um inteiro como resultado. Utilize o seguinte proto´tipo:
int multiplicacao(int,int);
(5) Escreva uma func¸a˜o que ca´lcule o piso da divisa˜o de dois inteiros ba
b
c, de forma
recursiva, retornando um inteiro como resultado. Utilize o seguinte proto´tipo:
int divisao(int,int);
(6) Escreva uma func¸a˜o recursiva que retorne um inteiro representando o resto
da divisa˜o de dois inteiros a
b
. Utilize o seguinte proto´tipo: int resto(int,int);
(7) Escreva uma func¸a˜o recursiva que retorne o ma´ximo divisor comum entre
dois inteiros. Utilize o seguinte proto´tipo: int mdc(int,int);
(8) Escreva uma func¸a˜o recursiva que retorne o ma´ximo elemento de um vetor.
A func¸a˜o deve receber um vetor de inteiros e um inteiro representando o indice
do u´ltimo elemento do respectivo vetor. Utilize o seguinte proto´tipo: int max(int
[],int);
(9) Escreva uma func¸a˜o recursiva que retorne o mı´nimo elemento de um vetor.
A func¸a˜o deve receber um vetor de inteiros e um inteiro representando o indice
do u´ltimo elemento do respectivo vetor. Utilize o seguinte proto´tipo: int min(int
[],int);
(10) Escreva uma func¸a˜o recursiva que retorne a me´dia de um vetor. A func¸a˜o
deve receber um vetor de nu´meros reais e um inteiro representando o indice
do u´ltimo elemento do respectivo vetor. Utilize o seguinte proto´tipo: float me-
dia(float [],int);
(11) Escreva uma func¸a˜o recursiva que retorne o fatorial de um nu´mero inteiro.
Utilize o seguinte proto´tipo: int fatorial(int);
(12) Escreva uma func¸a˜o recursiva que receba um inteiro n e ca´lcule o seguinte
somato´rio
∑n
i=1 i. Utilize o seguinte proto´tipo: int somatorio(int);
(13) Escreva uma func¸a˜o recursiva que receba um inteiro n e ca´lcule o blog2 nc,
ou seja, o piso do logaritmo de n na base 2. Utilize o seguinte proto´tipo: int
log2(int);
Pa´gina 2 de 5
Fundamentos da Computac¸a˜o (Prof. Marcelo - BCT ): Lista 3
(14) Escreva uma func¸a˜o recursiva que fac¸a a busca sequencial em um vetor.
A func¸a˜o deve receber um vetor inteiro, um inteiro representando o indice do
u´ltimo elemento desse vetor e um inteiro correpondente ao valor que deve ser
localizado no vetor. Se o elemento for encontrado a func¸a˜o retorna 1, sena˜o
retorna 0. Utilize o seguinte proto´tipo: int busca sequencial(int [], int, int);
(15) Escreva uma func¸a˜o recursiva que fac¸a a busca bina´ria em um vetor. A
func¸a˜o deve receber um vetor inteiro, um inteiro representando o indice do
u´ltimo elemento desse vetor e um inteiro correpondente ao valor que deve ser
localizado no vetor. Se o elemento for encontrado a func¸a˜o retorna 1, sena˜o
retorna 0. Utilize o seguinte proto´tipo: int busca sequencial(int [], int, int);
(16) Escreva uma func¸a˜o recursiva que ordene um vetor inteiro de forma na˜o
decrescente utilizando o algoritmo quicksort. A func¸a˜o deve receber um vetor
inteiro, um inteiro representando o indice do primeiro elemento desse vetor e um
inteiro representando o indice de seu u´ltimo elemento. A func¸a˜o deve modificar
o vetor recebido, e portanto na˜o sera´ necessa´rio retornar nenhum valor. Utilize
o seguinte proto´tipo: void quicksort(int [], int, int);
(17) Escreva uma func¸a˜o recursiva para calcular
(
n
k
)
, dado que
(
n
k
)
=
(
n−1
k
)
+
(
n−1
k−1
)
,(
m
m
)
= 1 e
(
m
1
)
= n. Sua func¸a˜o deve receber dois inteiros n e k, e deve retornar
um inteiro. Utilize o seguinte proto´tipo: int binomio(int, int);
(18) Escreva uma func¸a˜o recursiva para calcular a soma dos d´ıgitos de um inteiro
positivo. Por exemplo, a soma dos d´ıgitos de 345 e´ 12. Sua func¸a˜o recebe um
inteiro e retorna a respectiva soma, tambe´m no formato inteiro. Utilize o seguinte
proto´tipo: int digitos(int);
(19) Escreva uma func¸a˜o recursiva para determinar se os elementos de um vetor
inteiro formam um palindromo. Sua func¸a˜o recebe um vetor inteiro e um inteiro
representando o indice do u´ltimo elemento do referido vetor. Exemplo, v =
[1, 20, 30, 20, 1] e´ palindromo (retornar 1) e w = [20, 30, 31, 20] na˜o e´ (retornar 0).
Utilize o seguinte proto´tipo: int palindromo(int [], int);
(20) Escreva uma func¸a˜o recursiva que resolva o problema “Torres de Hanoi”.
Inicialmente temos 5 discos de diaˆmetro diferentes na estaca A. O problema
consiste em mover os cinco discos da estaca A para C, utilizando a estaca B
como auxiliar. As regras sa˜o as seguintes:
• apenas o disco do topo de uma estaca pode ser movido
• nunca um disco de diaˆmetro maior pode ficar sobre um de diaˆmetro menor
Pa´gina 3 de 5
Fundamentos da Computac¸a˜o (Prof. Marcelo - BCT ): Lista 3
Ex. 2 Apontadores
(1) Explique com suas pro´prias palavras o que sa˜o apontadores;
(2) Explique o uso do operador “&”;
(3) Explique o uso do operador “*”;
(4) O que os programas abaixo imprimem? NA˜O fac¸a no Codeblocks;
A) #inc lude <s t d i o . h>
i n t main ( )
{
i n t x=5, y=3, z ;
i n t ∗p ;
p=&x ;
z=2∗y+(∗p)−x ;
p r i n t f ( ‘ ‘ z=%d ’ ’ , z ) ;
r e turn 0 ;
}
B) #inc lude <s t d i o . h>
i n t main ( )
{
i n t x [ ] ={1 , 2 , 3 , 4 , 5} ;
i n t n=5, i ;
i n t ∗p ;
p=x ;
f o r ( i =0; i<n ; i++)
{
p r i n t f ( ‘ ‘%d\n ’ ’ , ∗ ( p+i ) ) ;
}
re turn 0 ;
}
C) #inc lude <s t d i o . h>
i n t main ( )
{
i n t x [ ]={1 ,2 , 3 , 4 , 5} , y [ ]={6 , 7 , 8 , 9 , 10} ;
i n t n=5, i ;
i n t ∗p , ∗q ;
p=x ;
q=y ;
f o r ( i =0; i<n ; i++) p r i n t f ( ‘ ‘%d\n ’ ’ , ∗(p+i ) + ∗( q+(n−1− i ) ) ) ;
r e turn 0 ;
}
Pa´gina 4 de 5
Fundamentos da Computac¸a˜o (Prof. Marcelo - BCT ): Lista 3
D) #inc lude <s t d i o . h>
i n t main ( )
{
i n t x [ ] ={1 , 2 , 3 , 4 , 5} ;
i n t ∗y [ 5 ] ;
i n t n=5, i ;
i n t ∗∗p ;
p=y ;
f o r ( i =0; i<n ; i++)
{
∗(p+i)=&x [ i ] ;
}
f o r ( i =0; i<n ; i++)
{
p r i n t f ( ‘ ‘%d\n ’ ’ , ∗ (∗ ( p+i ) ) ) ;
}
re turn 0 ;
}
E) #inc lude <s t d i o . h>
i n t maior ( i n t x , i n t y )
{
i f (x>y ) re turn x ;
e l s e re turn y ;
}
i n t main ( )
{
i n t a=6, b=8;
i n t (∗ f ) ( ) ;
f=maior ;
p r i n t f ( ‘ ‘%d\n ’ ’ , f ( a , b ) ) ;
r e turn 0 ;
}
F) #inc lude <s t d i o . h>
i n t mensagem( char msg [ ] )
{
p r i n t f ( ‘ ‘% s \n ’ ’ , msg ) ;
}
i n t main ( )
{
char a [ ] = ‘ ‘ He l l o World ! ’ ’ ;
i n t (∗ f ) ( ) ;
f=mensagem ;
f ( a ) ;
r e turn 0 ;
}
Pa´gina 5 de 5