209.95K
Category: programmingprogramming

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

1.

Задание 12
Выполнение алгоритмов для
исполнителя.
Микро-темы:
• Исполнитель Редактор
Повышенный уровень.
Максимальный балл – 1
Рекомендованное время на выполнение – 6 мин.

2.

Проверяемые элементы
содержания:
Умение анализировать результат
исполнения алгоритма на
алгоритмическом языке для
заданного исполнителя.

3.

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

4.

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

5.

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

6.

Задание 12 (Демо 2020/2021). Вариант решения 1.
чтобы понять принцип работы алгоритма,
НАЧАЛО
сначала рассмотрим строку из 10 цифр 8:
ПОКА нашлось (2222) ИЛИ
8888888888
нашлось (8888)
поскольку цепочки 2222 пока нет, сначала
ЕСЛИ нашлось (2222)
заменяем 8888 на 22:
ТО заменить (2222, 88)
22888888
ИНАЧЕ заменить (8888, 22)
цепочки 2222 снова нет, поэтому опять
КОНЕЦ ЕСЛИ
заменяем 8888 на 22:
КОНЕЦ ПОКА
222288
теперь появилась цепочка 2222, которая
КОНЕЦ
согласно алгоритму заменяется на 88:
Какая строка получится в
8888
результате применения
приведённой программы к
таким образом, в результате трёх замен
строке, состоящей из 70 идущих цепочка восьмёрок укоротилась на 6 цифр
подряд цифр 8? В ответе
посчитаем, сколько раз так можно сделать:
запишите полученную строку.
70 : 6 = 11,(6) – округляем вниз до 11
после 11 таких укорачиваний удалено 66
цифр 8, осталось всего 4, которые
заменяются на 22
Ответ: 22.

7.

Задание 12 (Демо 2020/21/22). Вариант решения 2. Python
НАЧАЛО
ПОКА нашлось (2222) ИЛИ
нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в
результате применения
приведённой программы к
строке, состоящей из 70 идущих
подряд цифр 8? В ответе
запишите полученную строку.
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)

8.

Задание 12 (Демо 2020/21/22). Вариант решения 2. PascalABC.NET
НАЧАЛО
ПОКА нашлось (2222) ИЛИ
нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в
результате применения
приведённой программы к
строке, состоящей из 70 идущих
подряд цифр 8? В ответе
запишите полученную строку.
begin
var s := StringOfChar('8', 70);
var p2 := Pos('2222',s);
var p8 := Pos('8888',s);
while (p2 > 0) or (p8 > 0) do begin
if p2 > 0 then begin
Delete( s, p2, 4 );
Insert( '88', s, p2 );
end
else begin
Delete( s, p8, 4 );
Insert( '22', s, p8 );
end;
p2 := Pos('2222',s);
p8 := Pos('8888',s);
end;
write(s);
end.

9.

Задание 12 (Демо 2020/21/22). Вариант решения 2. C++
НАЧАЛО
ПОКА нашлось (2222) ИЛИ
нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в
результате применения
приведённой программы к
строке, состоящей из 70 идущих
подряд цифр 8? В ответе
запишите полученную строку.
#include<iostream>
using namespace std;
int main()
{
string s(70, '8');
cout << s << endl;
int p2 = s.find("2222");
int p8 = s.find("8888");
while( p2 != string::npos or p8 != string::npos ) {
if( p2 != string::npos )
s.replace( p2, 4, "88" );
else
s.replace( p8, 4, "22" );
p2 = s.find("2222");
p8 = s.find("8888");
cout << s << endl;
}
cout << s;
}

10.

Задание 12 (Демо 2020/21/22). Вариант решения 3. Электронные таблицы
1) В ячейку С1 записываей исходную строку, используя ПОВТОР :
2) Определяем наличие «2222» и «8888» - функция НАЙТИ
3) Функция выдает ошибку, если образец не найден, ее можно избежать,
используя ЕСЛИОШИБКА (офис от 2007)
4) В А1 вносим формулу: =ЕСЛИОШИБКА(НАЙТИ(«2222»;С1);0)
5) В В1 вносим формулу: =ЕСЛИОШИБКА(НАЙТИ(«8888»;С1);0)

11.

Задание 12 (Демо 2020/21/22). Вариант решения 3. Электронные таблицы
9) Формулы диапозона А2:С2 протягиваем вниз. Последняя сторока перед
ошибкой это ответ.
Вместо вызовов функции ЗАМЕНИТЬ можно использовать функцию
Подставить:
ПОДСТАВИТЬ (С1; «2222»; «88»;1) И ПОДСТАВИТЬ (С1; «8888»;
«22»;1)
Аргумент 1 – означает: выполнить замену 1 раз для первого левого
вхождения.
После получения строки с ответом «22» в следующих строках ответ
просто повторяется – нет сообщеня о ошибке, как при использовании
ЗАМЕНИТЬ.
! В ЭТ как и в ЯП в логических выражениях(если и тд), 0=ЛОЖЬ, а другие
не равные 0, ИСТИНА.

12.

Задание 12.
ПОКА НЕ нашлось (><)
заменить(>1, 3>)
заменить(>2, 2>)
заменить(>3, 1>)
заменить(3<, <1)
заменить(2<, <3)
заменить(1<, <2)
КОНЕЦ ПОКА
На вход этой программы поступает
строка, начинающаяся с символа
«>», содержащая 20 цифр 1, 15 цифр
2, 40 цифр 3 и оканчивающаяся
символом «<». Определите, в каком
порядке должны располагаться
цифры во входной строке, чтобы
сумма цифр, получившаяся в
результате выполнения программы,
была максимально возможной. В
ответе запишите эту максимально
возможную сумму. Так, например,
если результат работы программы
представлял бы собой строку,
состоящую из 50 цифр 4, то верным
ответом было бы число 200.

13.

Задание 12 (Демо 2023).
Дана программа для Редактора:
На вход приведённой выше программе поступает строка, начинающаяся
с символа «>», а затем содержащая 39 цифр «0», n цифр «1» и 39 цифр
«2», расположенных в произвольном порядке. Определите наименьшее
значение n, при котором сумма числовых значений цифр строки,
получившейся в результате выполнения программы, является простым
числом.

14.

Задание 12 (Демо 2023). Решение
def is_sim(n):
check = True
for d in range(2, n):
if n % d == 0:
check = False
break
return check
ans = 117
count = 0
while not is_sim(ans):
ans += 4
count+=1
print(count)
• Данный алгоритм заменит 39 цифр
«0» на 39 единиц, а 39 цифр «2»
заменит на 39 цифр «2». Сумма
числовых
значений,
без
учёта
замененных цифр «1», равна 117. Так
как каждая цифра «1» в исходной
строке заменяется на две цифры «2»,
каждая цифра «1» в исходной строке
увеличивает
конечную
сумму
числовых значений на 4. Таким
образом, необходимо прибавить к
числу 117 число, кратное 4, так,
чтобы
получить
простое
число.
Ближайшее к 117 число, получаемое
прибавлением числа, кратного 4,
является 137 = 117 + 20.
• ответ — 5.
English     Русский Rules