Выполнение алгоритмов для исполнителя №12

1.

№12
Выполнение алгоритмов
для исполнителя

2.

Что нужно знать:
• правила выполнения линейных, разветвляющихся и
циклических алгоритмов;
• основные
операции
с
символьными
строками
(определение длины, выделение подстроки, удаление и
вставка символов, «сцепка» двух строк в одну);
• исполнитель – это человек, группа людей, животное,
машина или другой объект, который может понимать и
выполнять некоторые команды;
• в школьном алгоритмическом языке нц обозначает
«начало цикла», а кц – «конец цикла»; все команды между нц
и кц – это тело цикла, они выполняются несколько раз;
• запись нц для i от 1 до n обозначает начало цикла, в
котором переменная i (она называется переменной цикла)
принимает последовательно все значения от 1 до n с шагом 1.

3.

СТРОКА в языке Python - это неизменяемая последовательность символов.
S=”abcd”
Строковые константы заключаются в апострофы или кавычки
len(S)
Длина строки
str(<имя_объекта>)
Преобразования объекта в строку
eval(<строка_с_выражен
Вычислить результат выражения, заданного в виде обычной строки
ием>)
S.find(s1)
Ищет в строке S подстроку s1. Метод возвращает индекс первого
вхождения искомой подстроки. Если подстрока не найдена, то метод
возвращает -1.
S.rfind(s1)
Ищет в строке S подстроку s1. Метод возвращает индекс последнего
вхождения искомой подстроки. Если подстрока не найдена, то метод
возвращает -1.
S.replace(s1,s2)
Заменяет в строке S все вхождения подстроки s1 на подстроку s2.
S.count(s1)
Подсчитывает количество вхождений строки s1 в строку S.
Заменяет все символы строки S прописными буквами.
S.upper()
Заменяет все символы строки S строчными буквами.
S.lower()
Делает первую букву строки S прописной
S.capitalize()
Делает первую букву каждого слова прописной.
S.title()
s.strip(строка)
Возвращает копию исходной строки s, удаляя из ее начала и конца
все символы, которые указаны в аргументе до первого символа не
входящего в аргумент.
A=input().split()
Возвращающий список строк, разрезав исходную строку на части по
пробелам.
A=[‘red’,’green’,’blue]
Используя метод join() можно преобразовать список строк в одну
строку. При этом между элементами списка вставляется разделитель,
S=‘*’.join(A)
равный той строке, к которой применяется метод

4.

1) Метод count()
Метод возвращает количество элементов последовательности.
Синтаксис: s.count(v1, strt, end)
s - имя последовательности,
v1 - искомое значение,
strt - номер элемента, с которого начинается подсчет,
end - номер элемента, на котором подсчет заканчивается.
Последние два параметра (начало и конец) не являются обязательными.
Пример 1:
s = 'Hello, World'
c = s.count('o')
print(c)
Программа выведет на экран количество
символов 'o' в строке s, т.е. 2.
Пример 2:
s = 'blablablabl'
c = s.count('bl')
print(c)
Программа выведет на экран количество
вхождений подстроки 'bl' в строку s, т.е. 4.

5.

Пример 3:
s = 'aaaaa'
c = s.count('a', 2, 4)
print(c)
Программа выведет количество символов 'a' на
срезе [2:4]. Пояснение: каждый символ в строке
имеет номер, нумерация начинается с нуля. При
этом номер последнего символа не включается в
подсчет. Ответ:2
Пример 4:
L = [0, 1 , 2 , 0, 'h', '0']
c = L.count(0)
print(c)
Программа выведет количество чисел 0 в
списке L, т.е. 2. Обратите внимание, что
нулей, на самом деле, в списке три, однако
последний ноль записан в виде строки, т.к.
заключен в кавычки.

6.

2) Методы find() и rfind()
Методы используются для поиска подстроки в строке,
возвращая, при этом, номер первого символа искомой
подстроки в строке. Отличие метода find() от метода rfind()
заключается в том, что метод find() выполняет поиск слева
направо, а метод rfind() – справа налево.
Синтаксис: s.find(vl, strt, end)
где s – имя строки,
vl – искомая подстрока,
strt – номер символа, с которого начинается подсчет,
end – номер символа, на котором подсчет заканчивается.
Последние два параметра (начало и конец) не являются
обязательными.

7.

Пример 1:
s = 'peter piper picked a peck of pickled peppers'
c = s.find('ck')
print(c)

8.

Пример 2:
s = 'peter piper picked a peck of pickled peppers'
c = s.find('ck', 16, 31)
print(c)

9.

3) Метод replace()
Метод заменяет в строке n-ное количество искомых подстрок
на новую.
Синтаксис: s.replace(vl, new, n)
где s – имя строки,
vl – искомая подстрока,
new – строка, на которую требуется произвести замену,
n – количество замен.
Если количество замен не указано, то будут заменены все
вхождения искомой подстроки на новую.

10.

Пример 1:
s = 'peter piper picked a peck of pickled peppers'
s1 = s.replace('pe', 'Q')
print(s1)
Вывод:
Qter piQr picked a Qck of pickled QpQrs
Пример 2:
s = 'peter piper picked a peck of pickled peppers'
s1 = s.replace('pe', 'Q', 1)
print(s1)
Вывод:
Qter piper picked a peck of pickled peppers

11.

4) Метод split()
Разделяет строку по заданному разделителю и возвращает эти
строки в виде списка.
Синтаксис: s.split(s1, c)
где s - имя последовательности,
s1 - разделитель,
c – количество разделений.
Оба параметра не являются обязательными.

12.

