larisavenzel
09.02.2023 11:34

какой алгоритм лучше с 1 цветным датчиком или двумя и ответь почему

Нажмите на рекламу ниже и сразу увидите ответ
Популярные вопросы:
Ответ:
Kirilloo673
24.04.2020 06:19
Сначала надо избавиться от ошибок (пункт №3)
иначе не сможем выполнить 1 и 2 пункт задания.
  Исправляем if N mod 10 k:=N mod 10; на if (N mod 10 < k) then k:=N mod 10;
  Исправляем N:N div 10; на N:= N div 10;
 
После исправления ошибок при вводе 537 получим 3
Программа будет работать правильно для любого числа,
у которого вторая цифра слева меньше первой цифры, например:
7193

Чтобы программа работала правильно для всех чисел надо
изменить это: while N > 10 do на while N > 0 do

После всех исправлений код программы стал таким:
var
  N, k: integer;
begin
  readln(N);
  k := 9;
  while N > 10 do
  begin
    if (N mod 10 < k) then k := N mod 10;
    N := N div 10;
  end;
  write(k)
end.
0,0(0 оценок)
Ответ:
SharagaXD
20.02.2023 09:01
Граф, изображенный на плоскости, называется плоским графом, если его ребра не пересекаются в точках, отличных от вершин графа. Заметим, что данное понятие касается только геометрического изображения графа, но не графа как множества вершин и связей. Часто один и тот же граф может быть изображён как плоский, так и как не плоский.

Важное практическое приложение плоских графов - прокладка коммуникаций между объектами при условии, что пересечение коммуникаций нежелательно.

Теперь об одном важном свойстве плоских графов. Сначала важное понятие. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Заметим, что часть плоскости, лежащая "вне" фигуры графа, также подходит под определение грани и считается гранью. При определении граней графа нужна осторожность - опасно пренебрегать выражением "не содержащая других циклов" в определении термина. Так, на рис. 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г. Алгоритм работает за линейное время.
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота