https://stepik.org/82751
Вариант создан по мотивам ДЕМО – 2026 (прототип №1)
Закон диалектики: единство и борьба противоположностей. Георг Гегель.
1.5
Разбор демо_2026
https://viktsbor.blogspot.com/
План подготовки учащихся к сдаче ЕГЭ
1) Разбор текущего варианта демо (сначала самостоятельно, а уж потом с учениками)
2) Создание своего (уникального прототипа демо-варианта)
3) Проверка знаний учащихся по прототипу и разбиение учащихся по рейтингу (каждому свой номер: 1 - самый слабый … N – самый сильный)
В этом (п. №3) вся интрига подготовки, ваше педагогическое «чутье»
4) Подготовка (с учетом п.3) тренажера с автоматической проверкой выполнения заданий и с непрерывным (постоянным) доступом к выполнению этих заданий в заранее оговоренные с учащимися сроки, например:
- урок (или спецкурс) в понедельник;
- до 20-00 воскресенья (тек. недели) они эти задания делают (выполняют)
- после часа X смотрим результаты (с автоматикой см. журнал)
5) Настройка, подготовка, корректировка тренажера к запуску на следующий срок (обычно это неделя), возможна смена номеров вариантов у учащихся
6) Проверочная промежуточная работа на N вариантов (обычно проводим раз в месяц).
1. На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, нумерация
населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог из пункта G в пункт E и из пункта F в пункт H. В ответе запишите целое число.
Определите, какова сумма протяжённостей дорог из пункта G в пункт E и из пункта F в пункт H. В ответе запишите целое число.
[1]. На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог GE, FH и DA, если GA больше, чем GC. В ответе запишите целое число.
1. В таблице содержатся сведения о длинах дорог между населёнными пунктами (в км). На рисунке справа та же схема дорог изображена в виде графа. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите сумму длин дорог: EF, GA и CD.
2. Миша заполнял таблицу истинности логической функции F:
(x \/ y) /\ ¬ (y ≡ z) /\ ¬ w,
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных:
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
x y z w
0 1 0 0
1 0 1 0
1 1 0 0
(x \/ y) /\ ¬ (y ≡ z) /\ ¬ w,
print("x y z w")
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
f= (x or y) and not(y == z) and not(w)
if f == 1: print(x,y,z,w)
0
0
0
0
[2]. Миша заполнял таблицу истинности логической функции (x \/ y) /\ ¬ (y ≡ z) /\ ¬ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных:
[3]. В файле приведена база данных «Молочные продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц. Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение октября 2024 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок, шт. внесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.
ID_операции | Дата | ID_магазина | Артикул | Кол-во_упак, шт. | Тип_операции
Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Заголовок таблицы имеет следующий вид.
Артикул | Отдел | Наимен_товара | Ед_изм | Кол-во_в_упак. | Цена_за_упаковку
Таблица «Магазин» содержит информацию о
местонахождении магазинов. Заголовок таблицы
имеет следующий вид.
ID магазина | Район | Адрес
На рисунке приведена схема указанной базы данных.
Используя информацию из приведённой базы данных, определите, на какую сумму (в руб.) было продано варенца термостатного в магазинах Нагорного
района за период с 5 по 14 октября включительно.
В ответе запишите только число.
определите, на какую сумму (в руб.) было продано варенца термостатного в магазинах Нагорного района за период с 5 по 14 октября включительно.
4. По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Е - 10; Ж - 010; З - 011; Д - 11.
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
4. По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Е - 10; Ж - 010; З - 011; Д - 11.
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
[4]. По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З и И. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Е - 10; Ж - 010; З - 011; Д - 11.
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г и И.
5. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются её три последние двоичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 12(10) = 1100(2) результатом является число 1100100(2) = 100(10), а для исходного числа 4(10) = 100(2) это число 10011(2) = 19(10).
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 200.
for n in range(10,3000):
s = bin(n)[2:]
if n % 3 == 0:
s = s + s[-3:]
else:
s = s + bin((n%3)*3)[2:]
r = int(s, 2)
if r>=200: print(n); break
5. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются её три последние двоичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 12(10) = 1100(2) результатом является число 1100100(2) = 100(10), а для исходного числа 4(10) = 100(2) это число 10011(2) = 19(10).
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 200.
def fs(n):
t = ''
while n > 0:
t = str(n % 2) + t
n //= 2
return t
for n in range(10,3000):
s = fs(n)
if n % 3 == 0:
s = s + s[-3:]
else:
s = s + fs((n%3)*3)
r = int(s, 2)
if r>=200: print(n); break
[5]. На вход алгоритма подаётся натуральное число. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа.
2. Далее эта запись обрабатывается по следующему правилу:
a. если число делится на 3, то к этой записи дописываются две последние троичные цифры;
b. если число на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа. Например, для исходного числа 12(10)=110(3) результатом является число 11010(3)=111(10), а для исходного числа 4(10) = 11(3) это число 1112(3)=41(10). Укажите максимальное число, не превышающее 272, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
def fs(n):
t = ''
while n > 0:
t = str(n % 3) + t
n //= 3
return t
mn = 0
for n in range(4,2000):
s = fs(n)
if n % 3 == 0:
s = s + s[-2:]
else:
s = s + fs((n%3)*5)
r = int(s, 3)
if r<=272: mn = max(mn, r)
print(mn)
6. Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает,
что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм.
Повтори 2 [Вперёд 14 Налево 270 Назад 12 Направо 90]
Поднять хвост
Вперёд 9 Направо 90 Назад 7 Налево 90
Опустить хвост
Повтори 2 [Вперёд 13 Направо 90 Вперёд 6 Направо 90]
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченного заданными алгоритмом линиями, включая точки на линиях.
0) использовать Черепаха
1) опустить хвост -Черепашка при движении оставляет следы на песке
2) поднять хвост-Черепашка не оставляет следов
3) вперед (50) -Движение вперед на 50 шагов (точек экрана)
4) вправо (90)-Повернуть направо на 90º
5) влево (180)-Повернуть налево на 180º
6) назад (60) -Движение назад на 60 точек
7) цикл (n раз)
нц 5 раз
вперед (10)
вправо (120)
кц
использовать Черепаха
алг
нач
опустить хвост
нц 2 раз
вперед(14); влево(270)
назад(12); вправо(90)
кц
поднять хвост
вперед(9); вправо(90)
назад(7); влево(90)
опустить хвост
нц 2 раз
вперед(13); вправо(90)
вперед(6); вправо(90)
кц
кон
Черепашья графика в Python_e
from turtle import * - подключение черепахи
tracer(0) – рисование без задержки (быстро)
forward(Количество шагов) — вперёд на K шагов (fd);
backward(Количество шагов) — назад на K шагов; (bk)
right(Угол) — направо на R градусов (rt);
left(Угол) —налево на L градусов (lt);
color(Цвет пера, Цвет заливки) — цвет пера и заливки;
goto(X, Y) — перемещается в точку X, Y;
dot(Размер, Цвет) — точка в текущей позиции;
speed(Скорость) — скорость перемещения (от 0 до 10);
xcor() — возвращает текущую координату по X;
ycor() — возвразает текущую координату по Y;
up() — поднимает “перо”;
down() — опускает “перо”;
begin_fill() — начинает заливку контура;
end_fill() — прекращает заливку контура;
done() — завершает работу программы.
from turtle import *
k=20; up(); goto(-1*k,-10*k) # k-масштаб
lt(90); down(); tracer(0)
for i in range(2):
fd(14*k); lt(270); bk(12*k); rt(90)
up()
fd(9*k); rt(90); bk(7*k); lt(90)
down();
for i in range(2):
fd(13*k); rt(90); fd(6*k); rt(90)
up()
for x in range(-15*k, 1*k+1, k):
for y in range(-12*k, 13*k+1, k):
goto(x,y); dot(3)
done()
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченного заданными алгоритмом линиями, включая точки на линиях.
7_a. Виталий фотографирует интересные места и события цифровой камерой своего смартфона. Каждая фотография представляет собой растровое изображение размером 1024×768 пикселей, при этом используется палитра из 2^30 цветов. В конце дня Виталий отправляет снимки друзьям с помощью приложения-мессенджера. Для экономии трафика приложение оцифровывает снимки повторно, используя размер 800×600 пикселей и глубину цвета 28 бит. Сколько Кбайт трафика экономится при передаче 100 фотографий? В ответе укажите целую часть полученного числа.
7_b. Музыкальный фрагмент был записан в формате моно, оцифрован и сохранён в виде файла без сжатия данных. Размер полученного файла − 35 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате стерео (двухканальная запись) с частотой дискретизации в 3,5 раза больше, чем в первый раз. Сжатие данных не производилось. Укажите размер файла в Мбайт, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно.
7_a. Виталий фотографирует интересные места и события цифровой камерой своего смартфона. Каждая фотография представляет собой растровое изображение размером 1024×768 пикселей, при этом используется палитра из 2^30 цветов. В конце дня Виталий отправляет снимки друзьям с помощью приложения-мессенджера. Для экономии трафика приложение оцифровывает снимки повторно, используя размер 800×600 пикселей и глубину цвета 28 бит. Сколько Кбайт трафика экономится при передаче 100 фотографий? В ответе укажите целую часть полученного числа.
(1024×768×30 - 800×600×28)*100/(2^13)
[7_a](мод). Виталий фотографирует интересные места и события цифровой камерой своего смартфона. Каждая фотография представляет собой растровое изображение размером 1024×768 пикселей, при этом используется палитра из 1073741924 цветов. В конце дня Виталий отправляет снимки друзьям с помощью приложения-мессенджера. Для экономии трафика приложение оцифровывает снимки повторно, используя размер 800×600 пикселей и глубину цвета 28 бит. Сколько Кбайт трафика экономится при передаче 100 фотографий? В ответе укажите целую часть полученного числа.
from math import *
b=ceil(log(1073741924,2))
d=int((1024*768*b - 800*600*28)*100/(2**13))
print(d)
8. Все пятибуквенные слова, составленные из букв С, Т, Р, О, К, А, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААК
3. ААААО
4. ААААР
5. ААААС
6. ААААТ
……
Определите, под каким номером в этом списке стоит последнее слово с чётным номером, которое не начинается с букв А, С или Т и при этом содержит в своей записи ровно две буквы О. Примечание. Слово – последовательность идущих подряд букв, не обязательно осмысленная.
s='АКОРСТ'; s1=''; n=0; np=-1
for x1 in s:
for x2 in s:
for x3 in s:
for x4 in s:
for x5 in s:
s1 = x1 + x2 + x3 + x4+x5; n+=1
kO=s1.count('О')
if (kO==2) and n%2==0 and not(x1 in 'АСТ'): np=n
print(np)
8. Все пятибуквенные слова, составленные из букв С, Т, Р, О, К, А, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
……
Определите, под каким номером в этом списке стоит последнее слово с чётным номером, которое не начинается с букв А, С или Т и при этом содержит в своей записи ровно две буквы О. Примечание. Слово – последовательность идущих подряд букв, не обязательно осмысленная.
8. Все пятибуквенные слова, составленные из букв С, Т, Р, О, К, А, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
……
Определите, под каким номером в этом списке стоит последнее слово с чётным номером, которое не начинается с букв А, С или Т и при этом содержит в своей записи ровно две буквы О. Примечание. Слово – последовательность идущих подряд букв, не обязательно осмысленная.
from itertools import *
n=0; np=-1
for i in product ('АКОРСТ',repeat=5): # перестановки с повторениями
s=''.join(i); n+=1
kO=s.count('О')
if (kO==2) and n%2==0 and not(s[0] in 'АСТ'): np=n
print(np)
[8]. Все 5-буквенные слова, в составе которых могут быть только буквы П, Р, О, Г, У, Л, К, А, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. AAAAA
2. ААААГ
3. ААААК
4. ААААЛ
5. AAAAO
6. ААААП
7. AAAAP
s='АГКЛОПРУ'; k=0; s1=''; n=0
for x1 in s:
for x2 in s:
for x3 in s:
for x4 in s:
for x5 in s:
s1 = x1 + x2 + x3 + x4+x5; n+=1
kO=s1.count('О')
if (kO==2) and n%2!=0 and x1 != 'Г': k+=1
print(k)
Сколько существует слов в списке с нечётными
номерами, которые не начинаются с буквы Г
и содержат две буквы О?
9. Откройте файл электронной таблицы, содержащей в каждой строке семь натуральных чисел. Определите сумму чисел в строке с наибольшим номером, для которой выполнены оба условия:
– в строке есть одно число, которое повторяется трижды, остальные четыре числа различны;
– среднее арифметическое неповторяющихся чисел строки не больше повторяющегося числа.
В ответе запишите только число.
9. Откройте файл электронной таблицы, содержащей в каждой строке семь натуральных чисел. Определите сумму чисел в строке с наибольшим номером, для которой выполнены оба условия:
– в строке есть одно число, которое повторяется трижды, остальные четыре числа различны;
– среднее арифметическое неповторяющихся чисел строки не больше повторяющегося числа.
В ответе запишите только число.
f=open('DEMO_9.txt')
smn=0
for s in f:
a=list(map(int,s.split()))
a1=[]
a2=[]
for x in a:
if a.count(x)==3:
a2.append(x)
if a.count(x)==1:
a1.append(x)
if len(a2)==3 and len(a1)==4 and sum(a1)/4<=a2[0]:
smn=sum(a)
print(smn)
[9]. Откройте файл электронной таблицы, содержащей в каждой строке семь натуральных чисел. Определите сумму чисел в строке с наибольшим номером, для которой выполнены оба условия:
— в строке только два числа повторяются ровно два раза, остальные четыре числа различны;
— максимальное число строки
является повторяющимся числом.
В ответе запишите только число.
f=open('9_4_t_2.txt')
smn=0
for s in f:
a=list(map(int,s.split()))
a1=[]
a2=[]
for x in a:
if a.count(x)==2:
a2.append(x)
if a.count(x)==1:
a1.append(x)
if len(a2)==4 and len(a1)==4 and max(a)==max(a2):
smn=sum(a)
print(smn)
10. C помощью текстового редактора определите, сколько раз встречается сочетание букв «рук» или «Рук» в составе других слов, но не как отдельное слово, в тексте глав XIII, XIV и XV романа И.С. Тургенева «Отцы и дети».
В ответе укажите только число.
[10]. C помощью текстового редактора определите, сколько раз встречается сочетание букв «рук» или «Рук» в составе других слов, но не как отдельное слово, в тексте глав XIV, XV, XVI и XVII романа И.С. Тургенева «Отцы и дети».
В ответе укажите только число.
11. На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2783 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит. Известно, что для хранения 3 845 627 серийных номеров требуется не менее 11 Гбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.
1. Сколько байт занимает 1 номер: ba=11*2**30/3_845_627 (окр. в большую стор.)
2. Сколько бит занимает 1 символ: bi=ba*8/2783 (окр. в большую стор.)
3. ответ: 2**(bi-1)+1
[11]. На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2783 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит. Известно, что для хранения 3 845 627 [3 645 827] серийных номеров требуется не менее 11 Гбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.
from math import *
ba=ceil((11*2**30)/3_845_627)
bi=ceil((ba*8)/2783)
print(2**(bi-1)+1)
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может
совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом:
в текущую ячейку записывается символ «0», затем головка
сдвигается в соседнюю слева ячейку и переходит в состояние q3.
12. Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a0, a1, …, an–1}), включая специальный пустой символ a0. Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q = {q0, q1, …, qn–1}. В начальный момент времени головка находится в начальном состоянии q0. На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии. Программа работы исполнителя МТ задаётся в табличном виде.
12. Приведём пример выполнения программы, заданной таблично.
На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «λ». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z». Программа:
заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности символов «X». Возможное начальное состояние исполнителя:
Конечное состояние исполнителя после завершения выполнения программы:
12. Выполните задание.
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя:
После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды.
Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
12. Выполните задание. На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.
12. Выполните задание. На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя:
После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.
342 – 0
657 – 0
13. В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске.
Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы. Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств.
Сеть задана IP-адресом одного из входящих в неё узлов 191.128.66.83 и сетевой маской 255.192.0.0. Найдите в данной сети наибольший IP-адрес, который может быть назначен компьютеру. В ответе укажите найденный IP-адрес без разделителей.
Например, если бы найденный адрес был равен 111.22.3.44, то в ответе следовало бы записать: 11122344.
191191255254
14_b. Операнды арифметического выражения записаны в системе счисления с основанием 29.
923x874(29) + 524x6152(29)
В записи чисел переменной x обозначена неизвестная цифра из алфавита 29-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 28. Для найденного x вычислите частное от деления значения арифметического выражения на 28 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
for x in range(29):
c1=9*29**6+2*29**5+3*29**4+x*29**3+8*29**2+7*29**1+4
c2=5*29**7+2*29**6+4*29**5+x*29**4+6*29**3+1*29**2+5*29**1+2
c=c1+c2
if c%28==0:
p=c//28
print(p)
[14]. Операнды арифметического выражения записаны в системе счисления с основанием 29:
923x874(29) + 624x5162(29)
В записи чисел переменной x обозначена неизвестная цифра из алфавита 29-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 23. Для найденного x вычислите частное от деления значения арифметического выражения на 23 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
for x in range(29):
c1=9*29**6+2*29**5+3*29**4+x*29**3+8*29**2+7*29**1+4
c2=6*29**7+2*29**6+4*29**5+x*29**4+5*29**3+1*29**2+6*29**1+2
c=c1+c2
if c%23==0:
p=c//23
print(p)
14a. Операнды арифметического выражения записаны в системе счисления с основанием 19.
98897x21(19) + 2x923(19)
В записи чисел переменной x обозначена неизвестная цифра из алфавита 19-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 18. Для найденного x вычислите частное от деления значения арифметического выражения на 18 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
for x in '0123456789abcdefghi':
c=int('98897'+x+'21',19)+int('2'+x+'923',19)
if c%18==0:
print(x,c//18)
15_demo. На числовой прямой даны два отрезка: P = [25; 64] и Q = [40; 115]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение:
(x ∈ P) → (((x ∈ Q) /\ ¬ (x ∈ A)) → ¬ (x ∈ P))
истинно (т.е. принимает значение 1) при любом значении переменной х.
p = list(range(25 , 65))
q = list(range(40 , 116))
a = []
for x in range(1, 301):
f=(x in p) <= (((x in q) and (not(x in a))) <= (not(x in p)))
if f == 0:
a.append(x)
print(a[-1] - a[0])
15_b. (логическое «И») Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение :
(X & 56 ≠ 0) → ((X & 48 = 0) → (X & A ≠ 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
def f(x,a):
return (x&56!=0)<=((x&48==0)<=(x&a!=0))
for a in range(1, 100):
if all(f(x,a)==1 for x in range(1,1000)):
print(a)
break;
15_c
Для какого наименьшего целого неотрицательного числа A выражение
(x + 2y < A) \/ (y > x) \/ (x > 60)
тождественно истинно, т.е. принимает значение 1 при любых целых
неотрицательных x и y?
def f(a,x,y):
return (x+2*y<a) or (y>x) or (x>60)
for a in range(1000):
if all(f(a,x,y)==1 for x in range(1000) for y in range(1000)):
print(a)
break
16_a. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = (n – 1)× F(n − 1), если n > 1.
Чему равно значение выражения (F(2024) + 2 × F(2023)) / F(2022)?
import sys
sys.setrecursionlimit(20000)
def f(n):
if n==1: return 1
if n>1: return (n-1)*f(n-1)
print((f(2024) + 2*f(2023))//f(2022))
16_a. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = (n – 1)× F(n − 1), если n > 1.
Чему равно значение выражения (F(2024) + 2 × F(2023)) / F(2022)?
a=[1]*2025
for n in range (2, 2025):
a[n]=(n-1)*a[n-1]
print((a[2024] + 2*a[2023])//a[2022])
16_demo. Алгоритм вычисления функций F(n) и G(n), где n – целое число, задан следующими соотношениями:
F(n) = 2 × (G(n – 3) + 8);
G(n) = 2 × n, если n < 10;
G(n) = G(n – 2) + 1, если n ≥ 10.
Чему равно значение выражения F(15_548)?
import sys
sys.setrecursionlimit(20000)
def g(n):
if n<10: return 2*n
if n>=10: return g(n-2)+1
def f(n):
return 2*(g(n-3)+8)
print(f(15_548))
17. В файле содержится последовательность натуральных чисел. Её элементы
могут принимать целые значения от 1 до 100_000 включительно. Определите
количество пар последовательности, в которых только один из элементов
является двузначным числом, а сумма элементов пары кратна минимальному двузначному элементу последовательности. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
17. В файле содержится последовательность натуральных чисел. Её элементы могут принимать целые значения от 1 до 100_000 включительно. Определите количество пар последовательности, в которых только один из элементов является двузначным числом, а сумма элементов пары кратна минимальному двузначному элементу последовательности. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
def f(x): return x>9 and x<100
a = [int(x) for x in open('DEMO_17.txt')]
m1=min([x for x in a if x>9 and x<100])
k=0; m=0
for i in range(len(a)-1):
s=a[i]+a[i+1]
if (f(a[i]) + f(a[i+1])) == 1 and s%m1==0:
k+=1
if (s>m): m=s
print(k,m)
[17]. В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от -100 000 до 100 000 включительно. Определите количество пар последовательности, в которых только один из элементов является двузначным числом, а сумма элементов пары кратна минимальному двузначному элементу последовательности. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
def f(x): return abs(x)>9 and abs(x)<100
a = [int(x) for x in open('17_4_t_2.txt')]
m1=min([x for x in a if abs(x)>9 and abs(x)<100])
k=0; m=0
for i in range(len(a)-1):
s=a[i]+a[i+1]
if (f(a[i]) + f(a[i+1])) == 1 and s%m1==0:
k+=1
if (s>m): m=s
print(k,m)
18. Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой;
это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые
накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа – сначала максимальную сумму, затем минимальную. Исходные данные представляют
собой электронную таблицу размером N × N, каждая ячейка
которой соответствует клетке квадрата. Внутренние и внешние
стены обозначены утолщёнными линиями. Пример входных данных
=A1
=A21+A2
=A21+B1
=МИН(B21;A22)+B2
=A1
=A21+A2
=A21+B1
=МАКС(B21;A22)+B2
=A1
=A21+A2
=A21+B1
=МАКС(B21;A22)+B2
23
19_demo. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 17, 15 или 5 камней. Игра завершается, когда количество камней в куче становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 30 или менее камней. В начальный момент в куче было S камней, S ≥ 31.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
[ 30 ---> 130 ]
19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раза (количество камней округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 17, 15 или 5 камней. Игра завершается, если камней в куче становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 30 или менее камней. В начальный момент в куче было S камней, S ≥ 31.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
def f(x, p):
if x <= 30 or p > 2: #Условия завершения игры
return p == 2
if p % 2 != 0:
return f(x - 3, p + 1) or f(x - 5, p + 1) or f(x // 4, p + 1)
else:
return f(x - 3, p + 1) and f(x - 5, p + 1) and f(x // 4, p + 1)
for s in range (31, 300 + 1): #Перебор S
if f(s, 0): #в 1-й куче S к.
print(s)
20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
def f(x, p):
if x <= 30 or p > 3: #Условия завершения игры
return p == 3
if p % 2 == 0:
return f(x - 3, p + 1) or f(x - 5, p + 1) or f(x // 4, p + 1)
else:
return f(x - 3, p + 1) and f(x - 5, p + 1) and f(x // 4, p + 1)
for s in range (31, 300 + 1): #Перебор S
if f(s, 0): #в 1-й куче S к.
print(s)
21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
def f(x, p):
if x <= 30 or p > 4: #Условия завершения игры
return p == 2 or p == 4
if p % 2 != 0:
return f(x - 3, p + 1) or f(x - 5, p + 1) or f(x // 4, p + 1)
else:
return f(x - 3, p + 1) and f(x - 5, p + 1) and f(x // 4, p + 1)
for s in range (31, 300 + 1): #Перебор S
if f(s, 0): #в 1-й куче S к.
print(s)
Необходимо выкинуть значения, которые повторяются в здании 19, например:
в здании 19 получились следующие значения: 70; 71; 72
в здании 21 получились следующие значения: 70; 71; 72; 83; 84
Ответ будет: 83
22. В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A
и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0. Определите максимальное количество процессов, которые могут быть завершены за первые 17 мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
LibreOffice Calc
=МАКС(ВПР(C3; A:E; 5; 0); ВПР(D3; A:E; 5; 0))+B3
=МАКС(ВПР…
=ЕСЛИ(E3<=17…
23. Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 19
результатом является 2, при этом траектория вычислений не содержит числа
7 и содержит 13?
Траектория вычислений программы – это последовательность результатов
выполнения всех команд программы. Например, для программы СBА при
исходном числе 22 траектория состоит из чисел 7, 3, 2.
23. Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является 2, при этом траектория вычислений не содержит числа 7 и содержит 13? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2.
def f (x, y):
if (x==y): return 1
elif (x<y) or x==7: return 0
else: return f(x-1,y)+f(x-4,y)+f(x//3,y)
print(f(19,13)*f(13,2))
[24_a]. Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ T встречается ровно 100 раз. Для выполнения этого задания следует написать программу.
s = open("24.txt").readline()
m=0; k=100
a=[x for x in range(len(s)) if s[x]=='T']
for i in range(len(a)-(k+1)):
m=max(m,a[i+k+1]-a[i]-1)
print(m)
k=2 a=[0, 3, 7, 12]
[24_b]. Текстовый файл состоит из десятичных цифр и заглавных букв латинского
алфавита. Определите в прилагаемом файле максимальное количество
идущих подряд символов, среди которых подстрока 2025 встречается
не менее 90 раз и при этом содержится ровно 80 букв Y.
В ответе запишите число – количество символов в найденной последовательности.
Для выполнения этого задания следует написать программу.
s = open("DEMO_24.txt").readline()
m=0; k=80
a=[x for x in range(len(s)) if s[x]=='Y']
for i in range(len(a)-(k+1)):
k2025=s[a[i]:a[i+k+1]].count('2025') #кол-во '2025' в строке с 80 'Y'
if k2025>=90: m=max(m,a[i+k+1]-a[i]-1)
print(m)
[25_a]. Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M признаётся равным нулю. Напишите программу, которая перебирает целые числа, бо́льшие 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 4. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M. Например, для числа 20 М = 2 + 10 = 12. Количество строк в таблице для ответа избыточно.
25_b. Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 10^10, найдите все числа,
соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1917. Количество строк в таблице для ответа избыточно.
25_a. Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M признаётся равным нулю. Напишите программу, которая перебирает целые числа, бо́льшие 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 4. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M. Например, для числа 20 М = 2 + 10 = 12. Количество строк в таблице для ответа избыточно.
k=0
for x in range(800001,800500):
for y in range(2,x//2+1):
if x%y==0:
if y!=x//y and (y+x//y)%10==4:
k+=1
print(x, y+x//y)
break
if k==5: break
25_b. Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 10^10, найдите все числа,
соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1917. Количество строк в таблице для ответа избыточно.
from fnmatch import *
for a in range(1917,10**10+1,1917):
if fnmatch(str(a),'3?12?14*5'):
print(a, a//1917)
26. Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы. В рейтинговом списке маркетологи располагают продукты по следующему алгоритму:
– все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию;
– если минимальное число в этом упорядоченном списке – срок хранения, то продукт в рейтинге занимает первое свободное место от его начала;
– если минимальное число – срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга;
– если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание.
Этот алгоритм применяется последовательно для размещения всех N продуктов. Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места. Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество продуктов. Следующие N строк содержат пары чисел, обозначающих соответственно срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные). Запишите в ответе два натуральных числа: сначала номер последнего продукта, для которого будет определено его место в рейтинге, затем – количество продуктов, которые займут в рейтинге более низкие места.
data = []
file = open('26_4_t_2.txt')
next(file); id = 1
for line in file:
parts = line.split()
best_before = int(parts[0]) # хранение
exp_date = int(parts[1]) # срок годности
min_of_dates = min(best_before, exp_date)
if min_of_dates == best_before:
type = "Хранение"
else:
type = "Годность"
good = {
"Срок хранения" : best_before,
"Срок годности" : exp_date,
"Минимальное число": min(int(parts[0]), int(parts[1])),
"Тип" : type,
"Порядковый номер" : id
}
data.append(good)
id += 1
data = sorted(data, key=lambda x: x["Минимальное число"])
goods_after = sum(1 for detail in data[:-1] if detail["Тип"] == "Годность")
print(data[-1]["Порядковый номер"], goods_after)
Пример:
5
30 50
100 155
150 170
10 160
120 55
При таких исходных данных порядок расположения продуктов в рейтинге
следующий: 4, 1, 5, 2, 3. Последним займёт своё место в рейтинге продукт 3.
При этом один продукт
5 120 55, который займет в рейтинге более низкое место.
==>
3 1
4 10 160
1 30 50
5 120 55
2 100 155
3 150 170
f = open('26.txt')
n = int(f.readline())
a = []; i=1
for s in f:
sr1, sr2 = map(int, s.split())
m=min(sr1,sr2)
if sr1==m: tip=0
else: tip=1
prod={0: m, 1: sr1, 2: sr2, 3: tip, 4: i}
a.append(prod); i+=1
a = sorted(a, key=lambda x: x[0])
k=len([x for x in a[:-1] if x[3]==1])
print(a[len(a)-1][4],k)
Пример:
5
30 50
100 155
150 170
10 160
120 55
При таких исходных данных порядок расположения продуктов в рейтинге
следующий: 4, 1, 5, 2, 3. Последним займёт своё место в рейтинге продукт 3.
При этом один продукт
5 120 55, который займет в рейтинге более низкое место.
==>
3 1
4 10 160
1 30 50
5 120 55
2 100 155
3 150 170
27. Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле:
d(A,B) = √((x2 − x1)^2 + ( y2 − y1)^2) .
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px – минимальную из абсцисс центров кластеров и Py – минимальную из ординат центров кластеров.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 – расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 – максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров.
Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке – сначала
целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Возможные данные одного из файлов проиллюстрированы графиком.
y=9
from math import dist
def f_01( x, y ): # функция распределения по кластерам
if y<9: return 0
else: return 1
k = 2 # количество кластеров
klas = [ [] for i in range(k) ] #массив точек по кластерам
for s in open("DEMO_27_A.txt"):
x, y = map(float,s.replace(',','.').split())
klas[f_01(x,y)].append( (x, y) )
cent = [] # центроиды
for i in range(k):
mSd = float('inf') #мин. сум. рас. больше 10**18
for pC in klas[i]: # цикл по точкам - центрам
sumD = sum( dist(pC,p) for p in klas[i] )
if sumD < mSd:
mSd = sumD; cen = pC
cent.append( cen )
s0=[min(x) for x in zip(*cent)]
print( int(s0[0]*10000), int(s0[1]*10000))
#граф. изобр. распределения точек
from turtle import *
tracer(0); up()
hideturtle()
colors = ['red', 'green', 'blue', 'magenta']
scale, shiftX, shiftY = 25, 150, 150
for i, cluster in enumerate(klas):
for x, y in cluster:
goto( x*scale-shiftX, y*scale-shiftY )
dot( 3, colors[i] )
done()
Для файла А
Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px – минимальную из абсцисс центров кластеров и Py – минимальную из ординат центров кластеров.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 – расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 – максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров.
Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке – сначала
целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Возможные данные одного из файлов проиллюстрированы графиком.
y=27
y=19
y=11
x=19
аномалии
from math import dist
def f_01( x, y ): # функция распределения по кластерам (+1 аном.)
if x>19 and y<27: return 0
elif x<19 and y<27 and y>19: return 1
elif x<19 and y<19 and y>11: return 2
else: return 3
k = 3 # количество кластеров
klas = [ [] for i in range(k+1) ] #массив точек по кластерам (+1 аном.)
for s in open("DEMO_27_B.txt"):
x, y = map(float,s.replace(',','.').split())
klas[f_01(x,y)].append( (x, y) )
cent = [] # центроиды
for i in range(k):
mSd = float('inf') #мин. сум. рас.
for pC in klas[i]: # цикл по точкам – цент.
sumD = sum( dist(pC,p) for p in klas[i] )
if sumD < mSd:
mSd = sumD; cen = pC
cent.append( cen )
m1=0; m2=10**10
n1=-1; n2=-1 #номера клас. мак. мин. кол. точек
for i in range(k):
if len(klas[i])>m1: m1=len(klas[i]); n1=i
if len(klas[i])<m2: m2=len(klas[i]); n2=i
print( int(dist(cent[n1],cent[n2])*10000))
ms = 0 #мак. сум. рас.
for i in range(k):
td = max( dist(cent[i],p) for p in klas[i] )
if td > ms: ms = td
print(int(ms*10000))
Для файла Б
аномалии