Loading...
krach avatar krach 65 Точки

Homework: Tree and Graph Traversal

Интересно ми е защо се дава същата задача, както от предното домашно?

Конкретно за 1ва задача за намирането на root-a

Условие от последното домашно: Find the number of the root of the tree

Условие от предното домашно за дървета: Write a program to read the tree from the console and find:The root node

Тагове:
0
Структури от данни и алгоритми 24/07/2015 20:33:04
Filkolev avatar Filkolev 4482 Точки

В 4-та задача има грешка във входа - на 7-ми ред е дадено "1 5", което предполага, че 1 е родител на 5, а трябва да е обратното.

Също така не съм сигурен за какво е нужен първият ред. Не виждам за какво ни е да знаем колко елементи има в дървото, при положение, че тази информация 1) не се ползва (или аз поне не я ползвам), 2) може да се изведе от връзките между елементите ако се наложи. Някой намерил ли е приложение все пак на тази информация?

1
gale_st avatar gale_st 0 Точки

"1 5" означава, че има връзка между двата node-а

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

за първия ред и аз не съм сигурна, но попринцип в задачи се дават ограничения за това N и така знаеш колко памет ти трябва, дали ще имаш time limit и т.н.

0
31/07/2015 18:34:44
Filkolev avatar Filkolev 4482 Точки

Не би трябвало да е така, трябва ясно да е дефинирано кое е родител и кое дете, а във всички останали случаи във входните данни подредбата е правилна. В противен случай може всеки нод да разглеждаш като корен и няма да има начин да търсиш листата, понеже всеки нод ще има деца и родител; няма как да търсиш нодове без деца с тази дефиниция, защото такива просто няма.

0
dim4o avatar dim4o 288 Точки

И според мен е грешен входа. Ако беше така корена трябва да е 1, а не 5. Факт е, че решението може да работи и с този вход и да дава правилен изход, но определено не е коректно. Единствено не разбрах какво се очаква да направим по 1-ва задача. Там противоречията са много и няма как човек да си изгради единна теория за това как би могло да е коректното условие. Надявах се да се доизясни, но изглежда, че ще си остане така.

1
Filkolev avatar Filkolev 4482 Точки

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

При моето решение ще оставя програмата да връща отговор, че даденото е гора в последните два примера, дано оценяващите не се водят само по примерите.

0
nakov avatar nakov SoftUni Team Trainer 5295 Точки

Поправихме ребрато: 1 5 -> 5 1.

Ако връзките са двупосочни, задачата също може да се реши, но малко по-сложно.

Наков

0
MartinDachev avatar MartinDachev 30 Точки

Мисля, че има грешка и в насоките (hints) на 4-та задача. Ако разгледаме случая например когато най-дългият път по сума е от 1 листо до друго което му е sibling (имат общ родител) тогава решението с намирането на пътя до корена от всяко листо няма да работи. Никъде не пише че пътя трябва да минава задължително през корена. Ако съм разбрал правилно, то тогава решението се усложнява.

0
nakov avatar nakov SoftUni Team Trainer 5295 Точки
От телефона не мога лесно да проверя, но мисля, че тежестите са неотрицателни и следователно всеки най-дълъг път минава през корена. Наков
0
Filkolev avatar Filkolev 4482 Точки

Аз доколкото разбирам задачата (4-та) трябва да се разгледат сумите между две листа до първия им общ родител. Ако задължително трябва да се мине през корена това означава или 1) едни и същи нодове да участват в сумата ако вземем две листа от една и съща страна на корена (което според примера не е така), 2) да се вземе едно листо принадлежащо на левия наследник на корена и едно на десния.

Аз направих задачата като взимах сумите до първия общ родител, тъй като това е директният път между двете листа.

2
MartinDachev avatar MartinDachev 30 Точки

nakov, има дори в примера отрицателна стойност на нод. Дори и да няма отрицателни стойности, пак може 2 нода със общ "баща" да са с най-голяма сума. Тогава трябва да се мине по 1 и същи път 2 пъти както е казал Filkolev, за да мине през корена, в което и аз не намирам голяма логика.

Filkolev, да, и аз мисля, че трябва да е до общ родител, защото това е пътя от 1 листо до друго. Ако това се иска реално от задачата, трябва да се поправят hint-овете, защото виждам повечето са го направили както е указано в тях. А е добре и още един пример да се добави, който не минава през корена ;).

0
03/08/2015 18:39:49
nakov avatar nakov SoftUni Team Trainer 5295 Точки
Да, до общ родител, сгрешено е в хинта. Не мога да го оправя от телефона.
1
nakov avatar nakov SoftUni Team Trainer 5295 Точки

Оправих hint-а на задачата "Problem 4. Longest Path in a Tree". Идеята е за всяка двойка върхове да се намери пътя между тях и от всички такива пътища да се избере най-голямата сума.

За да се оптимизира пресмятането на сумата за пътя между двойка върхове да става със сложност O(1) и съответно цялата задача да се реши със сложност O(N*N), се смята пътя от всеки връх до корена + малко сметки за да се сметне пътя между всяка двойка върхове.

Имаше грешка в hints: пишеше, че всеки път трябва да минава през корена, но не е така.

Наков

1
MartinDachev avatar MartinDachev 30 Точки

Благодаря :)

А какъв начин използвате за изчлисляване на "nearest common parent" ​и най-вече каква е сложността на алгоритъма (питам тези, които са решили задачата с път през най-близкия общ родител).

0
05/08/2015 12:38:33
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.