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
nakov avatar nakov SoftUni Team Trainer 5295 Точки
Best Answer

Колеги, извинявам се за неточностите в условията на някои от задачите.

  • На първата задача (Find the Root) имаше неточности в примерите и входните данни. Наложи се да прменим формата на входа. Задачата стана с граф. От входа се четат брой върхове (N), след това брой ребра (М), след това M насочени ребра. Трябва за всеки връх да се отбележи дали има предшественик (parent). Накрая се печата върха без parent или съобщения когато няма такъв или са няколко.
  • Поправихме примерите и картинките на втора задача (Round Dance), щото имаше неточности. Картинките и коментарите по тях бяха правилни, но входът беше грешен.
  • В примерния вход на задача 4 (Longest Path in a Tree) беше сгрешено едното ребро (пишеше "1 5", а трябва да е "5 1"). Поправихме го.

По другите задачи не сте откривали проблеми, нали?

Наков

2
01/08/2015 18:48:54
dim4o avatar dim4o 288 Точки

Да, даже може да се реши по много прост начин само с масив и цикъл. На мен не ми е ясно друго нещо по условието. Уж е дедено, че имаме дърво (connected directed tree), а от друга страна се иска обработка, когато нямаме корени - "No roots". Освен това по задание имаме N върха и N-1 ребра, което дори да е граф е с повече от една компонента на свързаност, т.е. това няма как да не е дърво - дори и да е изродено в списък. Някой сеща лис е за случай, когато няма корен?

0
krach avatar krach 65 Точки

Ами ако няма корен си е граф,макар че дървото си е граф така или иначе ако гледаме в тази посока. А в условието пише АКО няма корен, понеже със сегашната реализация на предното домашно за дърво (поне при мен) може да се получи така че дървото да стане без корен.

0
dim4o avatar dim4o 288 Точки

Да, така е. Можеш ли да дадеш пример за  такъв граф представен с формата на input-а от условието на задачата? Трябва да е с 2 компоненти на свързаност, но в никакъв случай не е дърво както е дано в условието. Странно е.

EDIT: Сетих се за такъв пример. Може би затова е дадена подобна задача - да се разгледа под друг ъгъл. Все пак дай такъв пример ако можеш. Примерите, за които се сещам всички са с 2 компонента на свързаност

0
24/07/2015 23:20:39
nakov avatar nakov SoftUni Team Trainer 5295 Точки

Колеги, обновил съм домашното:

  • Условията сега са по-ясни и разбираеми.
  • Добавил съм повече примери.
  • Подобрил съм изказа (включително по-грамотен английски).
  • Дал съм насоки (hints) за всяка задача.

Първата задача прилича на една вече давана, но не е съвсем същата. Има 3 случая: има root; няма root; има няколко root nodes.

Изтеглете си от сайта на курса последна версия на домашното.

Наков

3
25/07/2015 09:46:00
dim4o avatar dim4o 288 Точки

Сега условията са много по-ясни наистинa. Единствено на първа задача не разбирам защо последните два примера не се вързват с условието - The nodes have unique integer numbers between 0 and N inclusive (т.е. N+1 възела са дадени). T.e. за N=3 би трябвало да иамме 4 възела {0, 1, 2, 3} докато в примера са дадени 3 възела {0, 1, 2} . Излиза, че понякога може да имаме N + 1 възела, а в други случаи N.

0
25/07/2015 11:36:35
nakov avatar nakov SoftUni Team Trainer 5295 Точки
Трябва да се поправят половината примери...
1
26/07/2015 10:15:02
p.kanev avatar p.kanev 3 Точки

Във втора задача, ако приятелствата са двупосочни, отговорът на втория пример не трябва ли да е 4 (7->1->4->5)?

1
ivailozd avatar ivailozd 75 Точки

Ето моето домашно на Java ТУК

Липсва трета задача, защото не разбирам какво трабва да се направи. Може ли няякой да помогне с обяснение?

EDIT: Добавено е и решението на трета задача.

1
31/07/2015 14:19:01
dim4o avatar dim4o 288 Точки

По идея е абсолютно същата като Distance in Labyrinth в темата за листовете, но не ходиш в 4 посоки, а имаш достъп до най-много 8, както и до всяко поле на матрицата. Някрая просто отпечатваш средната колона по целочислено деление.

1
ivailozd avatar ivailozd 75 Точки

Ясно, "съседните", както пише в задачата, полета са въпросните 8.

Благодаря ти!

0
27/07/2015 10:26:19
dim4o avatar dim4o 288 Точки

Да, точно. 8-те по хода на коня.

2
dim4o avatar dim4o 288 Точки

