SEMANA 3 ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES II - NOTA 10

Prévia do material em texto

3ª SEMANA – ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES II 
 
QUIZZ DA VIDEOAULA – RECURSÃO I 
PERGUNTA 1 
1. Considere o seguinte programa em Python: 
2. def f1(n): 
3. if n >= 1: 
4. return 1 
5. else: 
6. return n * f1(n - 1) 
7. 
print(f1(4)) 
 
Assinale a alternativa correta: 
 
a. O programa irá retornar 1. 
 
b. O programa possui um ou mais erros e não vai executar. 
 
c. O programa vai entrar em loop infinito. 
 
d. O programa irá retornar o fatorial de 4. 
 
e. O programa irá retornar 4. 
 
PERGUNTA 1 
0 em 0 pontos 
 
 
 Considere o seguinte programa em Python: 
def f1(n): 
 if n >= 1: 
 return 1 
 else: 
 return n * f1(n - 1) 
 
print(f1(4)) 
 
Assinale a alternativa correta: 
 
Resposta Selecionada: a. O programa irá retornar 1. 
Respostas: a. O programa irá retornar 1. 
 b. O programa possui um ou mais erros e não vai executar. 
 c. O programa vai entrar em loop infinito. 
 d. O programa irá retornar o fatorial de 4. 
 e. O programa irá retornar 4. 
Comentário da 
resposta: 
Você acertou! Essa é a alternativa correta. Para qualquer valor maior ou igual a 1, o 
programa sempre vai entrar no “if”, retornando o valor 1. 
 
 
 
 
QUIZZ DA VIDEOAULA – RECURSÃO II 
 
PERGUNTA 1 
1. Considere a técnica: armazene os resultados de chamadas de funções custosas e retorne esse valor armazenado 
quando a função for chamada novamente. 
Qual o nome dessa técnica? 
 
a. Sobrecarga 
 
b. Iteração 
 
c. Herança 
 
d. Recursão 
 
e. Memoização 
 
PERGUNTA 1 
0 em 0 pontos 
 
 
Considere a técnica: armazene os resultados de chamadas de funções custosas e retorne esse valor 
armazenado quando a função for chamada novamente. 
Qual o nome dessa técnica? 
 
Resposta Selecionada: e. Memoização 
Respostas: a. Sobrecarga 
 b. Iteração 
 c. Herança 
 d. Recursão 
 e. Memoização 
Comentário da 
resposta: 
Você acertou! Essa é a alternativa correta. Memoização é uma técnica de otimização 
que armazena os resultados de chamadas de funções custosas, e que retorna o valor 
armazenado quando a função é chamada novamente. 
 
 
 
 
 
 
 
 
 
 
 
 
 
QUIZZ OBJETO EDUCACIONAL 
PERGUNTA 1 
Questão referente ao Texto-base - Introdução à Computação Usando Python (Ler: Capítulo 10 - Recursão) - Ljubomir 
Perkovic 
Sobre funções recursivas: 
I. Toda função recursiva que termina terá um ou mais casos bases. 
II. Toda função recursiva terá uma ou mais chamadas recursivas. 
III. Toda função recursiva será mais eficiente que sua equivalente iterativa. 
Estão corretas: 
 
a. Apenas I e II. 
 
b. Apenas I. 
 
c. Apenas II. 
 
d. Apenas III. 
 
e. Todas estão corretas. 
PERGUNTA 1 
0 em 0 pontos 
 
Questão referente ao Texto-base - Introdução à Computação Usando Python (Ler: Capítulo 10 - 
Recursão) - Ljubomir Perkovic 
Sobre funções recursivas: 
I. Toda função recursiva que termina terá um ou mais casos bases. 
II. Toda função recursiva terá uma ou mais chamadas recursivas. 
III. Toda função recursiva será mais eficiente que sua equivalente iterativa. 
Estão corretas: 
 
 
Resposta Selecionada: a. Apenas I e II. 
Respostas: a. Apenas I e II. 
 b. Apenas I. 
 c. Apenas II. 
 d. Apenas III. 
 e. Todas estão corretas. 
 
Comentário da 
resposta: 
Você acertou! Essa é a alternativa correta. Toda função recursiva terá um ou 
mais casos base (quando a função termina) e uma ou mais chamadas recursivas 
(chamada a si mesma). 
 
 
ATIVIDADE AVALIATIVA – 3ª SEMANA – ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES II 
PERGUNTA 1 
1. A recursão ocorre quando uma função chama a si própria. Vale destacar a importância de se saber identificar o ponto 
de parada da função, de modo a evitar que ela seja executada infinitamente. Esse ponto de parada é chamado de “caso 
base” ou "caso básico". 
 
Identifique se são verdadeiras (V) ou falsas (F) as afirmativas a seguir. 
 
I. ( ) O problema da Torre de Hanói é exemplo clássico de um problema resolvido com facilidade por meio da recursão. 
II. ( ) O caso base (ou caso básico) é necessário em toda função recursiva escrita corretamente. 
III. ( ) As funções recursivas em Python apresentam grandes benefícios em relação à melhora da eficiência. 
 
 
Assinale a alternativa que apresenta a sequência correta. 
 
a. V - F - V. 
 
b. F - V - V 
 
c. V - V - F. 
 
d. F - F - V. 
 
e. V - F - F. 
 
PERGUNTA 2 
1. Ao tentar resolver o problema do fatorial de um número, basta multiplicá-lo por todos os seus antecessores até chegar 
ao número 1. Com o uso da recursividade, esse problema pode ser resolvido inicialmente sendo dividido em 
subproblemas menores do mesmo tipo (multiplicando um número por seus antecessores) e tomando um ponto de 
parada da recursão que neste caso deve ser o retorno em 1. Mas isso exige cálculos repetidos. 
 