Пример 1:
s = 'Hello, World'
c = s.split()
print(c)
Программа выведет на экран ['Hello,', 'World'],
то есть список, содержащий две строки.
Строка s будет разделена по пробелу.
Пример 2:
s = 'Hello, World! I’m here!'
c = s.split()
print(c)
Пример 3:
s = 'abrakadabra'
c = s.split('b')
print(c)
Программа выведет на экран
['Hello,', 'World!', 'I’m', 'here!'].
Программа выведет ['a', 'rakada', 'ra'], т.е.
строка будет разделена по символу 'b'.

13.

Пример 4:
s = 'ABCABCABC'
c = s.split('C', 1)
print(c)
Программа выведет ['AB', 'ABCABC'].
Разделителем является символ 'C', но разделена
она будет только один раз.

14.

5) len()
Возвращает количество элементов последовательности
(количество элементов списка, длину строки и т.д.).
Пример:
s = 'aaabbb'
print(len(s))
Программа выведет количество символов в
строке s (длину строки), т.е. 6.

15.

1) Редактор получает на вход строку цифр и преобразовывает её. Редактор может
выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если
цепочки v в строке нет, эта команда не изменяет строку.
нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если
она встречается, то команда возвращает логическое значение «истина», в противном
случае возвращает значение «ложь». Строка при этом не изменяется.
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой программы к строке,
состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.

16.

Решение (теоретическое):
1) чтобы понять принцип работы алгоритма, сначала рассмотрим строку из
10 цифр 8:
8888888888
1) поскольку цепочки 2222 пока нет, сначала заменяем 8888 на 22:
22888888
1) цепочки 2222 снова нет, поэтому опять заменяем 8888 на 22:
222288
1) теперь появилась цепочка 2222, которая согласно алгоритму заменяется
на 88:
8888
1) таким образом, в результате трёх замен цепочка восьмёрок укоротилась на
6 цифр
2) посчитаем, сколько раз так можно сделать: 70 : 6 = 11,(6) – округляем вниз
до 11
3) после 11 таких укорачиваний удалено 66 цифр 8, осталось всего 4,
которые заменяются на 22
4) Ответ: 22.

17.

s = 70*'8'
while "2222" in s or "8888" in s:
if "2222" in s:
s = s.replace( "2222", "88", 1 )
else:
s = s.replace( "8888", "22", 1 )
print(s)

18.

2) Редактор получает на вход строку цифр и преобразовывает её. Редактор может
выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если
цепочки v в строке нет, эта команда не изменяет строку.
нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Если она встречается, то команда возвращает логическое значение «истина», в
противном случае возвращает значение «ложь». Строка при этом не изменяется.
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (111)
заменить (111, 2)
заменить (22, 1)
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой выше программы к
строке вида 1…12…2, состоящей из 44 единиц и 21 двойки? В ответе запишите
полученную строку.

19.

Решение (теоретическое):
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

20.

Самостоятельно на Python:
s = 44*'1'+21*'2'
while "111" in s:
if "111" in s:
s = s.replace( "111", "2", 1 )
if "22" in s:
s = s.replace( "22", "1", 1 )
print(s)

21.

3) Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две
команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она
встречается, то команда возвращает логическое значение «истина», в противном случае возвращает
значение «ложь». Строка при этом не изменяется.
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (222) ИЛИ нашлось (555)
ЕСЛИ нашлось (222)
ТО заменить (222, 5)
ИНАЧЕ заменить (555, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой выше программы к строке, состоящей из
247 идущих подряд цифр 2?
В ответе запишите полученную строку.
Самостоятельно на Python:
552

22.

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

23.

5) Ниже приведена программа для исполнителя Редактор.
НАЧАЛО
ПОКА нашлось (722) ИЛИ нашлось (557)
ЕСЛИ нашлось (722)
ТО заменить (722, 57)
ИНАЧЕ заменить (557, 72)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
572
На вход этой программе подается строка, состоящая из 55 цифр;
последняя цифра в строке — цифра 7, а остальные цифры —
пятёрки. Какая строка получится в результате применения
программы к этой строке? В ответе запишите полученную
строку.

24.

6) Ниже приведена программа для исполнителя Редактор.
НАЧАЛО
ПОКА нашлось (19) ИЛИ нашлось (299) ИЛИ нашлось (3999)
заменить (19, 2)
заменить (299, 3)
заменить (3999, 1)
КОНЕЦ ПОКА
КОНЕЦ
29
На вход этой программе подаётся строка длины 99, состоящая
из цифры 1, за которой следуют 98 идущих подряд цифр 9.
Какая строка получится в результате применения программы к
этой строке? В ответе запишите полученную строку.

25.

7) Какая строка получится в результате применения приведённой ниже
программы к строке длины 101, в которой первый и последний символ –
это цифры 1, а остальные символы – цифры 8?
В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (81) ИЛИ нашлось (882) ИЛИ нашлось (8883)
ЕСЛИ нашлось (81)
ТО заменить (81, 2)
ИНАЧЕ ЕСЛИ нашлось (882)
ТО заменить (882, 3)
ИНАЧЕ заменить (8883, 1)
КОНЕЦ ЕСЛИ
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
13

26.

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

27.

9) Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (49) ИЛИ нашлось (97) ИЛИ нашлось (47)
ЕСЛИ нашлось (47)
ТО заменить (47, 74)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (97)
ТО заменить (97, 79)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (49)
ТО заменить (49, 94)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
794
На вход приведённой ниже программе поступает строка, содержащая 40
цифр 7, 40 цифр 9 и 50 цифр 4, расположенных в произвольном порядке.
Запишите без разделителей символы, которые имеют порядковые номера
25, 71 и 105 в получившейся строке.