Matematyka dyskretna 1/Test 2: Rekurencja

From Studia Informatyczne

Niech \displaystyle S_0=\left\lbrace 0 \right\rbrace oraz \displaystyle S_{i+1}=S_i \cup \left\lbrace \left\vert S_i \right\vert \right\rbrace . Suma \displaystyle \bigcup_{i=0}^{\infty}S_i jest:

zbiorem jednoelementowym \displaystyle \left\lbrace 0 \right\rbrace

zbiorem skończonym

zbiorem wszystkich liczb naturalnych

zbiorem nieskończonym

Niech \displaystyle S_0=\left\lbrace 10 \right\rbrace oraz \displaystyle S_{i+1}=S_i \cup \left\lbrace \left\vert S_i \right\vert \right\rbrace . Suma \displaystyle \bigcup_{i=0}^{\infty}S_i jest:

zbiorem jednoelementowym \displaystyle \left\lbrace 10 \right\rbrace

zbiorem skończonym \displaystyle \left\lbrace 0,1,2,3,4,5,6,7,8,9,10 \right\rbrace

zbiorem wszystkich liczb naturalnych

zbiorem wszystkich liczb naturalnych poza liczbą \displaystyle 0


Niech \displaystyle a_0=1 oraz \displaystyle a_n=a_0+a_1+\ldots+a_{n-1} . Ciąg \displaystyle a_n jest:

ciągiem arytmetycznym

ciągiem geometrycznym

ciągiem o wyrazach \displaystyle a_n=2^{n-1}

ciągiem Fibonacci'ego


Przy modyfikacji problemu przenoszenia Wież Hanoi i dopuszczeniu czterech wież zamiast trzech, liczba \displaystyle H_n ruchów potrzebnych do przeniesienia \displaystyle n krążków wyraża się zależnością:

\displaystyle H_n=2H_{n-1}+1

\displaystyle H_n=2H_{n-2}+3

\displaystyle H_n=2H_{n-1}+3

\displaystyle H_n=2H_{n-2}+1


Które z równości są prawdziwe dla liczb Fibonacci'ego:

\displaystyle f_{n+2}=f_{n+1}+f_n

\displaystyle f_{n+2}=f_n+f_{n-1}

\displaystyle f_{n+2}=f_n+f_{n-1}+\ldots+f_1+f_0-1

\displaystyle f_n=\frac{1}{\sqrt{5}} \left[\left( \frac{1+\sqrt{5}}{2} \right)^n-\left( \frac{1-\sqrt{5}}{2} \right)^n\right] .


Niech \displaystyle a_0=2 , zaś \displaystyle a_1=1 , oraz ponadto \displaystyle a_n=a_{n-1}+2a_{n-2} . Postać zwarta ciągu \displaystyle a_n , to:

\displaystyle a_n=\left( -2 \right)^n+3^n

\displaystyle a_n=\left( -1 \right)^n+2^n

\displaystyle a_n=-2^n+3

\displaystyle a_n=2\left( \frac{1}{2} \right)^n


Drzewo binarne o wysokości \displaystyle 4 ma szerokość:

co najwyżej \displaystyle 16

co najwyżej \displaystyle 8

co najmniej \displaystyle 4

co najmniej \displaystyle 5


Każde zdanie logiczne zbudowane wyłącznie z jednej zmiennej \displaystyle a , implikacji \displaystyle \Rightarrow oraz poprawnego nawiasowania jest:

równoważne zdaniu \displaystyle a

równoważne zdaniu \displaystyle a lub jest tautologią

tautologią

równoważne zdaniu \displaystyle \neg a lub zdaniu \displaystyle a