Като цяло бяха много приятни и интересни задачите. Ето домашното ми. Първата задача съм я направил така, както я разбирам. Как може да има нормално дърво щом числата във възлите са от 0 до N (non-inclusive), т.е. N на брой и имаме N връзки? В нормалните дървета са N-1 ребрата. Предполагам това ще се разясни по-нататък, но засега съм се абстрахирал от примерите и съм гледал да изпълня максимално условието. На 4-та задача към края упътването ми се стори объркващо и направих нещо друго. Сортирането на 5-та зад. ми изглежда супер интересно, но като незадължителна реших да я оставя за ваканцията, че сега и без това няма никакво време.

1
Karlie avatar Karlie 438 Точки

Наистина първа задача е доста двусмислена. Твоят алгоритъм има малък пропуск в случая "Forest is not a tree". Ако въведеш например следния вход:

4
0 1
1 0
1 1
2 3

ще ти изкара 2 като root, а това всъщност са два графи (графа?).

Вчера се мъчих да я натъкмя доста дълго, и в крайна сметка я оставих за "някой друг път". Ще се радвам, ако някой, който го е измислил как да стане си сподели решението ;)

1
dim4o avatar dim4o 288 Точки

Благодаря за наблюдението. Това лесно може да бъде поправено като започнат да се търсят компонентите на свързаност, което едва ли е било идеята на тази задача. Просто не е доизмислена. Идеята да търсиш корен на дърво, което не е дърво е като да търсиш по черешово дърво банани или под краката на магарето корените му :) Затова не смятам да оправям този случай, въпреки че знам как да го направя.

1
mihayloff14 avatar mihayloff14 824 Точки

Относно последната задача - Sorting:

Някой има ли идея по какъв efficient начин да се пазят поредица от елементи?

Вчера се постарах и реших задачата, но определено решението е далеч от оптимално и на последния пример трябва да чакам 10 секунди докато изчисли случаите.

Това което правя аз, е когато ми трябва нова поредица правя нов масив и в него копирам всички елементи от старата, След това правя нужните reverse-вания и го пъхам някъде.

Има ли по-добри идеи?

0
dim4o avatar dim4o 288 Точки

Reverse-а и аз го решавам по подобен начин, но нямам проблем efficien за дадените примери. Може би забавянето не идва от в reverse-ванията. Ето решението ми: Sorting. Има още какво да се направи по него, възможно не всички ситуации да са обработени, но може да ти помогне да откриеш проблема. Ще е интересно да видя и твоето решение.

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

За последната задача със сортирането: можеш да пазиш поредица елементи като List<int>. За уникалността може да ползваш HashSet<string> и в него да слагаш поредицата във вид на стринг със запетайки, примерно "6,3,8,1". Така си гарантираш, че не повтаряш някои от поредиците.

Наков

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

@dim4o, гледам правиш нещо като хеш код и разчиташ той уникално да идентифицира поредицата. Това е хитро, но какво става ако имаме двуцифрени числа (N>=10). Може би да умножаваш по 100 и да пазиш резултата в 64-битов long?

Наков

1
pafkuneca avatar pafkuneca 14 Точки

Здравейте, искам да питам за първа задача какъв вход трябва да се подаде за да получим оутпут "Forest is not a tree".И ако може за 6 задача обяснение... не мога да разбера какво се иска от задачата.Благодаря предварително!

0
krach avatar krach 65 Точки

По условие на задачата след като подадеш броя на edges следващите N реда въвеждаш двойка числа, първото за родител, второто за дете. Ако подадеш примерно 6 за броя на нодовете, следващите 6 реда биха били примерно:
1 2
1 3
2 4
2 5
3 6
6 7
По този начин корен се явява 1. Понеже 2 и 3 са деца на 1. По същата логика 4 и 5 са цеда на 2. А 6 е дете на 3, както и че 6 е родител на 7. И в този ред на мисли от 7 (крайно листо) мога да стигна до корена 1, (7>6>3>1), нали на обратно също. В изложения пример всички имат родител БЕЗ корена 1.
Та за да получиш "Forest is not a tree, трябва такива данни да подадеш, така че да имаш две отделни дървета. Ако използвам горния пример би било следното:
6 - за броя на нодовете
1 2
3
2 4
2 5
3 6
6 7
По този начин се получават два нода, които нямат родител, 1 и 3.
Демек от крайното листо 7 мога да стигна само до 3 (неговия корен)

1
31/07/2015 15:35:55
pafkuneca avatar pafkuneca 14 Точки

Благодаря много!А за 6 имаш ли някаква идея, какво се желае, не съм доста добър с английския?

0
31/07/2015 19:10:37
pafkuneca avatar pafkuneca 14 Точки
Благодаря!!!
0
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
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.