Я, какво ми е писал mlee:
Ако си тръгнал прост да се забавляваш :) предлагам ти да помислиш за два едносвързани списъка, които потенциално имат общ елемент(и).

И аз сега се чудя - как става тази работа!
Примерно, ако елемент от списъка ми е от следния клас:

struct MyNode
{
MY_TYPE data;
MyNode* pNext;
};

Освен да имат общ(и) последен елемент(и)...
Подозирам, че това е някаква задача за интервюта пак.
Хайде да поумуваме дружно, а!

Съдържаниет е скрито
Влезте за да го видите

Редактирано от SvetilSfitil на 06.11.08 19:13.

много не си спомням за структури от данни (отдавана бяха студенстките години), но помисли за случая когато имаш два списъка които имат обща част по между си

Правилно, това е класическият случай когато ти си правиш сам списъка, много е популярен за задачки и учебници. Ама на практика се ползват готовите имплементации (ако има такива). За всички тях е характерно, че един и същи обект (по-скоро пойнтер/рифрънс към него) може да участва ен пъти в един списък и дори едновременно в ка списъка.

Още една задачка-закачка взета от тест в една не толкова велика фирма

Условие:
Двама играчи, маса с произволна /недефинирана/ форма и площ.
Всеки от играчите разполага с безброй абсолютно еднакви монети.
Играчите се редуват последователно поставяйки монета на масата. За коректно поставяне на монета се счита, ако тя не припокрива друга и геометричния й центъра е върху масата. Монетите могат да се поставят както ви хрумне (на ръб, на плоскост,.... не е дефиниран броя на възможните поставяния на монета). Играта свършва с победа за играча поставил последен монета на масата

Задачата: Да се намери стратегия при която първият играч винаги печели.

Съдържаниет е скрито
Влезте за да го видите

Съдържаниет е скрито
Влезте за да го видите

Редактирано от mlee на 06.11.08 15:49.

Освен да имат общ(и) последен елемент(и)...
Точно така - последните им X (където Х >= 1) елемента на двата едносвързани списъка са едни и същи.

Елементарната имплементация е с точно m + n + 2 (където m - брой на елементите в единия списък, n - брой на елементите в другия списък) извиквания на GetNext и точно едно сравнение (използва се идеята, че ако последните елементи на двата списъка са различни значи двата списъка нямат нито един общ елемент). Интересно дали има още по-ефективен алгоритъм

-----
просто, брат ми, сам си правиш проблем...

Хм, ако масата не е със съфсем произволна форма - има елегантно решение за стратегия на първия играч. Уговорката е формата на масата да е симетрична спрямо една точка - огледално или ротационно. Тогава първия играч поставя своята монета така, че нейният център да лежи върху тази точка и след това поставя всички други монети симетрично на монетите, които поставя втория играч. Идеята е, че ако втория играч намери начин да постави още една монета на масата то и първия играч ще може да постави още една монета.

Ако формата на масата обаче наистина е абсолютно произволна - не знам.

-----
просто, брат ми, сам си правиш проблем...

Мислех си за центъра на тежестта, но при произволна форма, може да не се падне върху масата ...

Dum loquo hora fugit

Ако формата наистина е произволна (силно се надявам, че фсе пак е грешка ф условието) нещата стават мноооого дебели. Произволна форма, произволна площ, почти безкраен брой варианти за разполагане на монетите - не ми се мисли как се доказва, че след последния ход на първия играч на масата със сигурност няма да остане дори едно най-най-най-нюнюнчесто местенце за да се постави още една монета на ръб.

-----
просто, брат ми, сам си правиш проблем...

Аз друго си мисля - възможно ли е да има такава маса, с такава форма, така щото да може първият да загуби. И нищо не измислям.

Dum loquo hora fugit

То тук е разковничето!
Не е работата, от къде да започнеш, може би, а как да постъпиш, когато масата е почти запълнена и ти си на ход.
Ти си на ход и имаш място за малко повече от една монета - слагаш я изправена, като преграждаш празното място на две и другият е на ход. Той прави същото с неговата половина ...
Фактически, номерът е да разделиш пространството на две полупространства, май.

Dum loquo hora fugit

Редактирано от SvetilSfitil на 06.11.08 19:23.