Файл: Выполнение алгоритмов для исполнителя.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 04.12.2023

Просмотров: 2362

Скачиваний: 17

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Ещё пример задания:


Р-12. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.

нашлось (v)

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (21)

заменить (21, 5)

КОНЕЦ ПОКА

КОНЕЦ

Исходная строка содержит десять единиц и некоторое количество двоек, других цифр нет, точный порядок расположения единиц и двоек неизвестен. После выполнения программы получилась строка с суммой цифр 34. Какое наименьшее количество двоек могло быть в исходной строке?

Решение:

  1. сначала представим себе, что двоек в строке не было вообще: в этом случае сумма цифр была бы равна 10, что не подходит по условию;

  2. если к этим 10 единицам добавить 2 и сделать замену «21» на 5, то сумма станет равной (10-1+5) = 14, то есть каждое добавление двойки с заменой увеличит сумму на 4

  3. нам нужно добавить 34 – 10 = 24, то есть в цепочке должно быть 6 двоек, каждая из которых стоит перед единицей; в результате работы программы все 6 пар «21» должны быть заменены на 5.

  4. Ответ: 6.

Ещё пример задания:


Р-11. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.

нашлось (v)

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.


Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (111)

заменить (111, 2)

заменить (22, 1)

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке вида 1…12…2, состоящей из 44 единиц и 21 двойки? В ответе запишите полученную строку.

Решение (А.М. Кабанов, г. Тольятти):

  1. рассмотрим, что происходит со строкой во время алгоритма на меньшем примере (8 единиц и 8 двоек):

1111111122222222 → 21111122222222 → 2111111222222

2111111222222 → 22111222222 → 1111222222

  1. в результате этих шагов мы получили строку, похожую на изначальную, но единиц стало на 4 меньше, а двоек стало на 2 меньше;

  2. можно сказать, что дальнейшие повторы будут дальше уменьшать число единиц на 4, а двоек на 2

  3. перенесём это на нашу строку, запишем изменение числа единиц как 44-4n, а числа двоек как 21-2n, где n – некоторое число повторов действий выше. Если возьмём n = 10, то получим 4 единицы и 1 двойку: 11112 → 212

  4. Ответ: 212

Решение на PascalABC.NET (Л.А. Выходец):

  1. полная программа с использованием методов Contains и Replace:

begin

var s: string := '1' * 44+'2'*21;

while s.contains('111') do

begin

if s.contains('111') then

s := s.replace('111', '2', 1);

if s.contains('22') then

s := s.replace('22', '1', 1)

end;

writeln(s);

end.

  1. Ответ: 212

Ещё пример задания:


Р-10. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.

нашлось (v)

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (222) ИЛИ нашлось (555)

ЕСЛИ нашлось (222)

ТО заменить (222, 5)

ИНАЧЕ заменить (555, 2)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке, состоящей из

А) 247 идущих подряд цифр 5?

Б) 247 идущих подряд цифр 2?


В ответе запишите полученную строку.

Решение (В.Ю. Беспалова, г. Каменск-Уральский):

  1. Рассмотрим алгоритм решения для пункта А. Дана последовательность из 247 пятерок. Вначале, так как трёх «2» в последовательности нет, согласно алгоритму, первые три «5» заменяются одной «2». Получается одна «2» и двести сорок четыре «5».

  2. Так как еще не набирается трёх «2», происходит следующая замена трёх «5» на «2». И имеется теперь две «2» и двести сорок одна «5».

  3. Трёх «2» по-прежнему нет, поэтом опять три следующие «5» заменяются на «2», и теперь имеем три «2» и двести тридцать восемь «5». Так как появились три «2», они заменяются на одну «5».

  4. Далее операции повторяются. Таким образом, девять «5» заменяются на одну «5», то есть можем сказать, что при каждом повторении описанных выше действий вычеркиваются по восемь «5».

  5. Поэтому найдем, сколько «5» остались невычеркнутыми. Для этого вычислим целочисленный остаток от деления 247 (количество «5» по условиям вначале) на 8. Это 7. То есть остаются семь «5»: 5555555.

  6. Теперь заменим первые три «5» двойкой, получится 25555. Далее снова заменим три «5» на «2», и в итоге ответ: 225.

  7. Как же поступить, если остаток от деления равен 0? Например, будут даны вначале двадцать четыре «5». Тогда выполним шаг назад, когда оставались последние восемь «5» и преобразуем последовательность. Имеем: 55555555, далее 255555, затем 2255.

  8. Теперь рассмотрим решение для пункта Б. Дана последовательность из 247 двоек. Первые три «2» заменяются «5», далее следующие три «2» заменяются на «5», и следующие три «2» заменяются «5».

  9. Несмотря на то, что набирается три «5», не происходит замена трех «5» на «2», так как ветвь «Иначе» выполняется только в том случае, если не отработала ветвь «То». А так как далее идет последовательность «2», в которой количество «2» больше, чем две, происходит замена следующих идущих подряд трех «2» на «5», и так далее.

  10. Подсчитаем, сколько раз три «2» заменятся на «5». Вычислим целую часть от деления 247 на 3. Это 82. То есть в последовательности станет восемьдесят две «5» и оставшаяся одна «2» (целочисленный остаток от деления 247 на 3).

  11. Теперь к последовательности «5» применим алгоритм, описанный в пункте А. Найдем целочисленный остаток от деления 82 на 8. Это будет 2, то есть останется две «5» и плюс еще одна «2», полученная ранее. Имеем последовательность «552».

  12. Ответ: А) 225. Б) 552.

Ещё пример задания:


Р-09. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w)

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.

Б) нашлось (v)

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (222) ИЛИ нашлось (888)

ЕСЛИ нашлось (222)

ТО заменить (222, 8)

ИНАЧЕ заменить (888, 2)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 68 идущих подряд цифр 8? В ответе запишите полученную строку.

Решение:

  1. из программы видим, что Редактор что-то делает только тогда, когда в строке есть цепочка 222 или цепочка 888; то есть, если ни одной из этих цепочек нет, программа останавливается

  2. если в строке есть 222, то, в первую очередь, именно эта цепочка меняется (на 8)

  3. если в строке нет цепочки 222, но есть 888, то цепочка 888 меняется на 2

  4. попробуем формально выполнить первые шаги алгоритма для цепочки цифр 8

  5. сначала первые 888 меняются на 2, получается

2 [65 цифр 8]

  1. дальше так же меняем следующие две тройки из цифр 8:

222 [59 цифр 8]

  1. теперь (внимание!) у нас появилась цепочка 222, поэтому в соответствии с алгоритмом она сразу будет заменена на 8, получаем

[60 цифр 8]

  1. таким образом, за первые 4 шага работы цикла мы заменили 9 восьмерок на 1 или, что то же самое, удалили 8 восьмерок

  2. очевидно, что следующие 4 шага удалят ещё 8 восьмерок и т.д.

  3. сколько раз мы сможем это сделать? видимо, 8 раз, после этого останется 68 - 8·8 = 4 восьмерки

  4. итак, в цепочке 8888 на последнем шаге заменяем 888 на 2 и получаем 28

  5. Ответ: 28.

Смотрите также файлы