Дадаева И.Г._Алгоритмы структуры данных_рус / 10_Алгоритмы и структуры данных_рус
.rtf$$$001
Правильно построенные рекуррентные соотношения:
A) xn = xn -3, x0 = 1
B) xn+1 = xn+5, x0 = 7
C) xn+1 = xn *5
D) xn+1 = xn *6, x0 = 1
E) xn = xn+1+2, x0 = 0
F) xn+1 = xn+1+4, x0 = 6
G) xn+1 = xn+5
H) xn+1 = xn + xn-1, x0 = 1, x1 = 1
{Правильный ответ}=B, D, H
{Сложность}= 3
{Учебник}= Т.Кормен и др. Алгоритмы: построение и анализ, М.: МЦНМО, 2001
{Курс}=2
{Семестр}=3
$$$002
Неправильно построенные рекуррентные соотношения:
A) an+1 =an+(-1)n+1*1.5, a1=2
B) an+1=(an+1)2, a1=2
C) an+1 =an*3, a1=2
D) an+1=(an)3, a1=2
E) xn+1 = xn *8
F) an+1 =an+6, a1=2
G) an =an+1+3, a1=2
H) an+1 =an+1, a1=0
{Правильный ответ}=B, E, G
{Сложность}= 1
{Учебник}= Т.Кормен и др. Алгоритмы: построение и анализ, М.: МЦНМО, 2001
{Курс}=2
{Семестр}=3
$$$003
Корректные примеры рекуррентных соотношений:
A) xn+1 = xn *3.5
B) an+1 = an+1 *5
C) xn+1 =2-xn2, x0=2
D) xn = xn+1 -5, x0=1
E) an =an+1+3, a1=2
F) xn+1 =xn+n, x1=0
G) an+1 =an*n, a0=3
H) xn+1 = xn+1+4, x0 = 6
{Правильный ответ}=C, F, G
{Сложность}= 1
{Учебник}= Т.Кормен и др. Алгоритмы: построение и анализ, М.: МЦНМО, 2001
{Курс}=2
{Семестр}=3