Новинарски форум

Домашно No.2

Домашно No.2

by Габриела Цанова -
Number of replies: 6
"Правилен критерий е: графът да е ацикличен, всички възли да имат поне един родител и да има точно един възел без родители" - даже това е малко грешно.
  1. Един връх трябва да има не повече от един родител - иначе ще получим повече от едно входни ребра за някой от върховете.
  2. Трябва да има единствен връх, който няма родители - иначе ще получим гора.
  3. Графът трябва да е ацикличен.
  4. **Всеки връх трябва да има не повече от два наследника - в противен случай ще получим не двоично, а напълно произволно дърво.
In reply to Габриела Цанова

Re: Домашно No.2

by Тихомира Славова -
Ако ти е направило впечатление, условието е "Да се напише функция, която проверява дали даден ориентиран граф е дърво."
Така че критериите са си напълно в нормата. Вече в isBinTree се прави допълнителната проверка дали е точно двоично дърво, а не някое произволно.
Разбира се, никой не е казал, че не можеш да го напишеш в една функция, която едновременно проверява дали графът е дърво и ако да, дали е двоично.
Въпрос на личен избор.
In reply to Тихомира Славова

Re: Домашно No.2

by Габриела Цанова -
Цитирам условието:
"Да се напише функция
BinTree<int> toBinTree (IntGraph& g)
която проверява дали един ориентиран граф може да се разглежда като двоично дърво и ако може, построява това дърво. "

Все пак, в случая не това е водещото.
В критериите, които бяха качени, дори без този, който добавих, ако ги прочетеш много внимателно, ще откриеш, че е допусната малка грешка, отнасяща се до броя на родителите - просто не може дърво да има връх, който има повече от един родител.
In reply to Габриела Цанова

Re: Домашно No.2

by Тихомира Славова -
Ох, защо се захванах. Хайде и аз да цитирам:

Графи
  1. Да се напише функция, която проверява дали граф, зададен със списък от насленици е ориентиран или неориентиран, т.е. дали за всяка дъга имаме обратна дъга.
  2. Да се напише функция, която проверява дали даден ориентиран граф е дърво. Примери за непълни критерии:
  • графът да е ацикличен (може да имаме 1 -> 2, 2 -> 3, 1-> 3)
  • всички възли да имат поне един родител (може да имаме цикъл)
  • всички възли да имат поне един родител и да има възел без родители (може да имаме гора)
  • всички възли да имат поне един родител и да има точно един възел без родители (може да имаме 1 -> 2, 3 -> 4, 4 -> 3)
Правилен критерий е: графът да е ацикличен, всички възли да имат поне един родител и да има точно един възел без родители


Та, ако още не е ясно, критикуваш условията на допълнителните задачки, които ще ти помогнат да решиш самото домашно. И които са писани на упражнения, явно не си присъствала на тях. Не знам за теб, но според мен е по-лесно да се направи проверка дали дадено дърво е двоично, след като вече сме проверили, че наистина става дума за дърво. Освен това никъде не пише, че трябва някой от върховете да има повече от два родителя, точно обратното. Прочети си всичко внимателно и ще разбереш, че съм права.
In reply to Тихомира Славова

Re: Домашно No.2

by Габриела Цанова -
Според теб в едно дърво може ли да има връх, с повече от един родител?
Критикувам едно единствено условие - това за броя на родителите.

"всички възли да имат поне един родител" <=> "един или повече"

Не пише, че трябва, но не пише и точно обратното.
Чета внимателно и затова обръщам внимание на тези неща.
И понеже това вече се превръща в абсолютно безмислен спор, ще спра с коментарите.

A little hint:

1->2;
1->3;
2->4;
3->4;

Няма цикли. Има точно един връх без родители. Всеки друг връх има поне един родител.

Enjoy! (:
Attachment graph.png
In reply to Габриела Цанова

Re: Домашно No.2

by Тихомира Славова -
Ясно ми е какво критикуваш, също така ми е ясно, че в момента се хващаш за една дума. Първият ми отговор беше относно 4**, за да обясня, че проверката за броя наследници нарочно е пропусната във въпросното условие. А ти задълба в друга посока.
Аз приключвам въпроса.
In reply to Габриела Цанова

Re: Домашно No.2

by Трифон Трифонов -
Права си, думата "поне" трябва да се замени с "най-много" в целия текст. Благодаря за поправката, нанесох я в текста.