Его. Выполнение алгоритмов для исполнителя
 Скачать 1.75 Mb.
|
Ещё пример задания:Р-12. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w) Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. нашлось (v) Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (21) заменить (21, 5) КОНЕЦ ПОКА КОНЕЦ Исходная строка содержит десять единиц и некоторое количество двоек, других цифр нет, точный порядок расположения единиц и двоек неизвестен. После выполнения программы получилась строка с суммой цифр 34. Какое наименьшее количество двоек могло быть в исходной строке? Решение: сначала представим себе, что двоек в строке не было вообще: в этом случае сумма цифр была бы равна 10, что не подходит по условию; если к этим 10 единицам добавить 2 и сделать замену «21» на 5, то сумма станет равной (10-1+5) = 14, то есть каждое добавление двойки с заменой увеличит сумму на 4 нам нужно добавить 34 – 10 = 24, то есть в цепочке должно быть 6 двоек, каждая из которых стоит перед единицей; в результате работы программы все 6 пар «21» должны быть заменены на 5. Ответ: 6. Ещё пример задания:Р-11. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w) Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. нашлось (v) Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (111) заменить (111, 2) заменить (22, 1) КОНЕЦ ПОКА КОНЕЦ Какая строка получится в результате применения приведённой выше программы к строке вида 1…12…2, состоящей из 44 единиц и 21 двойки? В ответе запишите полученную строку. Решение (А.М. Кабанов, г. Тольятти): рассмотрим, что происходит со строкой во время алгоритма на меньшем примере (8 единиц и 8 двоек): 1111111122222222 → 21111122222222 → 2111111222222 2111111222222 → 22111222222 → 1111222222 в результате этих шагов мы получили строку, похожую на изначальную, но единиц стало на 4 меньше, а двоек стало на 2 меньше; можно сказать, что дальнейшие повторы будут дальше уменьшать число единиц на 4, а двоек на 2 перенесём это на нашу строку, запишем изменение числа единиц как 44-4n, а числа двоек как 21-2n, где n – некоторое число повторов действий выше. Если возьмём n = 10, то получим 4 единицы и 1 двойку: 11112 → 212 Ответ: 212 Ещё пример задания:Р-10. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w) Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. нашлось (v) Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (222) ИЛИ нашлось (555) ЕСЛИ нашлось (222) ТО заменить (222, 5) ИНАЧЕ заменить (555, 2) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Какая строка получится в результате применения приведённой выше программы к строке, состоящей из А) 247 идущих подряд цифр 5? Б) 247 идущих подряд цифр 2? В ответе запишите полученную строку. Решение (В.Ю. Беспалова, г. Каменск-Уральский): Рассмотрим алгоритм решения для пункта А. Дана последовательность из 247 пятерок. Вначале, так как трёх «2» в последовательности нет, согласно алгоритму, первые три «5» заменяются одной «2». Получается одна «2» и двести сорок четыре «5». Так как еще не набирается трёх «2», происходит следующая замена трёх «5» на «2». И имеется теперь две «2» и двести сорок одна «5». Трёх «2» по-прежнему нет, поэтом опять три следующие «5» заменяются на «2», и теперь имеем три «2» и двести тридцать восемь «5». Так как появились три «2», они заменяются на одну «5». Далее операции повторяются. Таким образом, девять «5» заменяются на одну «5», то есть можем сказать, что при каждом повторении описанных выше действий вычеркиваются по восемь «5». Поэтому найдем, сколько «5» остались невычеркнутыми. Для этого вычислим целочисленный остаток от деления 247 (количество «5» по условиям вначале) на 8. Это 7. То есть остаются семь «5»: 5555555. Теперь заменим первые три «5» двойкой, получится 25555. Далее снова заменим три «5» на «2», и в итоге ответ: 225. Как же поступить, если остаток от деления равен 0? Например, будут даны вначале двадцать четыре «5». Тогда выполним шаг назад, когда оставались последние восемь «5» и преобразуем последовательность. Имеем: 55555555, далее 255555, затем 2255. Теперь рассмотрим решение для пункта Б. Дана последовательность из 247 двоек. Первые три «2» заменяются «5», далее следующие три «2» заменяются на «5», и следующие три «2» заменяются «5». Несмотря на то, что набирается три «5», не происходит замена трех «5» на «2», так как ветвь «Иначе» выполняется только в том случае, если не отработала ветвь «То». А так как далее идет последовательность «2», в которой количество «2» больше, чем две, происходит замена следующих идущих подряд трех «2» на «5», и так далее. Подсчитаем, сколько раз три «2» заменятся на «5». Вычислим целую часть от деления 247 на 3. Это 82. То есть в последовательности станет восемьдесят две «5» и оставшаяся одна «2» (целочисленный остаток от деления 247 на 3). Теперь к последовательности «5» применим алгоритм, описанный в пункте А. Найдем целочисленный остаток от деления 82 на 8. Это будет 2, то есть останется две «5» и плюс еще одна «2», полученная ранее. Имеем последовательность «552». Ответ: А) 225. Б) 552. |