Задание 11. Ответы и решения
11.1 (ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующим соотношением:
F(n)=F(n−1)+2⋅F(n−2) при n>2
F(1)=0
F(2)=1
Чему равно значение функции F(6)?
В ответ запишите только натуральное число.
Решение. Вычисляем значения F(3), F(4) и т.д., пользуясь заданным уравнением:
F(3) = 1 + 2*0 = 1
F(4) = 1 + 2*1 = 3
F(5) = 3 + 2*1 = 5
F(6) = 5 + 2*3 = 11
Ответ: 11.
11.2 (ege.yandex.ru) Последовательность чисел Фибоначчи задается рекуррентным соотношением:
F(n)=F(n−1)+F(n−2) при натуральном n>2
F(1)=1
F(2)=1
Чему равно восьмое число в последовательности Фибоначчи?
В ответ запишите только натуральное число.
Решение. Вычисляем значения F(3), F(4) и т.д., пользуясь заданным уравнением:
F(3) = 1 + 1 = 2
F(4) = 2 + 1 = 3
F(5) = 3 + 2 = 5
F(6) = 5 + 3 = 8
F(7) = 8 + 5 = 13
F(8) = 13 + 8 = 21
Ответ: 21.
11.3 . (ege.yandex.ru) Максимальное число L(n) областей, на которые плоскость делится n прямыми, можно вычислить с помощью рекуррентного соотношения:
L(n)=L(n−1)+n при натуральных n≥1
L(0)=1
Каково максимальное число областей, на которые плоскость делится десятью прямыми?
В ответ запишите только натуральное число.
Решение 1. Вычисляем значения L(1), L(2) и т.д., пользуясь заданным уравнением:
L(1) = 1 + 1 = 2
L(2) = 2 + 2 = 4
L(3) = 4 +3 = 7
L(4) = 7 + 4 = 11
L(5) = 11 + 5 = 16
L(6) = 16 + 6 = 22
L(7) = 22 +7 = 29
L(8) = 29 + 8 = 37
L(9) = 37 +9 = 46
L(10) = 46 + 10 =56
Решение 2. Заметим, что L(n) = 1+ 1 + 2+ … + n. Известно, что
1 + 2+ … + n = n*(n+1)/2
(объяснение – здесь)
Поэтому L(n) = 1 + (1 + 2+ … + n) = 1+ n*(n+1)/2
Значит, L(10) = 1+ 10*11/2 = 56
Ответ: 56
11.4. (ege.yandex.ru) Для подсчета минимального числа ходов в головоломке ханойская башня используется функция S(n), которая вычисляется по следующему алгоритму:
S(n)=2⋅S(n−1)+1 при натуральном n>1
S(1)=1
Чему равно значение функции S(7)?
В ответ запишите только натуральное число.
Решение. Вычисляем значения S(2), S(3) и т.д., пользуясь заданным уравнением:
S(2) = 2*1 + 1 = 3
S(3) = 2*3 + 1 = 7
S(4) = 2*7 + 1 = 15
S(5) = 2*15 + 1 = 31
S(6) = 2*31 + 1 = 63
S(7) = 2*63 + 1 = 127
Ответ: 127.
Замечание. Можно доказать, что при любом n выполнено:
S(n) = 2n - 1
Воспользуемся методом математической индукции. При n=1 формула выполнена. Действительно,
21 – 1 = 2 – 1 = 1 = S(1)
Пусть S(n) = 2n – 1. Вычислим значение S(n+1) в соответствии с заданным уравнением. Имеем:
S(n+1) = 2*S(n)+1 = 2*(2n – 1) + 1 =
= 2n+1 – 2 + 1 = 2n+1 – 1
Ч.т.д.
11.5 (ege.yandex.ru) Алгоритмы вычисления значений функции F(n) и Q(n), где n – натуральное число, заданы следующими соотношениями:
F(n)=F(n−1)+2⋅Q(n−1) при n>1
F(1)=1
Q(n)=−2⋅F(n−1)+Q(n−1) при n>1
Q(1)=1
Чему равна сумма F(5)+Q(5)?
В ответ запишите только натуральное число.
Решение. Вычисляем параллельно значения F(2), Q(2), F(3), Q(3) и т.д., пользуясь заданными уравнениями:
F(2) = 1 + 2*1 = 3 Q(2) = -2*1 + 1 = -1
F(3) = 3 + 2*(-1) = 1 Q(3) = -2*3 + (-1) = -7
F(4) = 1 + 2*(-7) =-13 Q(4) = -2*1 + (-7) = -9
F(5) = -13 + 2*(-9) = -31 Q(5) = -2*(-13) + (-9) = 17
Ответ: -14
4 комментария
Объясните что означает оператор Sub в QBasic
Пример задачи
SUB F(n)
PRINT n
IF n <5 THEN
F(n+1)
F(n+3)
END IF
END SUB
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?
Извини, что сразу не ответил - дела, потом - праздники 🙂
Оператоп SUB обозначает начало описания подпрограммы (конец описания - END SUB
В твоем примере F - имя подпрограммы (оно используется при вызове подпрограммы. В сковках после имени указываются аргументы программыю В твоем примере аогумент только один, он обозначен буквой n.
В твоём примере приведена рекурсивная программа то есть при выполнении программы вызывается сама программа - но с другим значением аргумента.
При вызове F(1) происходит вот что.
1) Печатается 1.
2) Т.к. 1 < 5, то затем 3) Выполняется вызов F(2) 4) Выполняется вызов F(4) 5) На этом выполнение вызова F(1) заканчивается. Обозначим через S(k) сумму чисел, которые будут напечатаны при вызове F(k). Из сказанного понятно, что S(1) = 1 +S(2) + S(4) Точно так же можно показать, что S(2) = 2+S(3) +S(5) S(3) = 3 +S(4)+S(6) S(4) = 4 +S(5) + S(7) S(5) = 5; S(6) = 6; S(7)= 7 - в этих случаях условие n<5 ложно и дополнительные вызовы не выполняются. Теперь, двигаясь "сверху вниз", можно вычислить S(4), ..., S(1). Имеем: S(4) = 4+ S(5)+S(7) = 4+5+7=16 S(3) = 3+S(4)+S(6) = 3+16+6 = 25 S(2) = 2+S(3) + S(5) = 2 + 25 +5 = 32 S(1) = 1 + S(2) + S(4) = 1+ 32 +16 49 Ответ: 49 Напиши пож, все ли понятно. Ты не знал, что такое "SUB" в Бейсмке или вообще - что такое подпрограмма? Удаяи!
Это действительно трудная задача ( что и обозначают ** 🙂 ). Отвечаю коротко, если нужно – напишу подробнее.
0. Идея записать соотношения между значениями решений для различных n - совершенно правильная.
1. Подсказка. Из условия видно, что S(1) = F(1) + 1000*G(1) и S(2) = F(2) + 1000*G(2) .
Пользуясь тем, что значения функций F(n), G(n) и S(n) удовлетворяют одному и тому же рекурсивному уравнению, и тем, что это уравнение – линейное, можно доказать, что соотношение
S(n) = F(n) + 1000*G(n)
выполнено для любых n. Отсюда легко найти значение S(11).
2. Эта задача затрагивает тему линейных рекурсивных уравнений (их также называют разностными уравнениями). Они играют большую роль в математике, их свойства во многом аналогичны свойствам дифференциальных уравнений. Про разностные уравнения можно (при желании) поговорить с сильными школьниками, на этот счет есть материалы. В плане подготовки к ЕГЭ эту задачу можно не разбирать 🙂
Успехов! Пишите еше.
Здравствуйте, пробовала решить задачи для самостоятельного решения, прежде, чем дать их ученикам. Получились все задачи кроме 10**.
Никак не могу найти подход к этой задаче. Попробовала составить модель в ЭТ не помогло. Записала соотношения для X(3), X(4)...X(11), затем для F(3)...F(11), G(3)...G(11), S(3)...S(11). А дальше никак не пойму что делать. Подскажите, пожалуйста!