Студенты пришли на занятия в большую аудиторию и все сели на какие-то места первого ряда аудитории. пришедший преподаватель объявил, что сейчас состоится контрольная работа, и решил пересадить студентов так, чтобы никакие два студента не сидели на двух подряд идущих местах (чтобы между любыми двумя студентами всегда было как минимум одно свободное место). преподавателю пересадить минимальное число студентов, чтобы достичь нужного результата.входные данныесначала вводится натуральное число n — количество мест в первом ряду аудитории, а затем число k — количество студентов. далее в порядке возрастания перечислены номера мест, на которые студенты сели изначально (все места пронумерованы числами от 1 до n).1 ≤ k ≤ 1000, 2k–1 ≤ n ≤ 109.выходные данныевыведите одно число — минимальное количество студентов, которых придется пересадить.решение для n < = 15 будет набирать 30 , для n < = 1000 будет набирать 60 .
Важное практическое приложение плоских графов - прокладка коммуникаций между объектами при условии, что пересечение коммуникаций нежелательно.
Теперь об одном важном свойстве плоских графов. Сначала важное понятие. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Заметим, что часть плоскости, лежащая "вне" фигуры графа, также подходит под определение грани и считается гранью. При определении граней графа нужна осторожность - опасно пренебрегать выражением "не содержащая других циклов" в определении термина. Так, на рис. 2 область 2-4-3-5-2 не является гранью - она ограничена простым циклом, но сама содержит простой цикл 2-3-5-2.
Теперь собственно свойство. Пусть В - количество вершин в графе, Г - количество граней в плоском представлении графа, Р - количество рёбер в графе. Тогда получаем формулу Эйлера: В + Г - Р = 2 для связного графа. Для несвязного графа с K компонентами связности формула имеет вид В + Г - Р = K + 1. Подставьте в неё K=1 и сравните с предыдущей. Интересное совпадение, не правда ли?
Формула Эйлера для выпуклых многогранников
Также заметим, что формула Эйлера выполняется для выпуклых многогранников. И это не случайно: выпуклый многогранник может быть представлен как плоский граф, если вершины и рёбра многогранника рассматривать как вершины и рёбра графа.
Теперь покажем это на деле: возьмём n-угольную пирамиду с выпуклым многоугольником в основании и "превратим" её в плоский граф (см. рис. 3). У пирамиды n+1 граней (основание и n боковых граней), n+1 вершин (n в основании и одна "обособленная") и 2n рёбер (n в основании и n соединяющих "обособленную" вершину" с остальными). Легко проверить - формула Эйлера тут работает.
Теперь разберёмся с плоским графом на рис. 3 справа. Аналогично несложно понять, что имеются n+1 вершин и 2n рёбер. Теперь разберёмся с гранями. Их опять n+1 (n граней-треугольников и "внешняя" грань вне фигуры). Снова формула Эйлера работает: n+1+n+1-2n=2.
Сейчас похожий фокус проделаем с n-угольной призмой. Имеем n+2 граней (два основания и n боковых граней), 2n вершин (по n вершин в каждом основании) и 3n рёбер (по n в каждом основании и ещё n соединяющих основания). Получаем B + Г - Р = 2.
Теперь разбираемся с графом. Количество вершин и рёбер считается легко. Граней снова n+2: "внутренний" n-угольник, n четырехугольников и "внешняя" грань. И снова формула Эйлера работает.
Планарные графы и проверка на планарность
Планарный граф - граф, который может быть изображён как плоский. Приведём пример планарного графа:
Не всякий граф является планарным графом. Согласно теореме Куратовского-Понтрягина (иногда её также называют теоремой Понтрягина-Куратовского, а иногда и вовсе опускают одну из фамилий), граф планарен тогда и только тогда, когда он не содержит подграфов типов, приведённых на рис. 6.
На основе теоремы Куратовского-Понтрягина очень просто получить один примечательный вид непланарных графов. Поскольку полный граф с 5 вершинами непланарен, а полный граф с n>5 вершинами содержит такой подграф, то верно следующее. Полный граф с n>4 вершинами обязательно непланарен.
На первый взгляд кажется, что всё просто - у нас лишь два типа "вредных" подграфов. На самом же деле задача анализа большого графа на наличие таких подграфов весьма непроста. Одним из алгоритмов, проверяющих, планарен ли граф, является алгоритм, разработанный в 1970г. Хопкрофтом и Тарьяном и улучшенный ими в 1974г. Алгоритм работает за линейное время.
1) Какой ответ будет выведен после выполнения цикла:
for x := 1 to 8 do Подставляем Х от 1 до 8
if x mod 7 = 0 Подставляем сюда Х=1 1 mod 7=0 нет так как mod это остаток от деления 1 mod 7 = 1 условие ложно и следующая строчка работать не будет, значит единственный Х который нам подходит это 7
7 mod 7 = 0 Да
then x := x + 1; Х:=7+1 X:=8
ответ: 8
2) Какой ответ будет выведен после выполнения цикла:
S := 0;
for x := 1 to 10 do
if x mod 3 = 0 Тут у нас снова mod и нам подходят только числа 3,6,9
так как они при делении на 3 дают остаток 0
3 mod 3 = 0 да
6 mod 3 = 0 да
9 mod 3 = 0 да
then S := S + x;
S:=0+3 S:=3
S:=3+6 S:=9
S:=9+9 S:=18
ответ: 18
Объяснение: