Софтуерно Инженерство
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 5456 Точки
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 5456 Точки

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

  • Условията сега са по-ясни и разбираеми.
  • Добавил съм повече примери.
  • Подобрил съм изказа (включително по-грамотен английски).
  • Дал съм насоки (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 5456 Точки
Трябва да се поправят половината примери...
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 845 Точки

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

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

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

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

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

0
dim4o avatar dim4o 288 Точки

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

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

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

Наков

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

@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 4428 Точки

В 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 4428 Точки

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

0
dim4o avatar dim4o 288 Точки

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

1