Algoritmos e Estruturas de dados para Engenharia Elétrica - Poli - P1 2015

Prévia do material em texto

QUEStÃO 1 (2,6 PONTOS) 
Um algoritmo clássico para avaliar expressões aritméticas, inventado por E. W. Dijkstra, recebe um arranjo 
de entrada em que cada posição é ou um parênteses (“(“ e “)”), ou um operador (“+”, “-”, “*” e “/”) ou um 
número (por exemplo, “131”). Por exemplo, uma expressão aritmética é: 
(((12 + 5) * (30 – 26)) / 2) 
Ela seria colocada no arranjo E a seguir (separando os elementos do arranjo por vírgula e usando “<” e “>” 
para indicar o início e o fim do arranjo): 
E = <(,(, (, 12, +, 5, ), *, (, 30, –, 26, ), ), /, 2, )> 
Por simplicidade, a versão do algoritmo aqui usada considera que se deve sempre usar os parênteses para 
definir a prioridade da operação. 
Para processar uma expressão aritmética são usadas duas pilhas. O arranjo é processado da esquerda para a 
direita seguindo as seguintes regras: 
• Operandos são colocados no topo da pilha Operandos; 
• Operadores são colocados no topo da pilha Operadores; 
• Parênteses esquerdos (“(“) são ignorados; 
• Ao encontrar um parêntese direito (“)”), retira-se o operador no topo da pilha Operadores 
(operador) e dois operandos do topo da pilha Operandos (valor1, o primeiro retirado, e 
valor2, o segundo retirado). Executa-se a operação adequada sobre os operandos obtidos e 
coloca-se o resultado no topo da pilha Operandos. 
Quando não houver mais elementos do arranjo de entrada a processar, o resultado da expressão estará no 
topo da pilha de Operandos. 
a) (0,4 pontos) Apresente o estado das pilhas Operadores e Operandos abaixo após 12 elementos do 
arranjo E serem processados (ou seja, até, inclusive, o “26“). Considere que a pilha cresce da esquerda 
para a direita. 
E = <(,(, (, 12, +, 5, ), *, (, 30, –, 26, ), ), /, 2, )> 
Operadores * - 
 
Operandos 17 30 26 
 
b) (1,6 pontos) Complete o algoritmo Avaliar-Expressão-Em-Fila(Q) abaixo que recebe uma Fila de 
elementos Q ao invés de um arranjo. Suponha que sempre é recebida uma expressão válida (ou seja, 
assuma que ela nunca contém erros). Use as funções Push(S, x), Pop(S), Stack-Empty(S), 
Enqueue(Q, x), Dequeue(Q) e Queue-Empty(Q). Para calcular operações simples use as funções 
Soma(a, b) (que faz “a + b”), Divisão(a, b) (que faz “a / b”), Subtração(a, b) (que faz “a – 
b”), Multiplicação(a, b) (que faz “a * b”). 
Avaliar-Expressão-Em-Fila(Q) 
1 Seja Operadores uma nova Pilha 
2 Seja Operandos uma nova Pilha 
3 while not Queue-Empty(Q) 
4 elemento = Dequeue(Q) 
5 if elemento == "+" or elemento == "-" or 
 elemento == "*" or elemento == "/" 
6 Push(Operadores, elemento) 
7 _______________________________________________________________________ 
8 else if elemento == "(" 
9 // ignora 
10 _______________________________________________________________________ 
11 else if elemento == ")" 
12 operador = Pop(Operadores) 
13 valor1 = Pop(Operandos) 
14 valor2 = Pop(Operandos) 
15 if operador == "+" 
16 Push(Operandos, Soma(valor2, valor1)) 
17 else if operador == "-" 
18 Push(Operandos, Subtração(valor2, valor1)) 
19 else if operador == "*" 
20 Push(Operandos, Multiplicação(valor2, valor1)) 
21 else Push(Operandos, Divisão(valor2 valor1)) 
22 _______________________________________________________________________ 
23 _______________________________________________________________________ 
24 _______________________________________________________________________ 
25 _______________________________________________________________________ 
26 _______________________________________________________________________ 
27 _______________________________________________________________________ 
28 else // É um número 
29 Push(Operandos, elemento) 
30 _______________________________________________________________________ 
31 return Pop(Operandos) 
 
