Ad2 - fac

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1359 palavras )
  • Download(s) : 0
  • Publicado : 25 de agosto de 2012
Ler documento completo
Amostra do texto
AD2 - Fundamentos de Algoritmos para Computação

1. (1.0) Usando o Teorema das colunas calcule a seguinte soma: S = 10 · 11 · 12 + 11 · 12 · 13 + 12 · 13 · 14 + · · · 50 · 51 · 52 Resposta: Notemos que: 10 · 11 · 12 + 11 · 12 · 13 + · · · + 50 · 51 · 52 = (1 · 2 · 3 + 2 · 3 · 4 + · · · + 50 · 51 · 52) − (1 · 2 · 3 + 2 · 3 · 4 + · · · + 9 · 10 · 11) Isto ´, e
50 50 9

k(k + 1)(k + 2) =
k=10k=1

k(k + 1)(k + 2) −
k=1

k(k + 1)(k + 2)

Pelo desenvolvimento do exemplo 4, na aula 13, slide n´ mero 29, temos que: u
50 4 k(k + 1)(k + 2) = 6 · C53 k=1

Com racioc´ ınio an´logo, temos que: a
9 4 k(k + 1)(k + 2) = 6 · C12 k=1

Portanto,
50 4 4 4 4 k(k + 1)(k + 2) = 6 · C53 − 6 · C12 = 6(C53 − C12 ) k=10

Obs.: Na avalia¸˜o a distˆncia deve ser colocada a explica¸˜on de 50k(k+1)(k+ ca a ca k=1 4 4 a 2) = 6·C53 e 9 k(k +1)(k +2) = 6·C12 . Para acompanh´-las, consulte o material k=1 das aulas. 2. (1.5) Usando o Teorema do binˆmio de Newton calcule: o
n

kC(n, k)(−3)k
k=0

Resposta:
n n

k · C(n, k) · (−3)k =
k=0 k=0



n! · (−3)k = k!(n − k)!

n

= 0 +
k=0 k=1



n(n − 1)! (−3)k = k · (k − 1)!(n − k)!

n

k=1

n(n − 1)! (−3)k (k − 1)!(n− k)!

Fazendo mudan¸a de vari´vel, k −1 = j, temos que k = j +1 e para k = n, j = n−1. c a Da´ segue: ı,
n

k=1 n−1

n(n − 1)! (−3)k = (k − 1)!(n − k)!

n−1

j=0

n(n − 1)! (−3)j+1 = j!(n − j − 1)!
n−1

=n
j=0

(n − 1)! (−3)j (−3) = (−3)n C(n − 1, j)(−3)j 1n−1−j j!((n − 1) − j)! j=0

Pelo Teorema Binomial, temos:
n−1

(−3)n
j=0

1n−1−j (−3)j C(n − 1, j) = (−3)n(1 −3)n−1 = n(−3)(−2)n−1

3. (1.5) Uma pessoa deve pintar uma sequˆncia de n blocos, n ≥ 1, com as cores e vermelha, azul e branca, cada bloco com uma unica cor tal que blocos consecutivos ´ e n˜o podem ser pintados de branco. Encontre uma rela¸˜o de recorrˆncia para o a ca n´ mero de sequˆncias poss´ u e ıveis (an = o n´ mero de sequˆncias de n blocos pintados u e com as cores vermelha, azul e brancatal que blocos consecutivos n˜o podem ser a pintados de branco). Justifique. Resposta: Para pintar uma sequˆncia de n blocos, n ≥ 1, com as cores vermelha, e azul e branca, cada bloco com uma unica cor tal que blocos consecutivos n˜o podem ´ a ser pintados de branco, devemos proceder da seguinte forma: Se existe um unico bloco, ou seja, se n = 1, ele pode ser pintado de 3 maneiras: ´ vermelho, ouazul, ou branco, ou seja, a1 = 3. Se existem dois blocos, ou seja, se n = 2, podemos pint´-los da seguinte maneira: a • Se pintarmos o primeiro bloco de vermelho, restam trˆs cores para pintarmos e o segundo bloco: vermelho, ou azul, ou branco; • Se pintarmos o primeiro bloco de azul, restam trˆs cores para pintarmos o e segundo bloco: vermelho, ou azul, ou branco; • Se pintarmos o primeiro bloco debranco, restam duas cores para pintarmos o a e segundo bloco: vermelho, ou azul. N˜o podemos pintar de branco, pois n˜o ´ a permitido que blocos consecutivos sejam pintados de branco Da´ a2 = 8 ı,

Se existem 3 blocos, isto ´, n = 3 ent˜o poderemos pintar o primeiro de vermelho e e a nos restam dois blocos para serem pintados, e poderemos pint´-los de acordo com a

a sequˆncia anterior.Analogamente se pintarmos o primeiro de azul. Agora, se e pintarmos de branco, restam dois blocos para serem pintados, mas o segundo s´ o pode ser pintado de vermelho ou azul. Desta forma temos: a3 = 2a2 + 2a1 . Se existem n blocos, n ≤ 3 ent˜o poderemos pintar o primeiro de vermelho e nos a restam n − 1 blocos para serem pintados, e poderemos pint´-los de acordo com a a sequˆncia anterior.Analogamente se pintarmos o primeiro de azul. Agora, se e pintarmos de branco, restam n − 1 blocos para serem pintados, mas o segundo s´ o pode ser pintado de vermelho ou azul. Sendo assim, an = 2an−1 + 2an−2 para n ≥ 3, a1 = 3 e a2 = 8, ou seja:   2an−1 + 2an−2 , n ≥ 3 3 , n=1 an =  8 , n=2 4. (1.0) Para quais valores de r e s o grafo bipartido completo Kr,s ´ euleriano? Juse tifique. Resposta: O...
tracking img