6. PRESENTASJON, DRØFTING OG ANALYSE
6.8 I SAMHANDLING MED ANDRE
Podemos usar definições recursivas para seqüências de objetos, conjuntos de objetos e operações sobre obje- tos, desde que informações básicas sejam conhecidas e novas informações dependam de informações já co- nhecidas.
Os algoritmos recursivos fornecem uma forma natural de resolver certos problemas, através da utilização da mesma tarefa para solucionar uma versão reduzida do problema.
Certas relações de recorrência têm soluções de forma fechada.
Exercícios 2.3
Para os Exercícios 1 a 10, escreva os cinco primeiros valores das seqüências dadas.
Nos Exercícios 11 e 12, prove as propriedades dadas para os números de Fibonacci diretamente da definição. (Não é necessário usar indução.)
18. Os valores p e q são definidos como se segue:
a. Prove que 1 + p = p2 e 1 + q = q2 b. Prove que
c. Use o item (b) para provar que
é uma solução de forma fechada para a seqüência de Fibonacci.
19. Escreva uma definição recursiva para uma progressão geométrica com termo inicial a e razão r (veja Exercício 17 na Seção 2.2).
20. Escreva uma definição recursiva para uma progressão aritmética com termo inicial a e razão d (veja Exercício 18, Seção 2.2).
21. Em um experimento, certa colônia de bactérias tem inicialmente uma população de 50.000. Uma leitura é feita a cada duas horas, e no final de cada duas horas de intervalo há três vezes mais bactérias que antes.
a. Escreva a definição recursiva para A(n), onde A(n) é o número de bactérias presentes no início do n-ésimo período de tempo.
b. No início de qual intervalo existem 1.350.000 bactérias presentes?
22. Uma quantia de 500 unidades monetárias foi investida em uma conta remunerada a uma taxa de juro composto anual de 10%.
a. Escreva a definição recursiva para P(n), a quantia na conta no início do n-ésimo ano. b. Depois de quantos anos a quantia excederá o valor de 700 unidades monetárias? 23. Uma coleção T de números é definida recursivamente por:
1. 2 pertence a T.
2. Se X pertence a T, então X + 3 e 2 . X também pertencem a T.
Quais dos seguintes números pertencem a 77 a. 6 b. 7 c. 19 d. 12
24. Uma coleção M de números é definida recursivamente por: 1. 2 e 3 pertencem a M.
2. Se X e Y pertencem a M, então X . Y também pertence a M.
Quais dos seguintes números pertencem a M?
a. 6 b . 9 c. 16 d. 21 e. 26 f. 54 g. 72 h. 218
25. Uma coleção S de cadeias de caracteres é definida recursivamente por: 1. a e b pertencem a S.
2. Se X pertence a S, então Xb também pertence a S. Quais das seguintes cadeias pertencem a S?
a. a b. ab c. aba d. aaab e. bbbbb
26. Uma coleção W de cadeias de símbolos é definida recursivamente por 1. a,b e c pertencem a W.
2. Se X pertence a W, então a(X)c também pertence a W. Quais das seguintes cadeias pertencem a W?
a. a(b)c b. a(a(b)c)c c. a(abc)c d. a(a(a(a)c)c)c e. a(aacc)c
27. Forneça uma definição recursiva para o conjunto de todas as wffs predicativas unárias em x.
28. Forneça uma definição para o conjunto de todas as fórmulas bem definidas da aritmética de inteiros que envolvam inteiros e os operadores aritméticos +, —, * e /.
29. Forneça uma definição recursiva para o conjunto de todas as cadeias de parênteses bem balanceados. 30. Forneça uma definição recursiva para o conjunto de todas as cadeias binárias contendo um número ím-
par de Os (zeros).
31. Forneça uma definição recursiva para xR, o reverso da cadeia x.
32. Forneça uma definição recursiva para o tamanho da cadeia x. 33. Use a notação BNF para definir o conjunto dos inteiros positivos.
34. Use a notação BNF para definir o conjunto dos números decimais que consistem em um sinal opcional (+ ou —), seguido de um ou mais dígitos, o ponto decimal, zero ou mais dígitos.
35. Forneça uma definição recursiva para o fatorial n!, para
36. Forneça uma definição recursiva para a adição de dois inteiros não-negativos m e n.
37. a. Escreva uma definição recursiva para a operação de obtenção do maior dentre n inteiros, a1 . . ., an,
b. Escreva uma definição recursiva para a operação de obtenção do menor dentre n inteiros, a1 . . ., an,
38. a. Forneça uma definição recursiva para a conjunção de n proposições na lógica proposicional. b. Escreva uma formalização da propriedade associativa da conjunção (equivalência tautológica
2b da Seção 1.1), e use a indução para prová-la.
39. Sejam A e Bv Bv . . ., Bn afirmações. Prove a extensão finita das equivalências distributivas da lógica
proposicional:
e
37. a. Escreva uma definição recursiva para a operação de obtenção do maior dentre n inteiros, a1 . . ., an,
b. Escreva uma definição recursiva para a operação de obtenção do menor dentre n inteiros, a1 . . ., an,
38. a. Forneça uma definição recursiva para a conjunção de n proposições na lógica proposicional. b. Escreva uma formalização da propriedade associativa da conjunção (equivalência tautológica
2b da Seção 1.1), e use a indução para prová-la.
39. Sejam A e B1, B2 ,. . ., Bn afirmações. Prove a extensão finita das equivalências distributivas da lógica
Seção 2.3 Recursão e Relação de Recorrência 81 40. Sejam B1 ,B2 ,. . ., Bn afirmações. Prove a extensão finita da lei de De Morgan:
e
para
Nos Exercícios 41 a 46, escreva o corpo da função recursiva para computar S(n) para uma dada seqüência S. 41. 1 , 3 , 9 , 2 7 , . . . 42. 43. 1,2,4,7, 11, 1 6 , . . . 44. 2,4, 16,256,. .. 45. a, b, a + b, a + 2b, 2a+3b, . . . 46. p, p—q, p+q, p-2q, p + 2q, p-3q, . . .
47. Que valor é computado pelo seguinte algoritmo recursivo em Pascal, para um valor de entrada n? function f(n: integer): integer:
begin
if n = 1 then else
f: = f(n-1)+ 1;
end;
48. A seguinte função recursiva em Pascal é inicialmente chamada com um valor inicial para i igual a 1. L é uma lista (vetor) com 10 inteiros. Qual o procedimento executado pela função?
function g(L: lista; i,x : integer) : integer: begin if i> 10 then g:=0 else if L[i] =x then g:= 10 else g:=g(L,i+1,x); end;
49. Descreva informalmente um algoritmo recursivo para inverter os elementos de uma lista de itens. 50. Descreva informalmente um algoritmo recursivo para computar a soma dos dígitos de um inteiro posi- tivo.
51. Simule a execução do algoritmo SelectionSort para a lista L abaixo; escreva a lista após cada troca que altere o conteúdo da mesma.
4, 10, - 6 , 2, 5
52. Simule a execução do algoritmo SelectionSort para a lista L abaixo; escreva a lista após cada troca que altere o conteúdo da mesma.
53. O algoritmo de busca binaria é utilizado na lista a seguir; x tem o valor "Cuiabá". Enumere os elementos com os quais x é comparado.
Brasília, Campinas, Ipu, Nova Iguaçu, Petrolina, São Paulo, Xerém
54. Um algoritmo de busca binária é usado na lista a seguir, tendo como valor de busca x = "margarina". Indique com quais elementos x é comparado.
açúcar, chocolate, manteiga, margarina, nata, ovos
Nos Exercícios 55 a 60 resolva as relações de recorrência sujeitas às bases apresentadas. 55. S(1) = 5 S(n) = S(n-1) + 5 56. F(l) = 2 F(n) = 2F(n-1) + 2" 57. T(1)= 1 T(n) = 2T(n-\) + 1
(Dica: Veja Exemplo 11.)
58. A(1) = 1
A(n) = A(n— 1) + n para (Dica: Veja Prática 6.)
59. S(1) = 1
S(n) = S(n-1) + 2n - 1 para (Dica: Veja Exemplo 10.)
60. P(1) = 2
P(n) = 2P(n-1) + n2n para
(Dica: Veja Prática 6.)
Para os Exercícios 61 e 62, resolva as relações de recorrência sujeitas às bases apresentadas, usando a aborda- gem de expansão, suposição e verificação.
61. F(1) = 1
F(n) = nF(n — 1) para
62. S(1) = 1
S(n) = nS(n-1) + n!
63. O lixo em um depósito sanitário decompõe-se a uma taxa de 5% ao ano. Se 100 toneladas de lixo são inicialmente depositadas no depósito, quanto permanece não decomposto após 20 anos (ou seja, no iní- cio do 21.° ano)? (Dica: Enuncie e resolva uma relação de recorrência.)
64. Um milhão de unidades monetárias é depositado em uma conta, a uma taxa anual de remuneração de 8%. No final de cada ano um adicional de 100 unidades monetárias é depositado na mesma conta. Qual o montante do valor na conta no final de sete anos (ou seja, no início do 8.° ano)? (Dica: Escreva e resol- va a relação de recorrência. Consulte também o Exercício 17 da Seção 2.2 para obter a fórmula da soma de uma progressão geométrica.)
65. Membros antigos da Sociedade de Pitágoras definiram números figurados como sendo o número de pontos em uma certa configuração geométrica. Os primeiros números triangulares são 1, 3, 6, e 10, e são semelhantes ao diagrama da figura abaixo:
Seção 2.4 Análise de Algoritmos e Mais Sobre Prova de Correção 83 66. Os primeiros números pentagonais (veja exercício anterior) são 1,5, 12, 22, e são semelhantes ao di-
agrama da figura abaixo:
Encontre a fórmula para o n-ésimo número pentagonal. (Dica: Veja Exercício 18 da Seção 2.2 para obter a expressão da soma de uma progressão aritmética.)
67. Use a indução matemática para verificar que a equação (8) desta seção é a solução da relação de recor- rência (6) sujeita à condição básica de S(1) ser conhecida.