A9E896 — Выполнение и анализ программы: ответ и решение

Впишите правильный ответ.

Цепочки символов (строки) создаются по следующему правилу.

Первая строка состоит из одного символа – цифры «1».

Каждая из последующих цепочек создается такими действиями: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»).

Вот первые 4 строки, созданные по этому правилу:

(1) 1

(2) 112

(3) 1121123

(4) 112112311211234

Какая цифра стоит в седьмой строке на 120-м месте (считая слева направо)?

СВОЙСТВА ЗАДАНИЯ

КЭС:

3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность

3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат

3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена»

3.5 Многоразрядные целые числа, задачи длинной арифметики

Тип ответа:

Краткий ответ

Номер: A9E896

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINFA9E896

Ответ: 1

Обозначим строку после шага n через Sₙ. Правило построения: S₁ = «1»; следующая строка содержит две полные копии предыдущей и в конце цифру n. Здесь все номера шагов однозначные.
Поэтому длина удовлетворяет L₁ = 1 и Lₙ = 2Lₙ₋₁ + 1. Отсюда Lₙ = 2ⁿ − 1; обе старые копии имеют одинаковую длину.
В седьмой строке 127 символов, так что позиция 120 существует. Позиции с 1 до Lₙ₋₁ относятся к первой копии, следующие Lₙ₋₁ — ко второй, последняя позиция 2Lₙ₋₁ + 1 содержит n.
Строка 7, позиция 120: длина предыдущей 63. Во второй копии та же цифра находится на позиции 120 − 63 = 57.
Строка 6, позиция 57: длина предыдущей 31. Во второй копии та же цифра находится на позиции 57 − 31 = 26.
Строка 5, позиция 26: длина предыдущей 15. Во второй копии та же цифра находится на позиции 26 − 15 = 11.
Строка 4, позиция 11: длина предыдущей 7. Во второй копии та же цифра находится на позиции 11 − 7 = 4.
Строка 3, позиция 4: длина предыдущей 3. Во второй копии та же цифра находится на позиции 4 − 3 = 1.
Строка 2, позиция 1: длина предыдущей 1. Позиция в первой копии, её номер остаётся 1.
Дошли до первой строки, её единственный символ — 1.
Проверка обратного пути: позиция 1 последовательно переходит в позиции 1, 4, 11, 26, 57, 120 соответствующих строк. В каждом переходе сохраняется копируемый символ.
Ответ: 1.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFA9E896.

Сообщение увидит только команда сайта: на странице оно не публикуется.

Задание EGEINFA9E896: Выполнение и анализ программы

Решение задания EGEINFA9E896

Помочь улучшить сайт

Комментарии к решению