c) (0,6 pontos) A tabela a seguir apresenta alguns casos em que a expressão a ser avaliada é inválida. Por 
exemplo, a expressão "((1 + 2) * (1 + 3)" é inválida pois faltou um “)”. Preencha a condição que 
poderia verificar o erro no algoritmo do item (b) e informe entre quais duas linhas deveria ser inserido o 
código de verificação e tratamento do erro (mas não se preocupe com o tratamento). Caso necessário, 
use a função Stack-Size(S) que retorna o número de elementos na Pilha S. 
Caso Linhas Condição 
Faltou um único ")" 
30-31 
not Stack-Empty(Operadores) 
E/OU Stack-Size(Operandos) > 1 
Faltou um único operando 
13-14 
Stack-Empty(Operandos) 
 
Faltou um único operador 
11-12 
Stack-Empty(Operadores) 
 
 
QUEStÃO 2 (2,6 PONTOS) 
Considere a estrutura de dados Tabela de Hashing (também chamada de Tabela de Espalhamento) cuja 
resolução de colisões seja por encadeamento. Nesta estrutura, todos os elementos com mesmo valor de 
hash vão para a mesma posição na tabela de espalhamento e, aqui, em uma lista ligada simples. Considere o 
método de divisão para criar funções de hash, que mapeia uma chave k para uma de m posições na tabela 
por: h(k) = k mod m. 
a) (0,4 pontos) para um m genérico e um número de chaves p genérico, considere o pior caso de valores 
das chaves (aquele que pior utiliza a Tabela de Hashing). Pede-se: 
Quantas comparações serão necessárias se formos buscar, neste pior caso, uma determinada chave k na 
Tabela de Hashing ? p comparações. 
Desenhe a Tabela de Hashing que represente o pior caso: 
 
0 / 
h(k) k1 ... kp / 
... ... 
m-1 / 
 
 
b) (1,2 pontos) Complete o algoritmo Remove-Hash-Lista-Simples(T, k) abaixo que remove um 
dado k (representado na chave de cada elemento) da Tabela de Hashing T, nas condições do enunciado. 
Suponha que cada elemento da lista possui dois atributos: chave e próximo, que aponta para o próximo 
elemento da lista ou é NIL, se for o último elemento da lista. 
Remove-Hash-Lista-Simples(T, k) 
1 atual = T[h(k)] 
2 if atual ≠ NIL 
3 if atual.chave == k 
4 T[h(k)] = atual.proximo 
5 else if atual.proximo ≠ NIL 
6 anterior = atual 
7 atual = atual.proximo 
8 while atual.proximo ≠ NIL and atual.chave ≠ k 
9 anterior = atual 
10 atual = atual.proximo 
11 if atual.chave == k 
12 anterior.proximo = atual.proximo 
 
 
c) (1,0 ponto) Considere uma Tabela de Hashing por endereçamento aberto, em que todo registro fica 
dentro do elemento da tabela cujo endereço é o valor de hash da chave. Considere mais uma vez que o 
método de divisão seja usado para definir o valor de hash e que o tratamento de colisão seja feito por 
sondagem linear. Sejam as funções Hash-Insert(T, k) e Hash-Delete(T,k) dadas a seguir. 
 
 
Hash-Delete(T,k) 
1 j = h(k) 
2 if T[j] == NIL 
3 return NIL 
4 repeat 
5 if T[j].chave == k 
6 T[j] = DELETED 
7 return j 
8 else j = j + 1 
9 if j == T.m 
10 j = 0 
11 until j == h(k) or T[j] == NIL 
12 return NIL 
 
Hash-Insert(T,k) 
1 j = h(k) 
2 repeat 
3 if T[j] == NIL or T[j] == DELETED 
4 T[j].chave = k 
5 return j 
6 else j = j + 1 
7 if j == T.m 
8 j = 0 
9 until j == h(k) 
10 error "overflow" 
Para a seguinte sequência de comandos, indicar o conteúdo da Tabela de 
Hashing de tamanho m = 5, em cada passo: 
 
 0 1 2 3 4 
Hash-Insert(T,0) 
 0 / / / / 
Hash-Insert(T,10) 
 0 10 / / / 
Hash-Insert(T,24) 
 0 10 / / 24 
Hash-Delete(T,10) 
 0 deleted / / 24 
Hash-Insert(T,12) 
 0 deleted 12 / 24 
Hash-Insert(T,4) 
 0 4 12 / 24 
Hash-Delete(T,0) 
 deleted 4 12 / 24 
Hash-Insert(T,18) 
 deleted 4 12 18 24 
Hash-Insert(T,14) 
 14 4 12 18 24 
Hash-Delete(T,4)14 deleted 12 18 24 
 