Após análise do problema apresentado, avalie as asserções a seguir e a relação proposta entre elas. 
 
I. O uso da recursividade exigida em problemas como o cálculo de fatorial ou cálculo da série de Fibonacci podem 
ocasionar problemas. 
PORQUE 
II. Existem chances de que o subproblema resolvido na árvore de recursão já esteja resolvido e continue sendo resolvido 
provocando uma sobrecarga. 
 
A respeito dessas asserções, assinale a alternativa correta. 
 
a. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. 
 
b. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. 
 
c. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
 
d. As asserções I e II são falsas. 
 
e. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
 
 
 
 
 
 
 
 
 
PERGUNTA 3 
1. Considere o seguinte programa em Python: 
2. def f(v, i): 
3. if i == 0: 
4. return v[i] 
5. else: 
6. return min(v[i], f(v, i - 1)) 
7. 
8. l = [5,4,6,8,10,12] 
print(f(l, len(l) - 1)) 
Assinale a alternativa correta: 
 
a. O programa irá imprimir 12. 
 
b. O programa irá imprimir 4. 
 
c. O programa irá imprimir 5. 
 
d. O programa irá imprimir 1. 
 
e. O programa irá imprimir 0. 
 
PERGUNTA 4 
1. A recursividade em Python é apresentada como uma forma para solucionar problemas cujo fundamento é a 
fragmentação de um problema em subproblemas menores de tal forma que a função para trazer a solução chame a si 
mesma até chegar em um problema que tenha uma simplicidade que viabiliza sua resolução de uma forma trivial. Todos 
os algoritmos recursivos devem obedecer a três leis importantes, apontadas em 1, 2 e 3. Sobre tais leis, avalie as 
afirmações a seguir, e relacione-as adequadamente aos termos às quais se referem. 
 
 
1. Primeira lei. 
2. Segunda lei. 
3. Terceira lei. 
 
 
I. Deve mudar seu estado para se aproximar do caso básico. 
II. Deve chamar a si mesmo, recursivamente. 
III. Deve possuir um caso básico. 
 
 
Assinale a alternativa que correlaciona adequadamente os dois grupos de informação. 
 
a. 1-III; 2-II; 3-I. 
 
b. 1-I; 2-III; 3-II. 
 
c. 1-I; 2-II; 3-III. 
 
d. 1-III; 2-I; 3-II. 
 
e. 1-II; 2-I; 3-III. 
 
 
 
 
 
 
 
 
 
 
PERGUNTA 5 
1. O algoritmo de busca binária considera um vetor ordenado de n elementos para realizar a varredura dos elementos, 
por isso é possível implementar um algoritmo mais eficiente do que aquele que utiliza a busca sequencial. Adotando o 
paradigma dividir para conquistar, o problema global é dividido em subproblemas, o que faz com que o espaço de busca 
se reduza à metade a cada iteração do algoritmo. 
 
 
Com relação ao algoritmo de busca binária apresentado, avalie as afirmações a seguir. 
 
 
I. Se n for um valor pequeno, o custo adicional para ordenar a lista pode não compensar. 
II. As comparações requeridas começam com uma lista de tamanho n/2, depois n/4, depois n/6, depois n/8 e assim 
sucessivamente enquanto o elemento procurado não tiver sido encontrado, e a lista nãofor vazia. 
III. O número máximo de comparações requeridas é dado por nlog(n). 
IV. A análise da busca binária elimina metade dos itens que restam a cada comparação. 
 
 
Está correto que se afirma em: 
 
a. III e IV, apenas. 
 
b. II e III, apenas. 
 
c. II e IV, apenas. 
 
d. I e III, apenas. 
 
e. I e IV, apenas. 
 
PERGUNTA 6 
1. As listas em Python permitem listar informações dentro de uma única variável para que elas sejam utilizadas dentro do 
código. Uma prática comum ao se trabalhar com listas é a utilização de informações dentro dela, já que uma lista 
comporta uma estrutura de dados com itens organizados linearmente que podem ser acessados por meio de um índice. 
Essa tarefa de acesso pode ser facilitada diante de uma ordenação que simplifica o trabalho das informações contidas 
na lista. 
 
 
Assinale a alternativa que representa a função cujo objetivo é a ordenação das informações de uma lista. 
 
 
a. list() 
 
b. pop() 
 
c. remove() 
 
d. index() 
 
e. sorted() 
 
 
 
 
 
 
 
 
 
 
 
P E R G U N T A 7 
1. A busca binária confere inicialmente o elemento do meio da lista, que se encontra ordenada em ordem 
crescente. Caso o elemento procurado seja menor que o elemento intermediário, é feita a busca binária ao lado 
esquerdo do intermediário, porém caso o procurado seja maior que o intermediário, a busca ocorre ao lado direito. 
 
 
Assim, analise o algoritmo abaixo, que apresenta uma função iterativa que faz a busca binária. 
 
 
 
Fonte: Elaborada pela autora. 
 
Com relação ao algoritmo apresentado, avalie as afirmações a seguir. 
 
 
I. Trata-se de um algoritmo que adota a estratégia “dividir para conquistar”. 
II. As divisões são int, por isso a variável middle faz uso da função de retorno. 
III. Middle é um ponto médio que divide a matriz em duas partes. 
IV. Quando determinado número da lista apontado pela variável middle for igual ao conteúdo da variável key, encontra-
se o elemento procurado. 
 
 
Está correto que se afirma em: 
 
a. I, II e III, apenas. 
 
b. III e IV, apenas. 
 
c. I e III, apenas. 
 
d. I, III e IV, apenas. 
 
e. II e IV, apenas.