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

Сподели тази публикация:

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

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

Сподели тази публикация:

3 мнения за “Минимален брой пресичания”

  1. BORIME4KA, мисля, че за нечетните не е така, разчертах го за 5, 7 и 9 случая и излиза, че при n пияча оптималният брой наздравици е точно n. Виж във форума.

    < << Иван Давидов >>>

  2. Прав си, Ванка… Абсолютно си прав 🙂 Което означава, че за n души са нужни винаги n наздравици. Всъщност, идеята за решаване е много просто за всички нечетни случаи… свързват се два съседни елемента, след което се правят успоредни линии между останалите… Наистина е n, без значение дали програмистите са четен или нечетен брой 🙂

  3. Privet, Pesho! Kakto ti obeshtah, postvam tova, koeto ti kazah za broqt
    na vsichki takiva nazdravici, a imenno che broqt im (pri n choveka, pardon n programista) e n-to chislo na Katalan. Tova e ponezhe nazdravicite syvpadat s t.n. non-crossing partitions on the cyrcle. Za Catalan number – prosto napishete gornoto v google. No neshto poveche, poglednete v Enumerative Combinatorics II na Stanley, chapter 6 ima nad 300 nachina (ekwiwalentni razbira se)da se definira n-to Katalanovo chislo. Tazi yadacha, kakto veche napisah, syvpada s the numbers of non-crossing partitions, koito meyhdu drugoto sa predstaveni ya pzrvi pzt v clasicheskata statiq na Kreweras, G.,. Sur les partitions non croisees d’un cycle.
    A, izpolyvam i da ti blagodarq ya programata, koqto napisa ya men, no neshto ne shte da se kompilira. Sigurno problemyt e w laptopa mi, a ne v tvoqt televiyor:).
    I oshte neshto, programata koqto napisha namira t.n. tilting modules in representation finite-hereditary algebra, Dynkin diagram E8. V sluchaq na A_n, broqt na tezi moduli e (Ta-tam) otnovo n-to chislo na Katalan, taka che broqt na nazdravicite i tilting modules An sa v biekciq! One never, never knows!
    P.S. Izvinqvam se za latinskoto pismo.
    P.S.S Tam kydeto dumite nqmat smisyl na bylgarski, napravete linejnata smqna y – z v tqh – otnovo problemyt e v (nemskta klaviatura na) laptopa mi. Pisha go za horata, koito pri vse che sa izcheli celiqt post, oshte ne sa se dosetili. I ne mi chetete „konsko“ za tova, ne sym kato „Karl Veliki, kojto e govorel na nemski samo s konete si“^1:)
    Pozdravi i umnata, a mozhe i rusata:)
    Nikolay D.

    1) Dimitrov, Georgi

Вашият коментар

Specify Facebook App ID and Secret in Super Socializer > Social Login section in admin panel for Facebook Login to work

Specify LinkedIn Client ID and Secret in Super Socializer > Social Login section in admin panel for LinkedIn Login to work

Specify GooglePlus Client ID and Secret in Super Socializer > Social Login section in admin panel for GooglePlus Login to work

Вашият имейл адрес няма да бъде публикуван.