❙♦❧✉$%♦
❚❡"#❡ ✶ ❈♦♠ #❡❧❛'(♦ ) ❚❛❜❡❧❛ ❍❛-❤✱ ❛--✐♥❛❧❡ ❛ ❛❧2❡#♥❛2✐✈❛ ✈❡&❞❛❞❡✐&❛✿
❆
❆ ❢✉♥'(♦ ❞❡ ❍❛-❤ ❣❛#❛♥2❡ ❛ ❣❡#❛'(♦ ❞❡ ✈❛❧♦#❡- ❞✐❢❡#❡♥2❡- ♣❛#❛ ❝❤❛✈❡- ❞✐❢❡#❡♥2❡-✳
❇
◆❛ ❚❛❜❡❧❛ ❍❛-❤ ❞❡ ❡♥❞❡#❡'❛♠❡♥2♦ ❛❜❡#2♦ ♥❡❝❡--❛#✐❛♠❡♥2❡ ♦ ?♥❞✐❝❡ ❞❛ ♣♦-✐'(♦ ❞❡ ❛#♠❛③❡♥❛♠❡♥2♦ ❞❛ ❝❤❛✈❡ -❡#A
✐❣✉❛❧ ) ❢✉♥'(♦ ❞❡ ❍❛-❤ ❞❡--❛ ❝❤❛✈❡✳
❈
❖ ✉-♦ ❞❡ ❚❛❜❡❧❛ ❍❛-❤ ♥(♦ C ✐♥❞✐❝❛❞♦ D✉❛♥❞♦ -❡ 2❡♠ ✉♠ ❣#❛♥❞❡ ♥E♠❡#♦ ❞❡ ❝❤❛✈❡- ♣♦--?✈❡✐- ♠❛- ❛♣❡♥❛- ✉♠❛
♣❡D✉❡♥❛ ♣❛#2❡ -❡#A ❛#♠❛③❡♥❛❞❛✳
❉
❊♠ ❝❛-♦ ❞❡ ❝♦❧✐-(♦ D✉❛♥❞♦ -❡ ✉-❛ ✉♠❛ ❢✉♥'(♦ ❞❡ ❍❛-❤ ❤✭❝❤❛✈❡✮✱ ❡--❛ ♠❡-♠❛ ❢✉♥'(♦ ❞❡✈❡ -❡# #❡❝❛❧❝✉❧❛❞❛ ❛2C
D✉❡ -❡ ♦❜2❡♥❤❛ ✉♠ ✈❛❧♦# ❛✐♥❞❛ ♥(♦ ✉2✐❧✐③❛❞♦✳
❊
◆❛ ❚❛❜❡❧❛ ❍❛-❤ ♣♦# ❡♥❝❛❞❡❛♠❡♥2♦ ❞❡✜♥✐❞❛ ❡♠ ❛✉❧❛✱ ♥❡♥❤✉♠❛ ❝❤❛✈❡ C ❣✉❛#❞❛❞❛ ❞✐#❡2❛♠❡♥2❡ ♥❛ ♣#I♣#✐❛ 2❛❜❡❧❛✱
❛ D✉❛❧ ❛#♠❛③❡♥❛ ❛♣❡♥❛- ❛♣♦♥2❛❞♦#❡- ♣❛#❛ ❧✐-2❛- ❞❡ ❡❧❡♠❡♥2♦- ❝✉❥❛- ❝❤❛✈❡- ♣♦--✉❛♠ ❝I❞✐❣♦- ❍❛-❤ ❡♠ ❝♦❧✐-(♦✳
❚❡"#❡ ✷ ❈♦♥-✐❞❡#❛♥❞♦ ♦ ❛❧❣♦#✐2♠♦ ❛❜❛✐①♦✱ ❡♠ D✉❡ ▲ C ✉♠❛ ❧✐-2❛ ❧✐❣❛❞❛ -✐♠♣❧❡-✱ ❛--✐♥❛❧❡ ❛ ❛❧2❡#♥❛2✐✈❛ ✈❡&❞❛❞❡✐&❛✳
❉♦✲❙♦♠❡#❤✐♥❣✭▲✮
✶ ❝ ❂ ✵
✷ ① ❂ ▲✳✐♥✐❝✐♦
✸ ✇❤✐❧❡ ① 6= ◆■▲
✹ ② ❂ ①
✺ ✇❤✐❧❡ ②✳♣0♦①✐♠♦ 6= ◆■▲
✻ ✐❢ ②✳♣0♦①✐♠♦✳❝❤❛✈❡ ❂❂ ①✳❝❤❛✈❡
✼ ❝ ❂ ❝ ✰ ✶
✽ ②✳♣0♦①✐♠♦ ❂ ②✳♣0♦①✐♠♦✳♣0♦①✐♠♦
✾ ❡❧"❡ ② ❂ ②✳♣0♦①✐♠♦
✶✵ ① ❂ ①✳♣0♦①✐♠♦
✶✶ &❡#✉&♥ ❝
❆
❖ ❛❧❣♦#✐2♠♦ #❡2♦#♥❛ ❛ D✉❛♥2✐❞❛❞❡ ❞❡ ❡❧❡♠❡♥2♦- ❝♦♠ ❝❤❛✈❡- ✐❣✉❛✐- )- ❞♦ ♣#✐♠❡✐#♦ ❡❧❡♠❡♥2♦ ❞❛ ❧✐-2❛✳
❇
❖ ❛❧❣♦#✐2♠♦ ❞❡✈♦❧✈❡ ❛ D✉❛♥2✐❞❛❞❡ ❞❡ ❡❧❡♠❡♥2♦- ❝♦♠ ❝❤❛✈❡- ❞✐-2✐♥2❛-✳
❈
◆❡♥❤✉♠❛ ❞❛- ❞❡♠❛✐- ❛❧2❡#♥❛2✐✈❛- C ❝♦##❡2❛✳
❉
❖ ❛❧❣♦#✐2♠♦ ❡❧✐♠✐♥❛ 2♦❞♦- ♦- ❡❧❡♠❡♥2♦- ❝✉❥❛- ❝❤❛✈❡- -❡❥❛♠ ✐❣✉❛✐- )- ❞♦ ♣#✐♠❡✐#♦ ❡❧❡♠❡♥2♦ ❞❛ ❧✐-2❛✳
❊
❖ ❛❧❣♦#✐2♠♦ ❝♦♥2❛ ♦- ❡❧❡♠❡♥2♦- ❝♦♠ ❝❤❛✈❡- #❡❞✉♥❞❛♥2❡- ❡ ❡❧✐♠✐♥❛ ❛- #❡❞✉♥❞M♥❝✐❛- ❞❛ ❧✐-2❛✳
❚❡"#❡ ✸ ❙❡❥❛ ❙ ✉♠❛ ♣✐❧❤❛ ♦♥❞❡ ❢♦✐ ♣#♦❝❡--❛❞❛ ❛ -❡D✉O♥❝✐❛ ❞❡ ♦♣❡#❛'P❡-
❊ ❆ ❙ ✯ ❨ ✯ ✯ ✯ ◗ ❯ ❊ ✯ ✯ ✯ ❙ ❚ ✯ ✯ ■ ❖ ✯ ◆ ✯.
◆❡-2❛ -❡D✉O♥❝✐❛ ✉♠❛ ❧❡2#❛ #❡♣#❡-❡♥2❛ ❛ ♦♣❡#❛'(♦ V✉-❤✭❙✱ ❧❡2#❛✮ ❡ ✯ #❡♣#❡-❡♥2❛ ❛ ♦♣❡#❛'(♦ V♦♣✭❙✮✳ ❆--✐♥❛❧❡ ❛ ❛❧2❡#♥❛2✐✈❛
❊❘❘❆❉❆✿
❆
❉✉#❛♥2❡ ❛ ❡①❡❝✉'(♦ ❞❛ -❡D✉O♥❝✐❛ ❞❡ ♦♣❡#❛'P❡-✱ ❛ ♣✐❧❤❛ ❛2✐♥❣✐✉ 2❛♠❛♥❤♦ ♠A①✐♠♦ ✐❣✉❛❧ ❛ ✸✳
❇
❈♦♥-✐❞❡#❛♥❞♦ ❛ ❡①❡❝✉'(♦ ❞❛ -❡D✉O♥❝✐❛ ❞❡ ♦♣❡#❛'P❡-✱ ♣♦❞❡♠♦- ❛✜#♠❛# D✉❡ ❛♣I- ❛ ❡①❡❝✉'(♦ ❞❛- ♦♣❡#❛'P❡- ✷✱ ✹ ❡
✻ ❙ 2❡♠ ❡①❛2❛♠❡♥2❡ ♦ ♠❡-♠♦ ❝♦♥2❡E❞♦ ✭❝♦♥✜❣✉#❛'(♦✮✳
❈
❆♦ ✜♥❛❧ ❞♦ ♣#♦❝❡--❛♠❡♥2♦ ❞❛ -❡D✉O♥❝✐❛ ❞❡ ♦♣❡#❛'P❡-✱ ❛ ♣✐❧❤❛ ❝♦♥2C♠ ❛♣❡♥❛- ♦ ❡❧❡♠❡♥2♦ ■✳
❉
❉✉#❛♥2❡ ❛ ❡①❡❝✉'(♦ ❞❛ -❡D✉O♥❝✐❛ ❞❡ ♦♣❡#❛'P❡-✱ ❛ ♣✐❧❤❛ ✜❝♦✉ ✈❛③✐❛ ❡♠ 2#O- ♠♦♠❡♥2♦-✳
❊
❉✉#❛♥2❡ ❛ ❡①❡❝✉'(♦ ❞❛ -❡D✉O♥❝✐❛ ❞❡ ♦♣❡#❛'P❡-✱ ❛ ♣✐❧❤❛ ❛2✐♥❣✐✉ 2❛♠❛♥❤♦ ✶ ♣♦# ✺ ✈❡③❡-✳
❙♦❧✉$%♦
❚❡"#❡ ✹ ❙❡❥❛ ◗ ✉♠❛ ✜❧❛ ♦♥❞❡ ❢♦✐ ♣/♦❝❡11❛❞❛ ❛ 1❡2✉3♥❝✐❛ ❞❡ ♦♣❡/❛45❡1
❆ ✯ ❙ ❆ ✯ ▼ 9 ✯ ▲ ❊ ✯ ◗ ✯ ✯ ✯ ❯ ✯ ❊.
◆❡1>❛ 1❡2✉3♥❝✐❛ ✉♠❛ ❧❡>/❛ /❡♣/❡1❡♥>❛ ❛ ♦♣❡/❛4?♦ ❊♥2✉❡✉❡✭◗✱ ❧❡>/❛✮ ❡ ✯ /❡♣/❡1❡♥>❛ ❛ ♦♣❡/❛4?♦ ❉❡2✉❡✉❡✭◗✮✳ ❈♦♥1✐❞❡✲
/❛♥❞♦ ❛ ❡①❡❝✉4?♦ ❞❛ 1❡2✉3♥❝✐❛ ❞❡ ♦♣❡/❛45❡1 ❞❛❞❛✱ ❛11✐♥❛❧❡ ❛ ❛❧>❡/♥❛>✐✈❛ ❈❖❘❘❊❚❆✿
❆
❆♦ ✜♥❛❧ ❞❛ ❡①❡❝✉4?♦ ❞❛ 1❡2✉3♥❝✐❛ ❞❡ ♦♣❡/❛45❡1✱ ❛ ✜❧❛ ❝♦♥>M♠ ❛♣❡♥❛1 ❛ ❧❡>/❛ ❊✳
❇
❉✉/❛♥>❡ ❛ ❡①❡❝✉4?♦ ❞❛ 1❡2✉3♥❝✐❛ ❞❡ ♦♣❡/❛45❡1✱ ❛ ✜❧❛ ❛>✐♥❣✐✉ >❛♠❛♥❤♦ ♠Q①✐♠♦ ✐❣✉❛❧ ❛ ✹✳
❈
❉✉/❛♥>❡ ❛ ❡①❡❝✉4?♦ ❞❛ 1❡2✉3♥❝✐❛ ❞❡ ♦♣❡/❛45❡1✱ ❛ ✜❧❛ ✜❝♦✉ ✈❛③✐❛ ❡♠ ✸ ♠♦♠❡♥>♦1✳
❉
❉✉/❛♥>❡ ❛ ❡①❡❝✉4?♦ ❞❛ 1❡2✉3♥❝✐❛ ❞❡ ♦♣❡/❛45❡1✱ ❛ ✜❧❛ ✜❝♦✉ ✈❛③✐❛ ❡♠ ✷ ♠♦♠❡♥>♦1✳
❊
❉✉/❛♥>❡ ❛ ❡①❡❝✉4?♦ ❞❛ 1❡2✉3♥❝✐❛ ❞❡ ♦♣❡/❛45❡1✱ ❤♦✉✈❡ ✉♠ ✉♥❞❡$✢♦✇✳
❚❡"#❡ ✺ ❆11✐♥❛❧❡ ❛ ❛❧>❡/♥❛>✐✈❛ ✈❡(❞❛❞❡✐(❛✿
❆
◆?♦ M ♣♦11V✈❡❧ ✐♠♣❧❡♠❡♥>❛/ ✉♠❛ ❧✐1>❛ ❝✐/❝✉❧❛/ 1❡ ❡1>❛ ♥?♦ ❢♦/ ❞✉♣❧❛♠❡♥>❡ ❧✐❣❛❞❛✳
❇
❊♠ /❡❧❛4?♦ ❛♦1 ❛❧❣♦/✐>♠♦1 ✐♠♣❧❡♠❡♥>❛❞♦1 ❝♦♠ ❧✐1>❛ ❧✐❣❛❞❛ 1✐♠♣❧❡1✱ 1❡✉1 ❡2✉✐✈❛❧❡♥>❡1 ✉1❛♥❞♦ ❧✐1>❛ ❞✉♣❧❛♠❡♥>❡
❧✐❣❛❞❛ ♣♦11✉❡♠ ❛1 1❡❣✉✐♥>❡1 ❝❛/❛❝>❡/V1>✐❝❛1✿ ♦ ❞❡ ❜✉1❝❛ ♥?♦ ♣/❡❝✐1❛ ❞❡ ❛❧>❡/❛4?♦✱ ♦ ❞❡ ✐♥1❡/4?♦ ❞❡✈❡ 1❡/ ❛❧>❡/❛❞♦
♠❛1 1❡♠ ❣❛♥❤♦ ❞❡ ❡✜❝✐3♥❝✐❛✱ ♦ ❞❡ /❡♠♦4?♦ ♣/❡❝✐1❛ ❞❡ ❛❧>❡/❛4?♦ ♠❛1 ✜❝❛ ♠❛✐1 ❡✜❝✐❡♥>❡✳
❈
❊♠ /❡❧❛4?♦ ❛♦ ❛❧❣♦/✐>♠♦ ❞❡ ✐♥1❡/4?♦ ✐♠♣❧❡♠❡♥>❛❞♦ ❝♦♠ ❧✐1>❛ ❧✐❣❛❞❛ 1✐♠♣❧❡1✱ 1❡✉ ❡2✉✐✈❛❧❡♥>❡ ✉1❛♥❞♦ ❧✐1>❛ ❞✉♣❧❛✲
♠❡♥>❡ ❧✐❣❛❞❛ M ♠❛✐1 ❡✜❝✐❡♥>❡ ♥♦ ✉1♦ ❞♦ ❡1♣❛4♦ ❡♠ ♠❡♠X/✐❛ ♣♦/M♠ >❡♥❞❡ ❛ 1❡/ ♠❡♥♦1 ❡✜❝✐❡♥>❡ Y ♠❡❞✐❞❛ ❡♠ 2✉❡
❝/❡1❝❡ ♦ ♥Z♠❡/♦ ❞❡ ❡❧❡♠❡♥>♦1 ✐♥1❡/✐❞♦1 ♥❛ ❧✐1>❛✳
❉
◆❡♥❤✉♠❛ ❞❛1 ❞❡♠❛✐1 ❛❧>❡/♥❛>✐✈❛1 M ❝♦//❡>❛✳
❊
❆ ♣/✐♥❝✐♣❛❧ ✈❛♥>❛❣❡♠ ❞❡ 1❡ ✉>✐❧✐③❛/ ❧✐1>❛ ❞✉♣❧❛♠❡♥>❡ ❧✐❣❛❞❛✱ ❡♠ /❡❧❛4?♦ Y ❧✐1>❛ ❧✐❣❛❞❛ 1✐♠♣❧❡1✱ M ♣♦11✐❜✐❧✐>❛/ 2✉❡
1❡ ❢❛4❛ ✐♥1❡/4?♦ ❞❡ ❡❧❡♠❡♥>♦1 ♥♦ ✐♥V❝✐♦ ❞❛ ❧✐1>❛✳
❚❡"#❡ ✻ ❈♦♥1✐❞❡/❡ ❛1 ❢✉♥45❡1 /❡❝✉/1✐✈❛1 ♥✦ ❡ ❋✐❜✭♥✮ ♣❛/❛ ♥ ✐♥>❡✐/♦ ♣♦1✐>✐✈♦ ❡ 1✉❛1 ❞❡✜♥✐45❡1 ❛❧❣M❜/✐❝❛1✱ 2✉❡ ❡♠❜❛1❛♠
❛ ✐♠♣❧❡♠❡♥>❛4?♦ ❞♦1 ❛❧❣♦/✐>♠♦1 /❡❝✉/1✐✈♦1 ❋❛>♦/✐❛❧✭♥✮ ❡ ❋✐❜♦♥❛❝❝✐✭♥✮✱ /❡1♣❡❝>✐✈❛♠❡♥>❡✳ ❈♦♥1✐❞❡/❡ ❛ 1❡❣✉♥❞❛ ❧✐♥❤❛ ❞❡
❞❡✜♥✐4?♦ ❞❡ ❝❛❞❛ ❢✉♥4?♦ ❝♦♠♦ 1✉❛ ♣❛/>❡ /❡❝✉/1✐✈❛✿
n! =
{
1 1❡ n = 0
n ∗ (n− 1)! 1❡ n ≥ 1.
F ib(n) =
{
1 1❡ n = 0 ♦✉ n = 1
Fib(n− 1) + Fib(n− 2) 1❡ n ≥ 2.
9♦❞❡♠♦1 ❛✜/♠❛/ 2✉❡✿
❆
9❛/❛ ♥❂✷✱ ♦ ❛❧❣♦/✐>♠♦ ❋✐❜♦♥❛❝❝✐✭♥✮ ❢❛③ ✉♠❛ ❝❤❛♠❛❞❛ /❡❝✉/1✐✈❛✳
❇
❖ ❛❧❣♦/✐>♠♦ ❋✐❜♦♥❛❝❝✐✭♥✮✱ 2✉❡ ✐♠♣❧❡♠❡♥>❛ ❛ ❢✉♥4?♦ Fib(n) ♣♦11✉✐ ❝♦♠♦ Z♥✐❝♦ ❝❛1♦ ❜❛1❡ ♥❂✵✳
❈
❖ ❛❧❣♦/✐>♠♦ /❡❝✉/1✐✈♦ ❋✐❜♦♥❛❝❝✐✭♥✮ ❞❡✈❡ >❡/ ❝♦♠♦ Z♥✐❝❛ ❝♦♥❞✐4?♦ ❞❡ >M/♠✐♥♦ ✏✐❢ ♥ ❂❂ ✵ /❡>✉/♥ ✶✑✳
❉
❖ ♥Z♠❡/♦ ❞❡ ❝❤❛♠❛❞❛1 /❡❝✉/1✐✈❛1 ❞♦ ❛❧❣♦/✐>♠♦ ❋❛>♦/✐❛❧✭♥✮ 2✉❛♥❞♦ ❡①❡❝✉>❛❞♦ ♣❛/❛ ♥❂✸ M ✸✳
❊
❖ ❛❧❣♦/✐>♠♦ /❡❝✉/1✐✈♦ ❋❛>♦/✐❛❧✭♥✮ ❞❡✈❡ >❡/ ❝♦♠♦ ❝♦♥❞✐4?♦ ❞❡ >M/♠✐♥♦ ✏✐❢ ♥ ❂❂ ✶ /❡>✉/♥ ✶✑✳
❙♦❧✉$%♦
❚❡"#❡ ✼ ❆!!✐♥❛❧❡ ❛ ❛❧'❡(♥❛'✐✈❛ ❊❘❘❆❉❆✿
❆
❈♦♥❥✉♥'♦! ❞✐♥3♠✐❝♦! !6♦ ❝♦♥❥✉♥'♦! ♠❛♥✐♣✉❧❛❞♦! ♣♦( ❛❧❣♦(✐'♠♦! 9✉❡✱ ❞✉(❛♥'❡ '❛❧ ♠❛♥✐♣✉❧❛;6♦✱ ♣♦❞❡♠ ❝(❡!❝❡(✱
❡♥❝♦❧❤❡( ♦✉ !♦❢(❡( ♦✉'(❛! ♠✉❞❛♥;❛!✳
❇
❯♠ ♣(♦❝❡❞✐♠❡♥'♦ (❡❝✉(!✐✈♦ ❝❤❛♠❛ ❛ !✐ ♠❡!♠♦ ❞✉(❛♥'❡ !✉❛ ❡①❡❝✉;6♦✳ ❚❛✐! ♣(♦❝❡❞✐♠❡♥'♦! ✐♠♣❧❡♠❡♥'❛♠ ❛ 'C❝♥✐❝❛
❞❡ ❞❡❝♦♠♣♦!✐;6♦ ❞✐✈✐❞✐# ♣❛#❛ ❝♦♥)✉✐+,❛#✳
❈
D❛(❛ ❣❛(❛♥'✐( ❛ ✜♥✐'✉❞❡ ❞❡ ✉♠ ❛❧❣♦(✐'♠♦ (❡❝✉(!✐✈♦ C ♣(❡❝✐!♦ ❞❡✜♥✐( ✉♠❛ ❝♦♥❞✐;6♦ ❞❡ ✐♥F❝✐♦✳
❉
❯♠ ❛❧❣♦(✐'♠♦ C ❞✐'♦ ❝♦##❡,♦ !❡✱ ♣❛(❛ ❝❛❞❛ ❡♥'(❛❞❛ ✈G❧✐❞❛ ❡❧❡ ♣❛(❛ ❝♦♠ ❛ !❛F❞❛ ❝♦((❡'❛✳
❊
❯♠❛ ❡+,#✉,✉#❛ ❞❡ ❞❛❞♦+ C ✉♠ ♠❡✐♦ ♣❛(❛ ❛(♠❛③❡♥❛( ❡ ♦(❣❛♥✐③❛( ❞❛❞♦! ❝♦♠ ♦ ♦❜❥❡'✐✈♦ ❞❡ ❢❛❝✐❧✐'❛( ♦ ❛❝❡!!♦ ❡ ❛!
♠♦❞✐✜❝❛;J❡! ❛ ❡!'❡! ❞❛❞♦! ♣♦( ♣(♦❝❡❞✐♠❡♥'♦! ❝♦♠♣✉'❛❝✐♦♥❛✐!✳
❚❡"#❡ ✽ ❈♦♥!✐❞❡(❡ ♦! ❛❧❣♦(✐'♠♦! ❛❜❛✐①♦ ❡ ❛!!✐♥❛❧❡ ❛ ❛❧'❡(♥❛'✐✈❛ ❢❛❧"❛✿
❙❡♠✲♥♦♠❡ ✭❱✱ ♥✮
✶ ✐❢ ♥ ❂❂ ✶
✷ /❡#✉/♥ ❱❬✶❪
✸ ❡❧"❡ ① ❂ ❙❡♠✲♥♦♠❡ ✭❱✱ ♥✲✶✮
✹ ✐❢ ❴❴❴❴❴❴❴❴❴❴❴❴❴❴❴❴❴❴
✺ /❡#✉/♥ ①
✻ ❡❧"❡ /❡#✉/♥ ❱❬♥❪
❙❡♠✲♥♦♠❡✷ ✭❱✱ ♥✮
✶ ① ❂ ❱❬✶❪
✷ ❢♦/ ❥ ❂ ✷ #♦ ♥
✸ ✐❢ ❴❴❴❴❴❴❴❴❴❴❴❴❴❴❴❴❴❴
✹ ①❂❱❬❥❪
✺ /❡#✉/♥ ①
❆
❙❡ ♦ ❡!♣❛;♦ ❞❛ ❧✐♥❤❛ ✸ ❞♦ ❛❧❣♦(✐'♠♦ ❙❡♠✲♥♦♠❡✷ ❢♦( ♣(❡❡♥❝❤✐❞♦ ❝♦♠ ❱❬❥❪ ❁ ① ♦ ❛❧❣♦(✐'♠♦ ❝❛❧❝✉❧❛(G ♦ ♠F♥✐♠♦
❡❧❡♠❡♥'♦ ❡♥'(❡ ♦! ♥ ♣(✐♠❡✐(♦! ❡❧❡♠❡♥'♦! ❞❡ ❱✳
❇
❙❡ ♦ ❡!♣❛;♦ ❞❛ ❧✐♥❤❛ ✹ ❞♦ ❛❧❣♦(✐'♠♦ ❙❡♠✲♥♦♠❡ ❢♦( ♣(❡❡♥❝❤✐❞♦ ❝♦♠ ❱❬♥❪ ❃ ① ♦ ❛❧❣♦(✐'♠♦ ❡♥❝♦♥'(❛(G ♦ ♠G①✐♠♦
❡❧❡♠❡♥'♦ ❡♥'(❡ ♦! ♥ ♣(✐♠❡✐(♦! ❡❧❡♠❡♥'♦! ❞❡ ❱✳
❈
❖ ❛❧❣♦(✐'♠♦ ❙❡♠✲♥♦♠❡ C (❡❝✉(!✐✈♦ ❡ ♦ ❛❧❣♦(✐'♠♦ ❙❡♠✲♥♦♠❡✷ C ✐'❡(❛'✐✈♦✳
❉
➱ ♣♦!!✐✈❡❧ '♦(♥❛( ♦! ❞♦✐! ❛❧❣♦(✐'♠♦! ❡9✉✐✈❛❧❡♥'❡! ❛♣❡♥❛! ♣(❡❡♥❝❤❡♥❞♦ ❛ ❧✐♥❤❛ ✺ ❞♦ ❛❧❣♦(✐'♠♦ ❙❡♠✲♥♦♠❡ ❡ ❛
❧✐♥❤❛ ✸ ❞♦ ❛❧❣♦(✐'♠♦ ❙❡♠✲♥♦♠❡✷ ❝♦♠ ❡①♣(❡!!J❡! ❝♦♠♣❛(❛'✐✈❛!✱ ♥6♦ ♥❡❝❡!!❛(✐❛♠❡♥'❡ ✐❣✉❛✐!✳
❊
❍G ✉♠❛ ❛❧'❡(♥❛'✐✈❛ ❢❛❧+❛ ❡♥'(❡ ❛! ❞❡♠❛✐!✳