Recursão Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Recursão – Teoria dos Grafos e Análise de Algoritmos 
Exercícios
1. Uma progressão aritmética é uma sequência da forma a, a + d, a + 2d, a + 3d, …, isto
é, a sequência começa com o número a e cada termo sucessivo é obtido do anterior
adicionado d (a diferença comum entre dois termos quaisquer). A progressão aritmética
geral pode ser definida recursivamente por a1 = a e ak + 1 = ak + d para k ≥ 1. Nesse
contexto, encontre a solução geral para a progressão aritmética assinalando a alternativa
correta. 
Resposta: B
A sequência começa com o número e cada termo sucessivo é obtido do anterior𝑎
adicionado (a diferença comum entre dois termos quaisquer). Por exemplo,𝑑
(i) = 5, = 3: 5,8,9,11, …𝑎 𝑑
(ii) = 2, = 5: 2,7,12,17, …𝑎 𝑑
(iii) = 1, = 0: 1,1,1,1,1, …𝑎 𝑑
A progressão aritmética geral pode ser definida recursivamente por 1 = +1 = + 𝑎 𝑎 𝑒 𝑎𝑘 𝑎𝑘 𝑑
para ≥ 1.𝑘
A solução é = + ( − 1)d𝑎𝑛 𝑎 𝑛
2. Para descrever os elementos de um conjunto, encontramos usualmente três
mecanismos:
Resposta: D.
 = { , , , , … }𝑆 𝑏 𝑎𝑏𝑐 𝑎𝑎𝑏𝑐𝑐 𝑎𝑎𝑎𝑏𝑐𝑐𝑐
 𝑏 ∈ 𝑆
 { , ã ∈ ∈𝑠𝑒 𝑥 𝑆 𝑒𝑛𝑡 𝑜 𝑎𝑥𝑐 𝑆
é a única que permite definir de maneira correta o conjunto a partir da base pela𝑏 ∈ 𝑆
aplicação sucessiva do passo de indução. Por exemplo, para as próximas duas palavras
do conjunto desejado, temos , então e , então .∈ ∈ ∈ ∈𝑠𝑒 𝑏 𝑆 𝑎𝑏𝑐 𝑆 𝑠𝑒 𝑎𝑏𝑐 𝑆 𝑎𝑎𝑏𝑐𝑐 𝑆
3. A recursão pode ser usada para definir sequências, funções e conjuntos. As sequências
podem ser definidas a partir do primeiro termo da sequência, a0, e de uma regra para
encontrar um termo a partir do anterior, an+1. Quando definimos uma sequência
recursivamente, especificamos como os seus termos são encontrados a partir de termos
anteriores.
Nesse contexto, considere a sequência definida por:
a1=2
a2=2
a3=6
an=3 * an-3, Para n > 3
Calcule a4, a5, a6 e assinale a alternativa correta:
Resposta: A. 6, 6, 18.
4 = 3 4−3 = 3 1 = 3 2 = 6.𝑎 ∗ 𝑎 ∗ 𝑎 ∗
5 = 3 5−3 = 3 2 = 3 2 = 6.𝑎 ∗ 𝑎 ∗ 𝑎 ∗
6 = 3 6−3 = 3 3 = 3 6 = 18.𝑎 ∗ 𝑎 ∗ 𝑎 ∗
4. O conjunto de todas as cadeias (palavras ou strings) de comprimento finito de símbolos
sobre um alfabeto A é denotado por A*. A definição recursiva de A* é:
I - A cadeia vazia, denotada por ε , pertence a A*.
II - Um único símbolo qualquer de A pertence a A*.
III - Se x e y são cadeias em A*, então a concatenação xy também pertence a A*.
Dado o alfabeto A=｛0,1,2｝, apresente as cinco menores cadeias de A*:
Resposta: E. ε,0,1,2,00
Pela regra I, temos, inicialmente A*=｛ε｝
Pela regra II, temos que A*={ε,0,1,2}
Pela regra III, temos que A*={ε,0,1,2,00}
5. Considerando que usamos duas etapas para definir uma função com o conjunto dos
números inteiros não negativos como seu domínio, a saber: passo base, em que
especificamos o valor da função em zero; e o passo recursivo, em que fornecemos uma
regra para encontrar seu valor em um número inteiro a partir dos valores nos números
inteiros menores. Neste contexto, suponha que fseja definida recursivamente por: f0 = 3,
fn + 1 = 2fn + 3, encontre f1, f2, f3ef(4), assinalando a alternativa correta.
Resposta: C.
A partir da definição recursiva, temos que:
(1) = 2 (0) + 3 = 2 . 3 + 3 = 9𝑓 𝑓
(2) = 2 (1) + 3 = 2 . 9 + 3 = 21𝑓 𝑓
(3) = 2 (2) + 3 = 2 . 21 + 3 = 45𝑓 𝑓
(4) = 2 (3) + 3 = 2 . 45 + 3 = 93𝑓 𝑓
	Recursão – Teoria dos Grafos e Análise de Algoritmos
	Exercícios