argon bulletin board
Факултети => Факултет по математика и информатика => Темата е започната от: Атанас Терзийски в 10.07.2006, 10:01:04
-
Хай фенове!
Ония ден на поредната бирена сбирка от няколко човека ни хрумна следната загадка: Как да свърши наздравицата най-бързо, като се "чукнат" всеки с всеки от присъстващите, със следните уточнения:
- всички порции наздравици се извършват едновременно;
- масата е окръжност, а феновете са точки по нея;
- наздравицата е отсечка между две точки, като по същото време не може да има друга такава отсечка, която да я пресича: няма преплитане на ръце;
- броя на точките (фенове) е n.
Всъщност аз помислих сериозно над това, но не успях да доведа решението до край, а може би и задачата да не е лека... знам ли :)
-
:), честно ли точно това ви хрумна :)?
-
Хаха :)
хрумването ми "дойде" когато се появиха колизии от кръстосани ръце, изчаквания и т.н. -- а бях жаден. Поста включва и част от разсъжденията ми, когато исках да реша задачата... та се наложи да я опроставам...
бе не е лека, нали :)
-
Пиячи: n
Ако n е нечетно: най-оптимален брой наздравици = n
Ако n е четно: най-оптимален брой наздравици = n - 1 (обаче с кръстоска)
Подробностите по описанието на алгоритъма оставям на Ники Вълчанов, който може да даде идея как евентуално да се премахне кръстоската при четен брой фенове на бира.
-
Ако пиячите са n, не може и наздравиците да са n, а повече по няква формула, която не мога да си измисля, но:
Ако имаме пиячи /// наздравеци то изглежда така:
1 /// 0
2 /// 2
3 /// 3
4 /// 6
5 /// 10
...
т.е. това са ръбовете в графа или свързване на всички точки (с всички) или просто броя на звъновете на чашите при чукането им :)
-
- всички порции наздравици се извършват едновременно;
Ако имаме 4 души, които са седнали на четирите ръба на един квадрат, то тогава:
1 --- 2
| |
4 --- 3
Наздравица 1: 1 с 2, 3 с 4
Наздравица 2: 1 с 3, 2 с 4 (преплитане)
Наздравица 3: 1 с 4, 2 с 3
-
А 2 и 4 ... и ... 1 и 3 няма ли да го направят?
-
Алгоритъмът е древногръцки, не помня кой точно го е измислил, но ето каква е идеята:
Върху една окръжност на равни разстояния пореждаме n на брой точки. Номерираме ги последователно от 1 до n.
Свързваме точка 1 с точка n. Свързваме всички останали точки така, че да са успоредни на първата линия, т.е. свързваме 2 с n - 1, 3 с n - 2, 4 с n - 3 и т.н.
Ето тук изникват двата подслучая с четните и нечетните:
Ако n е нечетно, тогава винаги остава една точка, която не може да се свърже с останалите. Тази точка "почива" в този рунд. При първия рунд (наздравица), тази точка е (n + 1) / 2.
Ако n е четно, тогава след първата стъпка имаме окръжност, нарязана от n / 2 на брой хорди, разположени успоредно една спрямо друга.
Дотук беше лесното!
При втория рунд (наздравица) свързваме (1 : n - 1), (2, n - 2), (3, n - 3) и т.н. Отново възникват двата подслучая:
Ако n e нечетно, тогава във втори рунд точка n почива. В следващите рундове свързваме първо (1 : n - 2), на следващия (1 : n - 3) и т.н., докато точка 1 не изреди всички останали точки. Гледаме колко рунда сме направили и това ни е броя на наздравиците - 1. Последната наздравица е тази, при която точка 1 почива и свързваме (2 : n), (3, n - 1)... По този начин общият брой наздравици е точно числото n.
Ако n е четно, тогава се случва същото, както и при горния случай, с тази разлика, че от втори рунд нататък винаги остават две точки, които не могат да се свържат успоредно спрямо останалите. Но ако и те се свържат, тогава следвайки последователните стъпки, описани по-горе, стигаме до извода, че при четно n броят на наздравиците е n - 1.
Ха наздраве! Който успее да оптимизира кръстоската при четен брой пиячи е гений! Или просто ще ходим да пием бира винаги в нечетен брой!
-
Ето ви решение...
http://psabev.blogspot.com/2006/07/blog-post_10.html#links
-
Фенове: Иван Давидов и BORIME4KA,
луди сте!! Супер яко, чесно -- много се накефих ;-) - имате по бира от мен при следващата ни среща - само се обадете като сте из района на ПУ...
-
BORIME4KA,
Мисля, че грешиш за нечетните: според мен броят на наздравиците не е n * (n - 1), ами си е точно n - нито повече, нито по-малко. Ако си харесаме дадена точка и при последователните наздравици я свързваме с все по-отдалечаващите се съседни точки, а останалите точки ги свързваме успоредно, тогава на (n - 1)-вата наздравица първоначалната точка ще се здрависа с всички останали. Остава само да направим още една итерация, при която да изключим първата тока, да свържем двете най-близки около нея и след това да прекараме всички останали линии успоредно на първата линия.
Пример:
n = 5
1) 1:5, 2:4, 3 почива
2) 1:4, 2:3, 5 почива
3) 1:3, 4:5, 2 почива
4) 1:2, 3:5, 4 почива
5) 2:5, 3:4, 1 почива
При всяка наздравица отсечките последователно образуват пълен граф => всеки се здрависва с всеки, така че ще си позволя да направя следната корекция:
* ако програмист може да вдигне наздравица с няколко програмиста едновременно: n-1
* ако програмист може да вдигне наздравица само с един човек при четно n: n
* ако програмист може да вдигне наздравица само с един човек при нечетно n: n(!)
Извод: При n на брой пиячи оптималният брой наздравици според гореспоменатите изисквания е n, независимо от броя им, при положение, че n >= 2.
-
Приема се :-)
ksx, само Ванката ще черпиш май...