На вход программе поступает строка из 120 цифр, содержащая по 40 цифр 4, 7 и 9, расположенных в произвольном порядке. Программа последовательно заменяет первое слева вхождение цепочек $47$, $49$ и…
- 1
Каждая команда замены изменяет только порядок двух соседних цифр, поэтому длина строки и количества цифр 4, 7 и 9 сохраняются.
- 2
Цикл выполняется до тех пор, пока в строке есть хотя бы одна из пар $47$, $49$ или $97$. При каждом проходе первое слева вхождение каждой найденной пары заменяется на $74$, $94$ или $79$ соответственно.
Ещё 2 қадам — толық шешімде
142ФИПИ D50F56№ 12Күрделі Исполнитель Редактор получает на вход строку, начинающуюся с символа «>», а затем содержащую 15 цифр 1, 20 цифр 2 и 16 цифр 3, расположенных в произвольном порядке. Редактор выполняет программу…
- 1
Символ «>» перемещается вправо по строке. При обработке цифры 1 команда заменяет цепочку $>1$ на $22>$, поэтому каждая исходная цифра 1 даёт две цифры 2 и увеличивает сумму на 4.$$15 \cdot (2 + 2) = 60$$
- 2
При обработке цифры 2 цепочка $>2$ заменяется на $2>$, поэтому цифра 2 сохраняется и даёт вклад 2.$$20 \cdot 2 = 40$$
Ещё 2 қадам — толық шешімде
143ФИПИ D6986C№ 12Күрделі Исполнитель Редактор получает на вход строку цифр и преобразует её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет наличие цепочки…
- 1
В начале в строке нет цепочки 999, поэтому программа заменяет первое вхождение 333 на 9. Из 92 цифр 3 образуются 30 цифр 9 и 2 цифры 3.$$92 = 30 \cdot 3 + 2$$
- 2
Пока в строке есть 999, программа заменяет первое такое вхождение на 3. Десять таких замен уничтожают 30 цифр 9 и добавляют 10 цифр 3 к двум оставшимся, поэтому получается 12 цифр 3.$$30 \to 0,\quad 2+10=12$$
Ещё 2 қадам — толық шешімде
144ФИПИ D6A924№ 12Күрделі Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке…
- 1
На первом этапе программа заменяет вхождения 1111 на 888. Из 81 единицы можно выполнить 20 таких замен, поскольку 81 = 4 · 20 + 1.$$1^{81} \rightarrow 888^{20}1$$
- 2
После этого цепочки 1111 нет, но имеется цепочка из 60 восьмёрок. Каждая замена 88888 на 888 уменьшает её длину на 2.
Ещё 2 қадам — толық шешімде
Исполнитель Редактор получает на вход строку, начинающуюся с цифры «5», а затем содержащую $n$ цифр «2», где $3 < n < 10000$. Программа последовательно заменяет первое вхождение $72$ на $2$, первое…
- 1
Пусть текущая строка имеет вид $5 2^m$. Если $m \geq 2$, замена $522$ на $27$ даёт строку $27 2^{m-2}$.$$5 2^m \to 27 2^{m-2}$$
- 2
Затем первое вхождение $72$ заменяется на $2$, поэтому получается жол из $m-1$ цифр «2».$$27 2^{m-2} \to 2^{m-1}$$
Ещё 2 қадам — толық шешімде
146ФИПИ DCB943№ 12Күрделі Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке…
- 1
Пока в строке нет пяти цифр 2 подряд, выполняется замена первого фрагмента $9999$ на $2$. Для достаточно длинной последовательности из девяток пять таких замен дают $22222$.$$9999 \to 2$$
- 2
Когда появляется фрагмент $22222$, он заменяется на $99$. Поэтому после полного цикла количество девяток уменьшается на 18: четыре заменённых блока содержат 20 девяток, а результат добавляет 2 девятки.$$n \to n - 20 + 2 = n - 18$$
Ещё 2 қадам — толық шешімде
147ФИПИ E50259№ 12Күрделі Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет…
- 1
Изначально строка содержит 84 цифры 8. Пока в ней нет цепочки $1111$, программа заменяет первое слева вхождение $8888$ на $11$.
- 2
Когда в строке появляется цепочка $1111$, условие первой ветви становится истинным, и первое вхождение $1111$ заменяется на одну цифру $8$. Далее снова выполняется поиск $1111$, а при его отсутствии — замена $8888$ на $11$.
Ещё 2 қадам — толық шешімде
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки цифр $v$ на цепочку $w$. Если в строке нет…
- 1
Для каждого значения $n$ моделируем работу цикла: сначала заменяем найденную цепочку $73$, затем $322$, затем $2222$. После каждой итерации проверяем условие продолжения цикла.
- 2
Для значений $n$, меньших 12, сумма цифр итоговой строки не равна 15.
Ещё 2 қадам — толық шешімде
149ФИПИ FA2969№ 12Күрделі Исполнитель Редактор получает на вход строку цифр и может выполнять команды $\text{заменить}(v, w)$ и $\text{нашлось}(v)$. Команда $\text{заменить}(v, w)$ заменяет первое слева вхождение цепочки $v$…
- 1
Из исходной последовательности цифр 9 первые три замены $999$ на $2$ дают цепочку $222$. Она заменяется на $19$, после чего строка имеет вид $1\cdot 9^{49}$.$$9^{57}\to 222\cdot 9^{48}\to 19\cdot 9^{48}=1\cdot 9^{49}$$
- 2
Затем для образования очередной цепочки $222$ требуется заменить три цепочки $999$ на $2$. После замены $222$ на $19$ количество цифр 9 уменьшается на 8, а количество цифр 1 увеличивается на 1.$$49\to41\to33\to25\to17\to9\to1$$
Ещё 2 қадам — толық шешімде
150ФИПИ 0C9871№ 16Күрделі Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n=1$; $F(n)=nF(n-1)$, если $n>1$. Чему равно значение выражения…
- 1
Из рекуррентного соотношения следует, что $F(n)=n!$.$$F(2024)=2024\cdot2023\cdot F(2022),\quad F(2023)=2023\cdot F(2022)$$
- 2
Подставим эти выражения в исходную формулу и сократим на $F(2022)$:$$\frac{F(2024)/4+F(2023)}{F(2022)}=\frac{2024\cdot2023\cdot F(2022)/4+2023\cdot F(2022)}{F(2022)}=2023\left(\frac{2024}{4}+1\right)$$
Ещё 1 қадам — толық шешімде
151ФИПИ 0D4EB5№ 16Күрделі Ниже приведены две рекурсивные функции F и G. Функция G печатает символ «звёздочка» и при выполнении условия вызывает функцию F. Сколько символов «звёздочка» будет напечатано на экране при…
- 1
Вызов F(14) удовлетворяет условию $n > 0$, поэтому выполняется вызов G(11).$$F(14) \to G(11)$$
- 2
Функция G(11) печатает одну «звёздочку» и вызывает F(10), так как $11 > 1$.$$G(11) \to F(10)$$
Ещё 2 қадам — толық шешімде
152ФИПИ 28131C№ 16Күрделі Ниже на пяти языках программирования записан рекурсивный алгоритм $F$. Во всех вариантах алгоритм выводит значение параметра $n$, а затем, если $n \ge 4$, вызывает функцию для $n - 1$ и для целой…
- 1
При каждом входе в функцию сначала выводится её параметр $n$.$$F(6) \Rightarrow 6$$
- 2
Для значений $n \ge 4$ сначала выполняется вызов с параметром $n-1$, затем — с параметром $n \mathbin{//} 2$.$$6 \to 5 \to 4 \to 3 \to 2 \to 2 \to 3$$
Ещё 1 қадам — толық шешімде
153ФИПИ 39F802№ 16Күрделі Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n=1$; $F(n)=2nF(n-1)$, если $n>1$. Чему равно значение выражения…
- 1
Запишем значения функции, используя рекуррентную формулу.$$F(2024)=2\cdot2024\cdot F(2023)=4048F(2023),\quad F(2023)=2\cdot2023\cdot F(2022)=4046F(2022)$$
- 2
Подставим выражение для $F(2024)$ в числитель.$$F(2024)-F(2023)=(4048-1)F(2023)=4047F(2023)$$
Ещё 2 қадам — толық шешімде
154ФИПИ 45D78C№ 16Күрделі Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=n$ при $n\geq 2025$; $F(n)=n+3+F(n+3)$, если $n<2025$. Чему равно значение выражения…
- 1
Вычислим значение функции $F(2022)$. После одного шага аргумент становится равным $2025$, поэтому используется базовое значение.$$F(2022)=2022+3+F(2025)=2022+3+2025=4050$$
- 2
Раскроем рекурсию для $F(2018)$ до достижения аргумента $2027\geq 2025$.$$F(2018)=2018+3+F(2021)=2018+3+2021+3+F(2024)$$
Ещё 2 қадам — толық шешімде
155ФИПИ 4ABC65№ 16Күрделі Ниже на пяти языках программирования записан один и тот же рекурсивный алгоритм $F$. Запишите подряд без пробелов и разделителей все числа, которые будут выведены на экран при выполнении вызова…
- 1
Для $n \leq 0$ функция завершается без вывода. Вызов $F(1)$ сначала обращается к $F(-2)$, затем выводит 1 и вызывает $F(0)$, поэтому результатом является 1.$$F(1) \to 1$$
- 2
Вызов $F(2)$ сначала обращается к $F(-1)$, выводит 2, затем вызывает $F(1)$.$$F(2) \to 21$$
Ещё 3 қадам — толық шешімде
156ФИПИ 5F1A93№ 16Күрделі Алгоритм вычисления функции $F(n)$, где $n$ — целое число, задан следующими соотношениями: $F(n)=n$, если $n<10$; $F(n)=(n-2)\times F(n-5)$, если $n\geq 10$. Чему равно значение выражения…
- 1
Применим рекуррентное соотношение к функции $F(3220)$:$$F(3220)=3218\cdot F(3215)$$
- 2
Подставим это выражение в числитель:$$F(3220)-2F(3215)=(3218-2)F(3215)=3216F(3215)$$
Ещё 2 қадам — толық шешімде
157ФИПИ 63eB9e№ 16Күрделі Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n=1$; $F(n)=n\times F(n-1)$, если $n>1$. Чему равно значение выражения…
- 1
По рекуррентному соотношению функция вычисляет факториал: $F(n)=n!$.
- 2
Выразим числители через $F(3236)$:$$F(3238)=3238\cdot3237\cdot F(3236),\quad F(3237)=3237\cdot F(3236)$$
Ещё 1 қадам — толық шешімде
158ФИПИ 67F7F0№ 16Күрделі Алгоритм вычисления функции $F(n)$, где $n$ — целое число, задан следующими соотношениями: $F(n)=1$, если $n<10$; $F(n)=(n+3)\times F(n-3)$, если $n\ge 10$. Чему равно значение выражения…
- 1
Последовательно применяем рекуррентное соотношение к двум значениям функции:$$F(247\,560)=247\,563\cdot F(247\,557)$$
- 2
Ещё один шаг рекурсии даёт:$$F(247\,563)=247\,566\cdot F(247\,560)=247\,566\cdot247\,563\cdot F(247\,557)$$
Ещё 2 қадам — толық шешімде
159ФИПИ 8C5262№ 16Күрделі Ниже на пяти языках программирования записан рекурсивный алгоритм $F$: если $n > 2$, то последовательно выполняются вызовы $F(n - 1)$ и $F(n \mathbin{//} 2)$, после чего выводится значение $n$…
- 1
Вызов $F(7)$ сначала запускает $F(6)$, затем $F(3)$, а число $7$ выводится последним.$$F(7) \to F(6),\ F(3),\ 7$$
- 2
Разбираем вызов $F(6)$: сначала выполняется $F(5)$, затем $F(3)$, после чего выводится $6$.$$F(6) \to F(5),\ F(3),\ 6$$
Ещё 3 қадам — толық шешімде
160ФИПИ 914B18№ 16Күрделі Ниже на пяти языках программирования записан рекурсивный алгоритм F. Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(4). Числа…
- 1
При вызове с положительным n функция сначала печатает n, затем выполняет вызовы F(n - 1) и F(n - 2). При n ≤ 0 функция ничего не печатает.$$F(n) = n, F(n-1), F(n-2)$$
- 2
Вызов F(1) печатает 1, поскольку последующие вызовы F(0) и F(-1) ничего не выводят.$$F(1) \to 1$$
Ещё 3 қадам — толық шешімде