Задание 12. Алгоритмы. Выполнение алгоритма. Исполнитель Редактор

Алгоритм — конечная совокупность точно заданных правил решения некоторого класса задач или набор инструкций (команд), описывающих порядок действий исполнителя.
Исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды.
Известны три типа алгоритмов – линейные, разветвляющиеся, циклические.

Алгоритмы, в которых команды выполняются друг за другом, независимо от каких-либо условий, называются алгоритмами линейного типа.

Алгоритмы, в которых требуется организовать выбор последовательности действий в зависимости от каких-либо условий, называют алгоритмами разветвляющегося типа.

При составлении алгоритмов нередко возникает потребность в неоднократном повторении одних и тех же действий (команд). Такие алгоритмы называются циклическими. Неоднократно – не значит бесконечное число раз. Организация циклов, никогда не приводящая к остановке в выполнении алгоритма (так называемое зацикливание), является нарушением требования его результативности. При разработке алгоритма циклической структуры выделяют следующие понятия: параметр цикла – величина, с изменением которой связано многократное выполнение цикла; начальное и конечное значение параметра цикла; шаг цикла – это значение, на которое изменяется параметр цикла при каждом повторении.

Циклический алгоритм состоит из подготовки цикла, тела цикла, условия продолжения цикла. В подготовку цикла входят действия, связанные с заданием исходных значений для параметра цикла (начальное и конечное значения, шаг параметра). В тело цикла входят: многократно повторяющиеся действия для вычисления искомых величин; подготовка следующего значения параметра цикла, подготовка других значений, необходимых для повторного выполнения действий в теле цикла. В условии продолжения определяется необходимость дальнейшего выполнения повторяющихся действий. Если параметр цикла превысил конечное значение, то выполнение цикла должно быть прекращено.
Циклы могут быть с предусловием (когда условие проверяется перед началом тела цикла) и спостусловием (когда условие проверяется после первого прохождения тела цикла).

Способы описания алгоритмов.

- Символьный, когда алгоритм описывается с помощью специального набора символов (специального языка).
- Словесная форма записи алгоритмов обычно используется для алгоритмов, ориентированных на исполнителя-человека. Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного.
- Графическая запись с помощью блок-схем: осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма.
Современные языки программирования могут обрабатывать различные типы данных: числовые, логические, строковые и т.д.

Исполнитель Редактор

Исполнитель Редактор получает на вход строку из цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
1) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (1111, 23)
преобразует строку 06111130 в строку 062330.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
2) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл
  ПОКА условие
      последовательность команд
  КОНЕЦ ПОКА
  выполняется, пока условие истинно.
  
В конструкции
  ЕСЛИ условие
      ТО команда1
      ИНАЧЕ команда2
  КОНЕЦ ЕСЛИ
  выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Типы задач для исполнителя Редактор:
1. нахождение итоговой строки после применения команд Исполнителя;
2. нахождение начальной строки по итоговой строке после применения команд Исполнителя;
3. анализ итоговой строки после применения команд Исполнителя (сумма цифр, количество, делимость, поиск простых чисел).

Способы решения таких задач:
- аналитический;
- алгебраический;
- с использованием языка программирования;
- с помощью электронных таблиц.

Примеры решения задач

Задача 1.Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 101 пятерок?
НАЧАЛО
    ПОКА нашлось (5555)
        заменить (5555, 22)
        заменить (222, 5)
    КОНЕЦ ПОКА
КОНЕЦ

