Софтуерно Инженерство
Loading...
Simooo93 avatar Simooo93 81 Точки

[HOMEWORK] Advanced-Graph-Algorithms

Здравейте,

изглежда не мога да се ориентирам правилно за това как трябва да се четат входните данни от задачите. 

1. По първа задача всичко ми е ОК като изключим това, че в първия пример е дадено като отговор ребро "{3, 5} -> 2", а даденото във входните данни е "{5, 3}" и съответно аз принтирам "{5, 3} -> 2". Първоначално си помислих, че може би е свързано със мястото откъдето идваме: тоест тъй като 3-ката е вече в разширяващото дърво и придърпваме 5-цата от нея то и затова трябва да принтираме {3, 5}, но пък това не важи за 2-рия пример, където принтираме реброто така, както ни е дадено, а с логиката, която споменах. Ако някой може да помогне и да каже каква е логиката зад принтирането.

2. По втора задача аналогично имаме дадени ребра, някои от тях, които са принтирани на обратно във верния отговор. Пример: входни данни: ребро {3 1}; отговор: {1, 3}

3. На трета задача изобщо не хващам логиката относно процентите, които трябва да покажем. Очевидно не е средно аритметично, а и е дадена една табличка с проценти от 0 до 6, което пък избощо не разбирам как се пресмятат процентите вътре. Също така във втория пример е даден най-дълъг път до 1: 0-> 2 -> 3 -> 1. Но във входните данни няма път от 3 до 1.

Тагове:
0
Структури от данни и алгоритми 05/05/2016 16:21:43
a_rusenov avatar a_rusenov 1103 Точки

На първа и втора задача графът е неориентиран и няма значение как ще принтираш ребрата - дали ще е u - v или v - u е същото. Прав си обаче, че трябва да са консистентни примерите, затова ще ги оправим. :)

А на трета задача пресмятането на общия процент за първия пример е даден по формулата 88% * 99% * 98% * 95% * 100% = 81.11%. Относно втория пример - графът в тази задача също е неориентиран, следователно пътят от 1 до 3 е двупосочен. Визуално пътят 0 -> 2 -> 3 -> 1 изглежда по-дълъг, но тук се търси най-надеждният (с по-висок общ процент) и той е по-надежден от 0 -> 1.

2