|
Страници по тази тема: 1 | 2 | 3 | 4 | 5 | 6 | 7 | (покажи всички)
Тема
|
Забавление
|
|
Автор |
SvetilSfitil (Procul Profani!) |
Публикувано | 06.11.08 13:28 |
|
Я, какво ми е писал mlee:
Ако си тръгнал прост да се забавляваш :) предлагам ти да помислиш за два едносвързани списъка, които потенциално имат общ елемент(и).
И аз сега се чудя - как става тази работа!
Примерно, ако елемент от списъка ми е от следния клас:
struct MyNode
{
MY_TYPE data;
MyNode* pNext;
};
Освен да имат общ(и) последен елемент(и)...
Подозирам, че това е някаква задача за интервюта пак.
Хайде да поумуваме дружно, а!
Dum loquo hora fugitРедактирано от SvetilSfitil на 06.11.08 19:13.
| |
|
много не си спомням за структури от данни (отдавана бяха студенстките години), но помисли за случая когато имаш два списъка които имат обща част по между си
| |
|
Правилно, това е класическият случай когато ти си правиш сам списъка, много е популярен за задачки и учебници. Ама на практика се ползват готовите имплементации (ако има такива). За всички тях е характерно, че един и същи обект (по-скоро пойнтер/рифрънс към него) може да участва ен пъти в един списък и дори едновременно в ка списъка.
| |
|
Още една задачка-закачка взета от тест в една не толкова велика фирма
Условие:
Двама играчи, маса с произволна /недефинирана/ форма и площ.
Всеки от играчите разполага с безброй абсолютно еднакви монети.
Играчите се редуват последователно поставяйки монета на масата. За коректно поставяне на монета се счита, ако тя не припокрива друга и геометричния й центъра е върху масата. Монетите могат да се поставят както ви хрумне (на ръб, на плоскост,.... не е дефиниран броя на възможните поставяния на монета). Играта свършва с победа за играча поставил последен монета на масата
Задачата: Да се намери стратегия при която първият играч винаги печели.
Редактирано от mlee на 06.11.08 15:49.
| |
|
Освен да имат общ(и) последен елемент(и)...
Точно така - последните им X (където Х >= 1) елемента на двата едносвързани списъка са едни и същи.
Елементарната имплементация е с точно m + n + 2 (където m - брой на елементите в единия списък, n - брой на елементите в другия списък) извиквания на GetNext и точно едно сравнение (използва се идеята, че ако последните елементи на двата списъка са различни значи двата списъка нямат нито един общ елемент). Интересно дали има още по-ефективен алгоритъм
-----
просто, брат ми, сам си правиш проблем...
| |
Тема
|
Re: Забавление
[re: mlee]
|
|
Автор |
Hekф (зъл прът) |
Публикувано | 06.11.08 17:29 |
|
Хм, ако масата не е със съфсем произволна форма - има елегантно решение за стратегия на първия играч. Уговорката е формата на масата да е симетрична спрямо една точка - огледално или ротационно. Тогава първия играч поставя своята монета така, че нейният център да лежи върху тази точка и след това поставя всички други монети симетрично на монетите, които поставя втория играч. Идеята е, че ако втория играч намери начин да постави още една монета на масата то и първия играч ще може да постави още една монета.
Ако формата на масата обаче наистина е абсолютно произволна - не знам.
-----
просто, брат ми, сам си правиш проблем...
| |
|
Мислех си за центъра на тежестта, но при произволна форма, може да не се падне върху масата ...
Dum loquo hora fugit
| |
|
Ако формата наистина е произволна (силно се надявам, че фсе пак е грешка ф условието) нещата стават мноооого дебели. Произволна форма, произволна площ, почти безкраен брой варианти за разполагане на монетите - не ми се мисли как се доказва, че след последния ход на първия играч на масата със сигурност няма да остане дори едно най-най-най-нюнюнчесто местенце за да се постави още една монета на ръб.
-----
просто, брат ми, сам си правиш проблем...
| |
|
Аз друго си мисля - възможно ли е да има такава маса, с такава форма, така щото да може първият да загуби. И нищо не измислям.
Dum loquo hora fugit
| |
|
То тук е разковничето!
Не е работата, от къде да започнеш, може би, а как да постъпиш, когато масата е почти запълнена и ти си на ход.
Ти си на ход и имаш място за малко повече от една монета - слагаш я изправена, като преграждаш празното място на две и другият е на ход. Той прави същото с неговата половина ...
Фактически, номерът е да разделиш пространството на две полупространства, май.
Dum loquo hora fugitРедактирано от SvetilSfitil на 06.11.08 19:23.
| |
|
Страници по тази тема: 1 | 2 | 3 | 4 | 5 | 6 | 7 | (покажи всички)
|
|
|