matma dyskretna 10

background image

Matematyka dyskretna

zadania warte są 1 punkt

Krzysztof Misztal

07-01-2013

Zadanie 1. Rozwiąż rekurencje:

T (n) = 4T (n − 1) + 2

n

, T (0) = 6,

T (n) = 3T (n − 1) + n, T (0) = 10,

T (n) = 2T (n − 1) + 2, T (0) = 1 oraz porównaj z T (n) = 3T (n − 1) + 3, T (0) = 1,

T (n) = 2T (n − 1) + n2

n

, T (0) = 1,

T (n) = 2T (n − 1) + n

3

2

n

, T (0) = 2,

T (n) = rT (n − 1) + r

n

, T (0) = 1,

T (n) = rT (n − 1) + s

n

, T (0) = 1,

Zadanie 2. Ciąg Fibonacciego dany jest wzorem

T (n) =

(

T (n − 1) + T (n − 2),

n > 1

1,

n = 0 lubn = 1

• Wypisz kolka pierwszych wyrazów ciągu

• Pokaż, że



1 +

5

2



n



1

5

2



n

są rozwiązaniami równania T (n) = T (n − 1) + T (n − 2).

• Czy

c

1



1 +

5

2



n

+ c

2



1

5

2



n

jest rozwiązaniem równania T (n) = T (n − 1) + T (n − 2) dla każdego c

1

, c

2

R?

• Znajdź takie stałe c

1

, c

2

R aby ciąg Fibonaciego był zadany wzorem

T (n) = c

1



1 +

5

2



n

+ c

2



1

5

2



n

1


Wyszukiwarka

Podobne podstrony:
matma dyskretna 05 id 287941 Nieznany
matma dyskretna 04 id 287940 Nieznany
matma dyskretna 02
SpisTreściDoRomka, studia, Matma, Matma Dyskretna
matma dyskretna 06
matma dyskretna-09
matma dyskretna-01
matma dyskretna-02
matma dyskretna-03
matma dyskretna 08
Matma Dyskretna Vol 2 Arytmetyka(zadania przyklady)
matma dyskretna 03
matma dyskretna 01
matma dyskretna 07
Romekbeta2.0, studia, Matma, Matma Dyskretna
matma dyskretna 05 id 287941 Nieznany
matma dyskretna 04 id 287940 Nieznany

więcej podobnych podstron