Алгебра
Английский
Биология
География
Геометрия
История
Русский
Обществознание
Физика
Химия
Информатика
Литература
Математика1. Определите, сколько символов выведет эта процедура при вызове F(28):
Ответ:
Логика такая: Каждый вызов функции F(n) выводит один символ '*' в начале. Затем, если n > 1, вызываются F(n-1) и F(n-2). Нужно посчитать общее количество выведенных символов.
Считаем рекурсивно:
- F(28) выводит 1 символ, затем вызывает F(27) и F(26).
- F(27) выводит 1 символ, затем вызывает F(26) и F(25).
- И так далее...
Заметим, что количество вызовов F(n) равно числу Фибоначчи. F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, ...
Нам нужно найти количество символов, выведенных при вызове F(28). Это значит, нам нужно вычислить F(28) = F(27) + F(26) + 1.
Т.к. каждый вызов F(n) выводит один символ '*', то общее количество выведенных символов будет равно количеству вызовов функции F.
Пусть C(n) - количество символов выведенных при вызове F(n).
C(n) = 1 + C(n-1) + C(n-2), если n > 1, C(n) = 1, если n <= 1.
Вычисляем значения C(n) для небольших n:
- C(0) = 1
- C(1) = 1
- C(2) = 1 + 1 + 1 = 3
- C(3) = 1 + 3 + 1 = 5
- C(4) = 1 + 5 + 3 = 9
- C(5) = 1 + 9 + 5 = 15
- C(6) = 1 + 15 + 9 = 25
Продолжим вычисления до C(28):
Показать пошаговые вычисления
- C(7) = 1 + 25 + 15 = 41
- C(8) = 1 + 41 + 25 = 67
- C(9) = 1 + 67 + 41 = 109
- C(10) = 1 + 109 + 67 = 177
- C(11) = 1 + 177 + 109 = 287
- C(12) = 1 + 287 + 177 = 465
- C(13) = 1 + 465 + 287 = 753
- C(14) = 1 + 753 + 465 = 1219
- C(15) = 1 + 1219 + 753 = 1973
- C(16) = 1 + 1973 + 1219 = 3193
- C(17) = 1 + 3193 + 1973 = 5167
- C(18) = 1 + 5167 + 3193 = 8361
- C(19) = 1 + 8361 + 5167 = 13529
- C(20) = 1 + 13529 + 8361 = 21891
- C(21) = 1 + 21891 + 13529 = 35421
- C(22) = 1 + 35421 + 21891 = 57313
- C(23) = 1 + 57313 + 35421 = 92735
- C(24) = 1 + 92735 + 57313 = 150049
- C(25) = 1 + 150049 + 92735 = 242785
- C(26) = 1 + 242785 + 150049 = 392835
- C(27) = 1 + 392835 + 242785 = 635621
- C(28) = 1 + 635621 + 392835 = 1028457
Ответ: 1028457
Похожие
- 2. Алгоритм вычисления функции F(n) задан следующими соотношениями: F(n)=2.nn. п + 1 при п> 25 F(n)=F(n+2)+2F(n+3), если п 25 Определите количество натуральных значений и из отрезка [1; 1000], при которых значение F(п) кратно 11.
- 3. Алгоритм вычисления функции F(п) задан следующими соотношениями: F(n)=nn+3 +9, при п 15 F(n)=F(n-1)+п-2, при п> 15, кратных 3 F(n)=F(n-2)+ n + 2, при п > 15, не кратных 3 Определите количество натуральных значений и из отрезка [1; 1000], для которых все цифры значения F(n) чётные.
- 4. Алгоритм вычисления функции F(n), где и – натуральное число, задан следующими соотношениями: F(n) = 1, если п = 1 F(n)=nF(n-1) + 1, если п> 1. Чему равно значение выражения F(3303) / F(3300)? В ответе укажите только целую часть числа.
- 5. Алгоритм вычисления функции F(n), где и – натуральное число, задан следующими соотношениями: F(n)=п, если п≥ 10 000, F(n)=1+F(n/2), если п < 10 000 и п чётное, F(n)=n²+F(n+2), если п< 10 000 и и нечётное. Чему равно значение выражения F(192) - F(9)?
