Данчо Колев, дами и господа!

От известно време насам се каня да ви представя Данчо Колев, a.k.a. бащата на Биляна. Данчо е роден в с. Бреница (…ааа, вино кара воденицааааа…), женен, с две хубави деца.
Понастоящем инж. Колев има две висши, живее в Пловдив, работи в БДЖ, все още е зодия „свиня-стрелец“, кара VW Passat и ползва WordPress за новосъздадения си блог…
Обича пътуванията по света и у нас, Формула-1, бъзикането на високи и не чак толкова високи технологии, плуване и ски, узо и уиски, сачове и салати, крем карамел и сладолед…
За да се запознаете по-подробно с блога на Данчо, предлагам ви три избрани поста:

H2O или O2H…

Ако химичната формула на водата е H2O, в Англия хората сигурно често казват „О2H“, съкратено от „Oh, too hot!“… Някой абсолютен гений, който не е чувал що е то смесител за вода е сложил в хотелската ми стая два чучура… Един студен и един горещ. Да, студената вода върши чудесна работа в едни случаи, горещата – в други… Но обяснете ми как да имам нормална, хладка вода?!

Минимален брой пресичания

Никола, мой колега и голям приятел от Пловдив ми написа една задача, която просто нямаше как да не приема като лично предизвикателство… Само описание на алгоритми не бях вкарвал в блога, ама ето че и за това дойде момента…

Задача: Група програмисти се събират и решават да се напият възможно най-бързо. Как да свърши наздравицата най-бързо, като се „чукнат“ всеки с всеки от присъстващите, със следните уточнения:
– всички порции наздравици се извършват едновременно;
– масата е окръжност, а феновете са точки по нея;
– наздравицата е отсечка между две точки, като по същото време не може да има друга такава отсечка, която да я пресича: няма преплитане на ръце;
– броя на точките (фенове) е n.

Всъщност, това е сериозен проблем, примерно при дизайн на платки, когато без късо съединение (нежелано пресичане) трябва да се определят броя нива на платката. Важно е да споменем, че един програмист може да извършва само една наздравица в даден момент (иначе задачата е тривиална, защото на първи етап всички програмисти се чукват с No. 1, после с No. 2 и така виждаме, че броят е n; ако свързваме всеки път съседните, т.е. при връзки 1-2, 1-3, 1-4, …, 1-n можем да създадем и връзки 2-3, 3-4, 4-5, 5-6, … ще си спестим една наздравица, така че броят е де факто n-1, което е оптималното решение).

И тъй, за другия случай:
Разцъках си решенията за n=4, 6, 8 (после ще обясня защо само на четните).

n=4

n=6 

n=8

От тук нататък правим следният анализ…
За всяко четно n е достатъчно да направим връзки без свободни елементи (всички възли са свързани) и по главния диагонал (остават по 2 несвързани възела).
Общият брой е винаги n и това решение е оптимално.
Когато имаме нечетен брой елементи, обаче, един елемент винаги остава свободен, за който трябва да изпълним тези комбинации. Тогава ще имаме n.(n-1) етапа на наздравица.
Накратко:

  • ако програмист може да вдигне наздравица с няколко програмиста едновременно: n-1
  • ако програмист може да вдигне наздравица само с един човек при четно n: n
  • ако програмист може да вдигне наздравица само с един човек при нечетно n: n.(n-1)