Решение:
Аналитический способ
1) Чтобы понять принцип работы алгоритма, рассмотрим цепочку, состоящую из 12 пятерок – 555555555555.
2) После выполнения первой итерации получаем: 2255555555, была произведена только одна замена, для второй замены не хватает двоек.
3) После второй итерации получим:2255555555 ->22225555 -> 525555
4) После третьей итерации получаем: 525555 ->5222 -> 55. Таким образом, после выполнения трех итераций из двенадцати пятерок осталось только две.
5) 101:12=8, остаток 5.Таким образом, после применения этих трех итераций 8 раз к цепочке, состоящей из 101 пятерки, останется \(8\cdot 2 + 5 = 21\) пятерка.
6) Далее применяем алгоритм еще 5 раз, получаем:
555555555555555555555 –> … ->55555555555 -> 225555555 ->2222555 -> 52555
Ответ: 52555.

Задача 2. На вход приведённой ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 10 цифр 1, 20 цифр 2 и 30 цифр 3, расположенных в произвольном порядке.Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)
    ЕСЛИ нашлось (>1)
        ТО заменить (>1, 22>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>2)
        ТО заменить (>2, 2>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>3)
        ТО заменить (>3, 1>)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение:
Аналитический способ:
Все «>1» заменятся на « 22>» т.е. количество двоек будет равно количеству единиц умноженное на 2; все «>2» заменятся на «2>» т.е. здесь количество двоек не изменится; все «>3» заменятся на «1>» т.е. количество единиц будет равно количеству троек. Таким образом, итоговая строка будет содержать 30 единиц и 40 двоек. Сумма числовых значений цифр строки: \(30\cdot 1 + 40\cdot 2 = 110\).

Программный способ решения (Python):
1) В начале программы запишем исходную строку
s = ">" + 10*"1"+20*"2"+30*"3"
2) Далее перепишем программу на языке программирования. При этом три внутренних блока «ЕСЛИ» можно заменить просто командами «заменить», т.к. они не пересекаются друг с другом.

s = ">" + 10*"1"+20*"2"+30*"3"
while ">1" in s or ">2" in s or ">3" in s:
s = s.replace( ">1", "22>", 1 )
s = s.replace( ">2", "2>", 1 )
s = s.replace( ">3", ">", 1 )
r = s.count( "1")+s.count( "2")*2
print(s)

Примечание 1: функция s.replace( str1, str2, 1 ) заменяет в строке s подстроку str1 на строку str2 один раз. Если нужно заменить все вхождения подстроки str1, то третий аргумент не пишется.
Примечание 2: функция s.count( str1 ) подсчитывает количество вхождений подстроки str1 в строке s.
Ответ: 110.

Задача 3. Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 68 идущих подряд цифр 8? В ответе запишите полученную строку.
 НАЧАЛО
 ПОКА нашлось (222) ИЛИ нашлось (888)
    ЕСЛИ нашлось (222)
        ТО заменить (222, 8)
        ИНАЧЕ заменить (888, 2)
    КОНЕЦ ЕСЛИ
 КОНЕЦ ПОКА
 КОНЕЦ

Решение:
С использованием электронных таблиц:
1) В ячейку С1 нужно записать исходную строку любым образом. Для экономии времени можно воспользоваться функцией ПОВТОР

2) Далее нужно определить есть ли в данной строке подстроки “222”и “888”. Для этого можно использовать функцию НАЙТИ. Эта функция выдает ошибку, если подстрока не найдена.
3) Чтобы правильно обработать ошибку воспользуемся функцией ЕСЛИОШИБКА, которая в случае ошибки выдает 0, а при обнаружении подстроки его позицию. Для каждой подстроки воспользуемся отдельной ячейкой: например, в А2 - “222”, в В2 - “888”.

4) Теперь нужно построить строку, которая получится после первой итерации. Т.к. в исходной строке двоек нет в ячейке А2 получается 0, а в ячейке В2 – 1. Для этого используем функцию «ЕСЛИ» и вложим в нее функцию «ЗАМЕНИТЬ».

5) Для получения результата необходимо протянуть диапазон А2:С2 вниз до появления ошибки.

Ответ: 28

Задача 4. Дана программа для редактора:
НАЧАЛО
    ПОКА нашлось (01) ИЛИ нашлось (02) ИЛИ нашлось (03)
        заменить (01, 30)
        заменить (02, 101)
        заменить (03, 202)
    КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 20 единиц, 10 двоек и 70 троек. Сколько единиц было в исходной строке?

Решение:
Алгебраический способ решения:
1) Для начала необходимо разобраться, сколько цифр 1, 2 и 3 дают строки 01, 02, 03.
01 –> 30 (одна единица дает одну тройку);
02 –> 101 ->130 после первой замены в составе последовательности есть 01, к которой можно применить еще замену(одна двойка дает одну единицу и одну тройку).
03 –>202 –> 2130 аналогично, замену можно применить два раза (одна тройка дает одну единицу, одну двойку, одну тройку).
Пусть изначально в строке было Xединиц, Yдвоек, Z троек. Тогда из Xединиц получим X троек, из Yдвоек получим Y единиц и Y троек, из Zтроек получим Zединиц, Zдвоек, Zтроек. Этот результат можно записать в виде системы:
\(\left\{\begin{matrix}
Y+Z=20 \\
Z=10 \\
X+Y+Z=70\end{matrix}\right.\)
Решение системы: X=50, Y=10, Z=10
Ответ: 50

Задача 5. Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось(10)
ЕСЛИ нашлось(10) ТО
заменить(10, 001)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось(1)
ТО заменить(1, 01)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой программы поступает строка, состоящая из 1 и следующими за ней n нулями (n – натуральное двузначное число от 10 до 20). Вывести все значения n, при которых длина получившейся строки будет являться простым числом.

Решение:
Программный способ решения (Python):
1) В данной задаче необходимо вспомнить алгоритм поиска простых чисел. Число является простым, если не имеет других делителей кроме 1 и самого себя. Оформим проверку, является ли число простым в виде функции, которая если количество делителей больше двух, заканчивает работу.
defIsPrime(a):
c=0
for i in range (1,a+1):
if a%i==0:
c+=1
return c==2
2) Основную программу начнем с цикла for с функцией range, начальное значение 10 конечное 21, т.к. данная функция при работе не обрабатывает последнее значение.
forninrange(10,21):
3)В теле цикла формируем строку, где n задает переменное количество нулей.
s = "1"+ n*"0"
4) Далее формируем цикл с предусловием по данной программе для Исполнителя.
5) Замену в исходной строке осуществим с помощью функции replace.
6) По окончании цикла нужно подсчитать длину строки. Для этого используем функцию len(s).
7) Далее вызываем подпрограмму-функцию поиска простых чисел и с помощью оператора if проверяем, является ли полученная длина строки простым числом.

Пример полной программы:
defIsPrime(a):
c=0
for i in range (1,a+1):
if a%i==0:
c+=1
return c==2

for n in range(10,21):
s = "1"+ n*"0"
while "10" in s :
s = s.replace( "10", "001", 1)
s = s.replace( "1", "01", 1)
dl=len(s)
if IsPrime(dl):
print (i)

Ответ: 10 12 14 20

Задача 6. Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (333) ИЛИ нашлось (555)
ЕСЛИ нашлось (555)
ТО заменить (555, 3)
ИНАЧЕ заменить (333, 5)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 65 идущих подряд цифр 5? В ответе запишите полученную строку.

Решение:
Аналитический способ решения:
1) Чтобы понять принцип работы алгоритма, рассмотрим цепочку, состоящую из девяти пятерок – 555555555.
2) После трехкратного выполнения алгоритма результат будет 333, еще раз применим алгоритм и получим одну пятерку.
3) Таким образом, данный алгоритм преобразует 9 пятерок в одну.
4) 65:9=7, остаток 2, т.е. 63 пятерки преобразуются в 7 пятерок и остаются еще две, в сумме 9 пятерок, а соответствии с п2) получим одну 5.
Ответ: 5.

Задача 7. Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось(01) ИЛИ нашлось(02) ИЛИ нашлось(03)
заменить(01, 2302)
заменить(02, 10)
заменить(03, 201)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 58 единиц, 23 двойки и 15 троек. Сколько двоек было в исходной строке?

Решение:
Алгебраический метод решения:
1) Для начала необходимо разобраться, сколько цифр 1, 2 и 3 дают строки 01, 02, 03.
01 – 2302 – 2310 после первой замены в составе последовательности есть 02, к которой можно применить еще замену.
02 – 10
03 – 201 – 22310 аналогично , замену можно применить два раза.
Таким образом, получается, что 01 дает одну 1, одну 2 и одну 3; 02 дает одну 1; 03 дает одну 1, две 2 и одну 3
Записав полученный результат в виде системы уравнений, получим
\(\left\{\begin{matrix}
X+Y+Z=58 \\
X+2Y=23 \\
X+Z=15\end{matrix}\right.\)
Первое уравнение выражает количество 1 в итоговой строке, второе – количество 2 и, соответственно, третье – количество 3. После решения системы получим X=7, Y=43, Z=8
Ответ: 43

Задача 8. Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 69 идущих подряд цифр 8? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (3333) ИЛИ нашлось (8888)
    ЕСЛИ нашлось (3333)
         ТО заменить (3333, 88)
        ИНАЧЕ заменить (8888, 33)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение:
С использованием электронных таблиц:
1) В ячейку С1 нужно записать исходную строку любым образом. Для экономии времени можно воспользоваться функцией ПОВТОР

2) Далее нужно определить есть ли в данной строке подстроки “3333”и “8888”. Для этого можно использовать функцию НАЙТИ. Эта функция выдает ошибку, если подстрока не найдена.
3) Чтобы правильно обработать ошибку воспользуемся функцией ЕСЛИОШИБКА, которая в случае ошибки выдает 0, а при обнаружении подстроки его позицию. Для каждой подстроки воспользуемся отдельной ячейкой: например, в А2 - “3333”, в В2 - “8888”.

4) Теперь нужно построить строку, которая получится после первой итерации. Т.к. в исходной строке троек нет в ячейке А2 получается 0, а в ячейке В2 – 1. Для этого используем функцию ЕСЛИ и вложим в нее функцию ЗАМЕНИТЬ.

5) Для получения результата необходимо протянуть диапазон А2:С2 вниз до появления ошибки.

Ответ : 888

Задача 9. Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (4444) ИЛИ нашлось (7777)
ЕСЛИ нашлось (4444)
ТО заменить (4444, 77)
ИНАЧЕ заменить (7777, 44)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 86 идущих подряд цифр 4? В ответе запишите полученную строку.

Решение:
Программный способ решения (Python):
1) Записываем исходную строку в строковую переменную s= 86*'4'
2) Далее формируем цикл с предусловием. Два условия объединяем связкой «or» (логическое ИЛИ).
3)В тело цикла помещаем условный оператор: при выполнении условия будет произведена одна замена, в противном случае – другая.
Примерполнойпрограммы:

s = 86*'4'
while "4444" in s or "7777" in s:
if "4444" in s:
s = s.replace( "4444", "77", 1 )
else:
s = s.replace( "7777", "44", 1 )
print(s)

Ответ: 44

Задача 10. Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (222) ИЛИ нашлось (888)
ПОКА нашлось (555)
заменить (555, 8)
КОНЕЦ ПОКА
ЕСЛИ нашлось (222)
ТО заменить (222, 8)
ИНАЧЕ заменить (888, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Дана строка, состоящая из 21 цифры, причем первые три цифры – двойки, а остальные – пятерки. Какая строка получится в результате применения программы к данной строке?

Решение:
Аналитический способ решения:
1) Напомним, что тело цикла «ПОКА» выполняется, пока выполняется условие в этом цикле. Поэтому каждая тройка пятерок в исходной строке заменится на однувосьмерку, и на выходе из цикла получим строку 222888888
2) Далее осуществится замена трех двоек на одну восьмерку. Получим 8888888.
3) Теперь применим весь алгоритм два раза, в результате которого каждая тройка восьмерок заменится на двойку. Результат 228
Ответ: 228.

