ЕГЭ и ОГЭФИПИ · понять и решить
Начать подготовку
Меню

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

ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий

Открыть решение ↓ Ошибка или пожелание

Тип задачи: Выполнение и анализ программы.

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

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

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

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

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

(1)     1

(2)     112

(3)     1121123

(4)     112112311211234

…

Сколько раз в общей сложности встречаются в восьмой строке нечетные цифры (1, 3, 5, 7, 9)?



i
СВОЙСТВА ЗАДАНИЯ
КЭС:
3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность
3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат
3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена»
3.5 Многоразрядные целые числа, задачи длинной арифметики
Тип ответа:Краткий ответ
Номер: 93CFDF
НЕ РЕШЕНО Ответить

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

Ответ: 170

Обозначим строку после шага n через Sₙ. Правило построения: S₁ = «1»; следующая строка содержит две полные копии предыдущей и в конце цифру n. Здесь все номера шагов однозначные.
Поэтому длина удовлетворяет L₁ = 1 и Lₙ = 2Lₙ₋₁ + 1. Отсюда Lₙ = 2ⁿ − 1; обе старые копии имеют одинаковую длину.
Пусть Cₙ — число нечётных цифр. Две копии удваивают предыдущий счётчик; в конце добавляется ещё 1, если номер n имеет нужную чётность. Иначе добавляется 0.
Шаг 1: C = 1.
Шаг 2: C = 2.
Шаг 3: C = 5.
Шаг 4: C = 10.
Шаг 5: C = 21.
Шаг 6: C = 42.
Шаг 7: C = 85.
Шаг 8: C = 170.
Следовательно, в строке 8 нужных цифр 170.
Проверка другим подсчётом: цифра d появляется один раз на своём шаге и затем удваивается на каждом оставшемся шаге. В строке n она встречается 2ⁿ⁻ᵈ раз. Для нужной чётности получаем 128 + 32 + 8 + 2 = 170.
Ответ: 170.

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

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

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

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

Комментарии видны всем посетителям сайта.

Комментариев пока нет. Будьте первым.

Чтобы оставить комментарий, войдите или зарегистрируйтесь.