Задание 1. Анализ информационных моделей
Функции модуля itertools
Itertools — это Python-модуль, который предоставляет набор функций для работы с итерируемыми объектами. Итерируемый объект — это любой объект, предоставляющий возможность пройти по своим элементам, например список, кортеж и словарь. Itertools позволяет выполнять стандартные операции с итерируемыми объектами, такие как фильтрация, группировка и объединение.
Модуль Itertools предоставляет несколько функций, позволяющих манипулировать итерируемыми объектами. Рассмотрим подробнее наиболее полезные функции itertools.
1. permutations(): эта функция возвращает все возможные перестановки итерируемого объекта с уникальным расположением элементов в итераторе.
2. combinations(): эта функция возвращает все возможные комбинации элементов в итерируемом объекте, не повторяя в итераторе ни одной из комбинаций. Если указан опциональный аргумент r, будут возвращены только комбинации длины r.
3. product(): эта функция возвращает декартово произведение итерируемых объектов. Получаемый итератор содержит кортежи, каждый из которых формируется путем отбора по одному элементу из каждого итерируемого объекта. Если указан опциональный аргумент repeat, то входные итерируемые объекты повторяются указанное количество раз.
Функции библиотеки itertools возвращают не список, а итератор. Он не хранит все значения сразу, а позволяет один раз последовательно пройти по ним в цикле.
Для сохранения всех значений итератора его можно преобразовать в список с помощью функции list().
Строковый метод join() возвращает строку, объединяя все элементы итерации, разделенные разделителем строк. Метод в Python предоставляет гибкий способ создания строк из повторяемых объектов. Он объединяет каждый элемент итерируемого объекта (например, список, строку и кортеж) с помощью разделителя строк и возвращает объединенную строку.
from itertools import *
cmb = list(combinations('ABC', 2))
print(cmb)
# Результат: [('A', 'B'), ('A', 'C'), ('B', 'C')]
prm = list(permutations('DEF'))
print(prm)
# Результат: [('D','E','F'), ('D','F','E'), ('E','D','F'),
# ('E','F','D'), ('F','D','E'), ('F','E','D')]
prd = list(product('AC', repeat=2))
print(prd)
# Результат: [('A', 'A'), ('A', 'C'), ('C', 'A'), ('C', 'C')]
cm = product('ABC', repeat=2)
cm = list(map( "".join, cm ) )
print(cm)
# Результат: ['AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC']
cm = product('ABC', repeat=2)
for p in cm:
s = "".join(p)
print(s, end=' ')
# Результат: AA AB AC BA BB BC CA CB CC
[('A', 'B'), ('A', 'C'), ('B', 'C')]
[('D', 'E', 'F'), ('D', 'F', 'E'), ('E', 'D', 'F'), ('E', 'F', 'D'), ('F', 'D', 'E'), ('F', 'E', 'D')]
[('A', 'A'), ('A', 'C'), ('C', 'A'), ('C', 'C')]
['AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC']
AA AB AC BA BB BC CA CB CC
Решение задач
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.
46
Решение на Python:
from itertools import *
# Записываются ребра исходной таблицы
t = '13 15 17 23 24 31 32 34 36 37 42 43 46 51 57 63 64 67 71 73 75 76'
# Записываются ребра графа
g = 'аб ав ад ба бв вб ва вд вг ве гв ге гк да дв де ед ев ег ек ке кг'
# Записываются всевозможные перестановки вершин графа абвгдек
for per in permutations('абвгдек'):
new_g = t
for i in range(1, 8):
# Номера населенных пунктов 1234567 заменяются буквами абвгдек из перестановки,
# полученная строка сравнивается со строкой g, при совпадении выводится сопадение номеров пунктов и вершин графа
new_g = new_g.replace(str(i), per[i-1])
if set(g.split()) == set(new_g.split()):
print('1 2 3 4 5 6 7')
print(*per)
1 2 3 4 5 6 7
г б в а к д е
Вершине а графа соответствует пункт 4, а вершине д - 6. По исходной таблице определяем расстояние между пунктами 4 и 6, которое равно 46.
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите сумму протяженностей дорог из пункта B в пункт H и из пункта A в пункт Е. В ответе запишите целое число.
38
from itertools import *
t = '12 14 17 21 24 28 35 37 38 41 42 46 53 58 64 67 71 73 76 82 83 85'
g = 'ab ah ae ba bh ce cg cd dc df ea eg ec fh fg fd ge gc gf ha hb hf'
for p in permutations('abcdefgh'):
ng = t
for i in '12345678': ng = ng.replace(i, p[int(i)-1])
if set(g.split()) == set(ng.split()):
print('12345678')
print(''.join(p))№ 2564 (Уровень: Средний)
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина дороги ЗЕ равна 15 км. Определите длину дороги БГ. В ответе запишите целое число – длину дороги в километрах.
Ответ: 22
from itertools import *
t = '15 18 23 24 32 38 42 46 48 51 57 64 67 68 75 76 78 81 83 84 86 87'
g = 'ав ае бж бг ва вд гд гб де дз дж дв дг еа ед ез жз жд жб зе зж зд'
for per in permutations('абвгдежз'):
new_g = t
#print(new_g, per)
for i in range(1, 9):
new_g = new_g.replace(str(i), per[i - 1])
#print(new_g)
if set(g.split()) == set(new_g.split()):
print('1 2 3 4 5 6 7 8')
print(*per)
Решение
1 2 3 4 5 6 7 8
в б г ж а з е д
1 2 3 4 5 6 7 8
г а в е б з ж д
В первом варианте длина дороги ЗЕ равна 17, не удовлетворяет условию, решение задачи дает второй вариант
№ 1234 Статград 26.04.2021 (Уровень: Сложный)
На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе.
Известно, что длина дороги ГЕ больше, чем длина дороги ГЖ. Определите длину дороги БВ. В ответе запишите целое число - длину дороги в километрах.
Ответ: 29
from itertools import *
t = '14 15 17 23 25 28 32 34 35 38 41 43 46 47 51 52 53 64 67 68 71 74 76 82 83 86'
g = 'аб аг ае ба бв бд вб вд ви га гд гж ге дг дб дв ди еа ег еж же жг жи иж ид ив'
for per in permutations('абвгдежи'):
new_g = t
#print(new_g, per)
for i in range(1, 9):
new_g = new_g.replace(str(i), per[i - 1])
#print(new_g)
if set(g.split()) == set(new_g.split()):
print('1 2 3 4 5 6 7 8')
print(*per)
Решение
1 2 3 4 5 6 7 8 По условию: длина дороги ГЕ > ГЖ, г=4, е=7, ж=6. Тогда 17 > 20 Нет
а в д г б ж е и
1 2 3 4 5 6 7 8 По условию: длина дороги ГЕ > ГЖ, г=3, е=2, ж=8. Тогда 18 > 21 Нет
б е г д а и в ж
1 2 3 4 5 6 7 8 По условию: длина дороги ГЕ > ГЖ, г=4, е=7, ж=1. Тогда 17 > 14 Да
ж в д г и а е б Этот вариант определяет решение задачи, б=8, в=2. Длина дороги БВ равна 29
1 2 3 4 5 6 7 8
и е г д ж б в а
Домашнее задание
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите сумму протяженностей дорог из пункта A в пункт H и из пункта H в пункт C. В ответе запишите целое число.
37
(И. Карпачёв) На рисунке справа схема дорог Н-ского района изображена в виде графа, звёздочка в ячейке таблицы обозначает наличие дороги между двумя пунктами. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите длину дороги из пункта Д в пункт Е. В ответе запишите целое число.
9
На рисунке справа схема дорог N-ского района изображена в виде графа. В таблице слева есть сведения о протяжённости каждой из этих дорог (в километрах).
| Номер пункта | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||
| Номер пункта | |||||||||
| 1 | 21 | 15 | 27 | ||||||
| 2 | 25 | 21 | 22 | ||||||
| 3 | 18 | 11 | 10 | ||||||
| 4 | 21 | 20 | |||||||
| 5 | 15 | 25 | 18 | 23 | |||||
| 6 | 21 | 11 | 21 | 10 | |||||
| 7 | 10 | 20 | 21 | ||||||
| 8 | 27 | 22 | 23 | 10 | |||||
Таблицу и схему рисовали независимо друг от друга, поэтому нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма длин дорог из пункта A в пункт D и из пункта B в пункт H.
Ответ: 40
На рисунке справа схема дорог Н-ского района изображена в виде графа, а в таблице слева указаны длины каждой из этих дорог. Так как таблицу и схему рисовали независимо друг от друга, неизвестно, каким номерам населённых пунктов в таблице соответствуют буквенные обозначения на графе.
Определите сумму длин дорог РВ и СВ на схеме.
Скрыть
Ответ: 35
На рисунке справа изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Ж и В на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания. Например, если бы ответом были пункты П2 и П8, то в качестве ответа нужно было бы указать 28.
Ответ: 57
На рисунке слева схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт В, если известно, что длина дороги из А в И 13. В ответе запишите целое число — длину дороги в километрах.
Ответ: 15
Схема связей населённых пунктов изображена буквами на графе, а в таблице дано время пути по соответствующей дороге в минутах. Однако связь между буквами на графе и номерами в таблице не видна — её заполняли разные люди и не согласовали работу между собой.
Определите, за какое минимальное время можно добраться из населённого пункта Д в пункт Е в минутах. В ответе запишите только число.
Ответ: 75
На рисунке схема проходов между камерами в муравьиной ферме изображена в виде графа, в таблице содержатся сведения о длине этих проходов в сантиметрах. Однако связь между буквами на графе и номерами в таблице не видна — её заполняли разные люди и не согласовали работу между собой.
Известно, что длина прохода ДЕ отличается от длины ДИ на 6 см. Помогите муравью найти кратчайшее расстояние между камерами Б и Ж. Передвигаться можно только по указанным проходам.
Ответ: 24
Тестирование
Внимание. Прохождение теста доступно только один раз, результаты сохраните на свою электронную почту.