Задача 11. Дана программа для редактора:
НАЧАЛО
    ПОКА НЕ нашлось (00)
        заменить (01, 210)
        заменить (02, 3101)
        заменить (03, 2012)
    КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка начиналась с нуля и заканчивалась нулём, а между ними содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 61 единицу, 50 двоек и 18 троек. Сколько цифр было в исходной строке?

Решение:
Алгебраический метод:
1) Для начала необходимо разобраться, сколько цифр 1, 2 и 3 дают строки 01, 02, 03.
01 – 210
02 – 3101—31210 после первой замены в составе последовательности есть 01, к которой можно применить еще замену.
03 –2012 – 22102 – 22131210 аналогично , замену можно применить три раза.
Таким образом, получается, что 01 дает одну 1, одну 2 ; 02 дает две 1, одну 2 и одну 3; 03 дает три 1, три 2 и одну 3
Записав полученный результат в виде системы уравнений, получим
\(\left\{\begin{matrix}
X+2Y+3Z=61 \\
X+Y+3Z=50 \\
Y+Z=18\end{matrix}\right.\)
Первое уравнение выражает количество 1 в итоговой строке, второе – количество 2 и, соответственно, третье – количество 3. После решения системы получим X=18, Y=11, Z=7
Далее складываем количество единиц двоек и троек, прибавляем два нуля (в конце и в начале) и получаем 38.
Ответ: 38

Задача 12. Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 127 идущих подряд цифр «9»? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (333) ИЛИ нашлось (999)
ЕСЛИ нашлось (333)
ТО заменить (333, 9)
ИНАЧЕ заменить (999, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение:
С использованием электронных таблиц
1) В ячейку С1 нужно записать исходную строку любым образом. Для экономии времени можно воспользоваться функцией ПОВТОР

2) Далее нужно определить есть ли в данной строке подстроки “333” или “999”. Для этого можно использовать функцию НАЙТИ. Эта функция выдает ошибку, если подстрока не найдена.
3) Чтобы правильно обработать ошибку воспользуемся функцией ЕСЛИОШИБКА, которая в случае ошибки выдает 0, а при обнаружении подстроки его позицию. Для каждой подстроки воспользуемся отдельной ячейкой: например, в А2 - “333”, в В2 - “999”.

4) Теперь нужно построить строку, которая получится после первой итерации. Т.к. в исходной строке троек нет в ячейке А2 получается 0, а в ячейке В2 – 1. Для этого используем функцию «ЕСЛИ» и вложим в нее функцию «ЗАМЕНИТЬ».

5) Для получения результата необходимо протянуть диапазон А2:С2 вниз до появления ошибки.

Ответ : 339

Задача 13. Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (888) ИЛИ нашлось (77)
ЕСЛИ нашлось (888)
ТО заменить (888, 8777)
ИНАЧЕ заменить (77,8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 100 идущих подряд цифр 8.
В ответе через запятую запишите количество цифр 8 и цифр 7, которое будет в конечной строке.
Решение:
Аналитический способ:
1) Проанализировав программу, можно сделать такой вывод: каждая подстрока 888 будет заменяться на 8777. Подсчитаем, сколько таких замен будет в исходной строке 100:3= 33(1). Будет произведено 33 замены и в конце останется одна 8.
2) Далее, поскольку в каждой подстроке 8777 присутствуют 77, они будут заменены на 8. Получим 887.
3) Таким образом, подстрока 888 преобразуется в подстроку 887. Количество символов в итоговой строке не изменится. Замен было сделано 33, следовательно, семерок стало 33, а восьмерок осталось 67.
Ответ: 67, 33