КАРТОЧКИ
ТЕСТЫ
Главная
Курсы
Куратор
Подписка
16. Рекурсивные алгоритмы: все задания
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=3$ при $n=1$;
$F(n)=n+2+F(n-1)$, если $n>1$.
Чему равно значение выражения $F(2023)-F(2021)$?
Выразим значения функции через $F(2021)$.
$F(2022)=2022+2+F(2021)=2024+F(2021).$
$F(2023)=2023+2+F(2022)=2025+F(2022).$
Подставим значение $F(2022)$:
$F(2023)=2025+2024+F(2021).$
Тогда: $F(2023)-F(2021)=2025+2024=4049.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n=1$;
$F(n)=n-2+F(n-1)$, если $n>1$.
Чему равно значение выражения $F(2024)-F(2022)$?
Выразим значения функции через $F(2022)$.
$F(2023)=2023-2+F(2022)=2021+F(2022).$
$F(2024)=2024-2+F(2023)=2022+F(2023).$
Подставим значение $F(2023)$:
$F(2024)=2022+2021+F(2022).$
Тогда: $F(2024)-F(2022)=2022+2021=4043.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=n$ при $n\geqslant2025$;
$F(n)=n+3+F(n+3)$, если $n<2025$.
Чему равно значение выражения $F(2018)-F(2022)$?
Вычислим $F(2018)$:
$F(2018)=2018+3+F(2021)=2021+F(2021).$
$F(2021)=2021+3+F(2024)=2024+F(2024).$
$F(2024)=2024+3+F(2027)=2027+F(2027).$
Так как $2027\geqslant2025$, получаем:
$F(2027)=2027.$
Следовательно:
$F(2024)=2027+2027=4054.$
$F(2021)=2024+4054=6078.$
$F(2018)=2021+6078=8099.$
Вычислим $F(2022)$:
$F(2022)=2022+3+F(2025)=2025+F(2025).$
Так как $2025\geqslant2025$, получаем:
$F(2025)=2025.$
Следовательно:
$F(2022)=2025+2025=4050.$
Тогда: $F(2018)-F(2022)=8099-4050=4049.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=(n+1)/2+F(n-1)$, если $n>1$ и при этом $n$ нечётно;
$F(n)=2\cdot F(n-1)+1$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(33)$?
Примечание. При вычислении значения $F(n)$ используется операция целочисленного деления.
Так как $33=2\cdot16+1$, рассмотрим значения функции для нечётных аргументов. Обозначим:
$G(k)=F(2k+1).$
Тогда для чётного аргумента $2k$:
$F(2k)=2\cdot F(2k-1)+1=2\cdot G(k-1)+1.$
Для следующего нечётного аргумента:
$G(k)=F(2k+1)=\dfrac{2k+2}{2}+F(2k).$
Следовательно:
$G(k)=k+1+2\cdot G(k-1)+1=2\cdot G(k-1)+k+2.$
Введём выражение:
$H(k)=G(k)+k+4.$
Тогда:
$H(k)=2\cdot G(k-1)+k+2+k+4=2\cdot G(k-1)+2k+6.$
Получаем:
$H(k)=2\cdot\bigl(G(k-1)+(k-1)+4\bigr)=2\cdot H(k-1).$
Начальное значение:
$H(0)=G(0)+4=F(1)+4=0+4=4.$
Поэтому:
$H(k)=4\cdot2^k=2^{k+2}.$
Значит:
$G(k)=2^{k+2}-k-4.$
Вычислим значение при $k=16$:
$F(33)=G(16)=2^{18}-16-4=262144-20=262124.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=2$ при $n<3$;
$F(n)=F(n-2)+F(n-1)-n$, если $n>2$ и при этом $n$ чётно;
$F(n)=F(n-1)-F(n-2)+2\cdot n$, если $n>2$ и при этом $n$ нечётно.
Чему равно значение функции $F(32)$?
Рассмотрим нечётное число $n=2k+1$:
$F(2k+1)=F(2k)-F(2k-1)+4k+2.$
Для чётного числа $2k$:
$F(2k)=F(2k-2)+F(2k-1)-2k.$
Подставим это выражение:
$F(2k+1)=F(2k-2)+F(2k-1)-2k-F(2k-1)+4k+2=F(2k-2)+2k+2.$
Теперь найдём следующее чётное значение:
$F(2k+2)=F(2k)+F(2k+1)-(2k+2).$
Подставим найденное выражение:
$F(2k+2)=F(2k)+F(2k-2)+2k+2-(2k+2)=F(2k)+F(2k-2).$
Следовательно, каждое чётное значение функции равно сумме двух предыдущих чётных значений.
Начальные значения:
$F(2)=2.$
$F(3)=F(2)-F(1)+2\cdot3=2-2+6=6.$
$F(4)=F(2)+F(3)-4=2+6-4=4.$
Последовательно вычислим чётные значения:
$F(6)=F(4)+F(2)=4+2=6.$
$F(8)=F(6)+F(4)=6+4=10.$
$F(10)=F(8)+F(6)=10+6=16.$
$F(12)=F(10)+F(8)=16+10=26.$
$F(14)=F(12)+F(10)=26+16=42.$
$F(16)=F(14)+F(12)=42+26=68.$
$F(18)=F(16)+F(14)=68+42=110.$
$F(20)=F(18)+F(16)=110+68=178.$
$F(22)=F(20)+F(18)=178+110=288.$
$F(24)=F(22)+F(20)=288+178=466.$
$F(26)=F(24)+F(22)=466+288=754.$
$F(28)=F(26)+F(24)=754+466=1220.$
$F(30)=F(28)+F(26)=1220+754=1974.$
$F(32)=F(30)+F(28)=1974+1220=3194.$
20
Алгоритм вычисления функций $F(n)$ и $G(n)$, где $n$ — целое число, задан следующими соотношениями:
$F(n)=2\cdot(G(n-3)+8);$
$G(n)=2\cdot n$, если $n<10$;
$G(n)=G(n-2)+1$, если $n\geqslant10$.
Чему равно значение выражения $F(15548)$?
Подставим значение аргумента в формулу функции $F$:
$F(15548)=2\cdot(G(15548-3)+8)=2\cdot(G(15545)+8).$
При каждом применении рекурсии аргумент функции $G$ уменьшается на $2$, а значение увеличивается на $1$.
Число $15545$ нечётное, поэтому будем уменьшать его до наибольшего нечётного числа, меньшего $10$, то есть до $9$.
Количество применений рекурсии:
$\dfrac{15545-9}{2}=\dfrac{15536}{2}=7768.$
Следовательно:
$G(15545)=G(9)+7768.$
Так как $9<10$, получаем:
$G(9)=2\cdot9=18.$
Тогда:
$G(15545)=18+7768=7786.$
Вычислим значение функции $F$:
$F(15548)=2\cdot(7786+8)=2\cdot7794=15588.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n=1$;
$F(n)=(n-1)\cdot F(n-1)$, если $n>1$.
Чему равно значение выражения $\dfrac{F(2024)-3\cdot F(2023)}{F(2022)}$?
По рекуррентной формуле:
$F(2024)=2023\cdot F(2023).$
Тогда:
$F(2024)-3\cdot F(2023)=2023\cdot F(2023)-3\cdot F(2023)=2020\cdot F(2023).$
Также:
$F(2023)=2022\cdot F(2022).$
Подставим это значение:
$\dfrac{F(2024)-3\cdot F(2023)}{F(2022)}=\dfrac{2020\cdot2022\cdot F(2022)}{F(2022)}=2020\cdot2022.$
Вычислим: $2020\cdot2022=4084440.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=2\cdot F(n-1)+2$, если $n>1$ и при этом $n$ нечётно;
$F(n)=n/2+F(n-1)$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(30)$?
Примечание. При вычислении значения $F(n)$ используется операция целочисленного деления.
Обозначим через $A_k$ значение функции для чётного аргумента:
$A_k=F(2k).$
Для нечётного числа $2k-1$ получаем:
$F(2k-1)=2\cdot F(2k-2)+2=2\cdot A_{k-1}+2.$
Тогда:
$A_k=F(2k)=k+F(2k-1)=2\cdot A_{k-1}+k+2.$
Начальное значение:
$A_1=F(2)=2/2+F(1)=1+0=1.$
Последовательно вычислим значения:
$A_2=2\cdot1+2+2=6.$
$A_3=2\cdot6+3+2=17.$
$A_4=2\cdot17+4+2=40.$
$A_5=2\cdot40+5+2=87.$
$A_6=2\cdot87+6+2=182.$
$A_7=2\cdot182+7+2=373.$
$A_8=2\cdot373+8+2=756.$
$A_9=2\cdot756+9+2=1523.$
$A_{10}=2\cdot1523+10+2=3058.$
$A_{11}=2\cdot3058+11+2=6129.$
$A_{12}=2\cdot6129+12+2=12272.$
$A_{13}=2\cdot12272+13+2=24559.$
$A_{14}=2\cdot24559+14+2=49134.$
$A_{15}=2\cdot49134+15+2=98285.$
Так как $A_{15}=F(30)$, получаем:
$F(30)=98285.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n=1$;
$F(n)=2n\cdot F(n-1)$, если $n>1$.
Чему равно значение выражения $\dfrac{F(2024)-3\cdot F(2023)}{F(2022)}$?
По рекуррентной формуле:
$F(2024)=2\cdot2024\cdot F(2023)=4048\cdot F(2023).$
Тогда:
$F(2024)-3\cdot F(2023)=4048\cdot F(2023)-3\cdot F(2023)=4045\cdot F(2023).$
Также:
$F(2023)=2\cdot2023\cdot F(2022)=4046\cdot F(2022).$
Подставим это значение:
$\dfrac{F(2024)-3\cdot F(2023)}{F(2022)}=\dfrac{4045\cdot4046\cdot F(2022)}{F(2022)}=4045\cdot4046.$
Вычислим: $4045\cdot4046=16366070.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n<3$;
$F(n)=F(n-1)+n-1$, если $n>2$ и при этом $n$ чётно;
$F(n)=F(n-2)+2\cdot n-2$, если $n>2$ и при этом $n$ нечётно.
Чему равно значение функции $F(33)$?
Для вычисления $F(33)$ используется формула для нечётных значений аргумента:
$F(n)=F(n-2)+2\cdot n-2.$
Последовательно нечётные аргументы принимают значения $3,5,7,\ldots,33$.
При переходе к очередному нечётному аргументу прибавляется:
$2\cdot n-2.$
Для $n=2k+1$ получаем:
$2\cdot(2k+1)-2=4k.$
Числу $33$ соответствует значение: $33=2\cdot16+1.$
Следовательно: $F(33)=F(1)+4\cdot(1+2+\ldots+16).$
Так как:
$F(1)=1,$
$1+2+\ldots+16=\dfrac{16\cdot17}{2}=136,$
получаем: $F(33)=1+4\cdot136=1+544=545.$
20
Алгоритм вычисления функции $F(n)$, где $n$ — целое число, задан следующими соотношениями:
$F(n)=n$, если $n<10$;
$F(n)=n-1+F(n-1)$, если $n\geqslant10$.
Чему равно значение выражения $F(8567)-F(8563)$?
Выразим значение $F(8567)$ через $F(8563)$:
$F(8567)=8566+F(8566).$
$F(8566)=8565+F(8565).$
$F(8565)=8564+F(8564).$
$F(8564)=8563+F(8563).$
Следовательно: $F(8567)=8566+8565+8564+8563+F(8563).$
Тогда: $F(8567)-F(8563)=8566+8565+8564+8563=34258.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n=1$;
$F(n)=2n\cdot F(n-1)$, если $n>1$.
Чему равно значение выражения $\dfrac{F(2024)+2\cdot F(2023)}{F(2022)}$?
По рекуррентной формуле:
$F(2024)=2\cdot2024\cdot F(2023)=4048\cdot F(2023).$
Тогда:
$F(2024)+2\cdot F(2023)=4048\cdot F(2023)+2\cdot F(2023)=4050\cdot F(2023).$
Также: $F(2023)=2\cdot2023\cdot F(2022)=4046\cdot F(2022).$
Подставим это значение:
$\dfrac{F(2024)+2\cdot F(2023)}{F(2022)}=\dfrac{4050\cdot4046\cdot F(2022)}{F(2022)}=4050\cdot4046.$
Вычислим: $4050\cdot4046=16386300.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n=1$;
$F(n)=(n-1)\cdot F(n-1)$, если $n>1$.
Чему равно значение выражения $\dfrac{F(2024)+2\cdot F(2023)}{F(2022)}$?
По рекуррентной формуле:
$F(2024)=2023\cdot F(2023).$
Тогда:
$F(2024)+2\cdot F(2023)=2023\cdot F(2023)+2\cdot F(2023)=2025\cdot F(2023).$
Также: $F(2023)=2022\cdot F(2022).$
Подставим это значение:
$\dfrac{F(2024)+2\cdot F(2023)}{F(2022)}=\dfrac{2025\cdot2022\cdot F(2022)}{F(2022)}=2025\cdot2022.$
Вычислим: $2025\cdot2022=4094550.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=2\cdot n+F(n-1)$, если $n>1$ и при этом $n$ нечётно;
$F(n)=2\cdot F(n-1)$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(22)$?
Рассмотрим два последовательных аргумента $2k-1$ и $2k$, где $k\geqslant2$.
Для нечётного аргумента:
$F(2k-1)=2\cdot(2k-1)+F(2k-2)=4k-2+F(2k-2).$
Для следующего чётного аргумента:
$F(2k)=2\cdot F(2k-1)=2\cdot F(2k-2)+8k-4.$
Начальное значение:
$F(2)=2\cdot F(1)=2\cdot0=0.$
Последовательно вычислим значения функции для чётных аргументов:
$F(4)=2\cdot F(2)+12=2\cdot0+12=12.$
$F(6)=2\cdot F(4)+20=2\cdot12+20=44.$
$F(8)=2\cdot F(6)+28=2\cdot44+28=116.$
$F(10)=2\cdot F(8)+36=2\cdot116+36=268.$
$F(12)=2\cdot F(10)+44=2\cdot268+44=580.$
$F(14)=2\cdot F(12)+52=2\cdot580+52=1212.$
$F(16)=2\cdot F(14)+60=2\cdot1212+60=2484.$
$F(18)=2\cdot F(16)+68=2\cdot2484+68=5036.$
$F(20)=2\cdot F(18)+76=2\cdot5036+76=10148.$
$F(22)=2\cdot F(20)+84=2\cdot10148+84=20380.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=2\cdot F(n-1)+2$, если $n>1$ и при этом $n$ нечётно;
$F(n)=n/2+F(n-1)$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(26)$?
Примечание. При вычислении значения $F(n)$ используется операция целочисленного деления.
Обозначим через $A_k$ значение функции для чётного аргумента:
$A_k=F(2k).$
Для нечётного аргумента $2k-1$:
$F(2k-1)=2\cdot F(2k-2)+2=2\cdot A_{k-1}+2.$
Для следующего чётного аргумента:
$A_k=F(2k)=k+F(2k-1)=2\cdot A_{k-1}+k+2.$
Начальное значение:
$A_1=F(2)=2/2+F(1)=1+0=1.$
Последовательно вычислим значения:
$A_2=2\cdot1+2+2=6.$
$A_3=2\cdot6+3+2=17.$
$A_4=2\cdot17+4+2=40.$
$A_5=2\cdot40+5+2=87.$
$A_6=2\cdot87+6+2=182.$
$A_7=2\cdot182+7+2=373.$
$A_8=2\cdot373+8+2=756.$
$A_9=2\cdot756+9+2=1523.$
$A_{10}=2\cdot1523+10+2=3058.$
$A_{11}=2\cdot3058+11+2=6129.$
$A_{12}=2\cdot6129+12+2=12272.$
$A_{13}=2\cdot12272+13+2=24559.$
Так как $A_{13}=F(26)$, получаем: $F(26)=24559.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n=1$;
$F(n)=n+F(n-1)$, если $n$ чётно;
$F(n)=2\cdot F(n-2)$, если $n>1$ и при этом $n$ нечётно.
Чему равно значение функции $F(24)$?
Сначала найдём значение $F(23)$.
Для нечётных аргументов значение функции удваивается:
$F(3)=2\cdot F(1)=2.$
$F(5)=2\cdot F(3)=4.$
Следовательно, для нечётного числа $n=2k+1$ выполняется:
$F(2k+1)=2^k.$
Число $23$ представим в виде: $23=2\cdot11+1.$
Поэтому: $F(23)=2^{11}=2048.$
Так как $24$ — чётное число:
$F(24)=24+F(23)=24+2048=2072.$
20
Алгоритм вычисления функции $F(n)$, где $n$ — целое число, задан следующими соотношениями:
$F(n)=n$, если $n<10$;
$F(n)=(n-2)\cdot F(n-5)$, если $n\geqslant10$.
Чему равно значение выражения $\dfrac{F(3220)-2\cdot F(3215)}{F(3210)}$?
В ответе запишите целую часть полученного числа.
По рекуррентной формуле:
$F(3220)=(3220-2)\cdot F(3215)=3218\cdot F(3215).$
Тогда:
$F(3220)-2\cdot F(3215)=3218\cdot F(3215)-2\cdot F(3215)=3216\cdot F(3215).$
Также:
$F(3215)=(3215-2)\cdot F(3210)=3213\cdot F(3210).$
Подставим это значение:
$\dfrac{F(3220)-2\cdot F(3215)}{F(3210)}=\dfrac{3216\cdot3213\cdot F(3210)}{F(3210)}=3216\cdot3213.$
Вычислим: $3216\cdot3213=10333008.$
Полученное число целое, поэтому его целая часть равна $10333008$.
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=2\cdot F(n-1)+2$, если $n>1$ и при этом $n$ нечётно;
$F(n)=n/2+F(n-1)$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(28)$?
Примечание. При вычислении значения $F(n)$ используется операция целочисленного деления.
Обозначим через $A_k$ значение функции для чётного аргумента:
$A_k=F(2k).$
Для нечётного аргумента $2k-1$:
$F(2k-1)=2\cdot F(2k-2)+2=2\cdot A_{k-1}+2.$
Для следующего чётного аргумента:
$A_k=F(2k)=k+F(2k-1)=2\cdot A_{k-1}+k+2.$
Начальное значение:
$A_1=F(2)=2/2+F(1)=1+0=1.$
Последовательно вычислим значения:
$A_2=2\cdot1+2+2=6.$
$A_3=2\cdot6+3+2=17.$
$A_4=2\cdot17+4+2=40.$
$A_5=2\cdot40+5+2=87.$
$A_6=2\cdot87+6+2=182.$
$A_7=2\cdot182+7+2=373.$
$A_8=2\cdot373+8+2=756.$
$A_9=2\cdot756+9+2=1523.$
$A_{10}=2\cdot1523+10+2=3058.$
$A_{11}=2\cdot3058+11+2=6129.$
$A_{12}=2\cdot6129+12+2=12272.$
$A_{13}=2\cdot12272+13+2=24559.$
$A_{14}=2\cdot24559+14+2=49134.$
Так как $A_{14}=F(28)$, получаем: $F(28)=49134.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=2\cdot n+F(n-1)$, если $n>1$ и при этом $n$ нечётно;
$F(n)=2\cdot F(n-1)$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(24)$?
Обозначим значение функции для чётного аргумента:
$A_k=F(2k).$
Для нечётного аргумента $2k-1$ получаем:
$F(2k-1)=2\cdot(2k-1)+F(2k-2)=4k-2+A_{k-1}.$
Для следующего чётного аргумента:
$A_k=F(2k)=2\cdot F(2k-1)=2\cdot A_{k-1}+8k-4.$
Начальное значение:
$A_1=F(2)=2\cdot F(1)=0.$
Последовательно вычислим значения:
$A_2=2\cdot0+8\cdot2-4=12.$
$A_3=2\cdot12+8\cdot3-4=44.$
$A_4=2\cdot44+8\cdot4-4=116.$
$A_5=2\cdot116+8\cdot5-4=268.$
$A_6=2\cdot268+8\cdot6-4=580.$
$A_7=2\cdot580+8\cdot7-4=1212.$
$A_8=2\cdot1212+8\cdot8-4=2484.$
$A_9=2\cdot2484+8\cdot9-4=5036.$
$A_{10}=2\cdot5036+8\cdot10-4=10148.$
$A_{11}=2\cdot10148+8\cdot11-4=20380.$
$A_{12}=2\cdot20380+8\cdot12-4=40852.$
Так как $A_{12}=F(24)$, получаем: $F(24)=40852.$
20
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n=1$;
$F(n)=n\cdot F(n-1)$, если $n>1$.
Чему равно значение выражения $\dfrac{F(2024)-F(2023)}{F(2022)}$?
По рекуррентной формуле:
$F(2024)=2024\cdot F(2023).$
Тогда:
$F(2024)-F(2023)=2024\cdot F(2023)-F(2023)=2023\cdot F(2023).$
Также:
$F(2023)=2023\cdot F(2022).$
Подставим это значение:
$\dfrac{F(2024)-F(2023)}{F(2022)}=\dfrac{2023\cdot2023\cdot F(2022)}{F(2022)}=2023^2.$
Вычислим: $2023^2=4092529.$
20