Informatyka UJ forum

peter_89

Witam,
postanowiłem poprosić Was o pomoc, jeśli dałem posta w złym miejscu to przepraszam. :wink:

Problem jest następujący:

Jest n-patyków które trzeba podzielić na k części w taki sposób by:
1) każdy patyk był równy
2) miał maksymalną możliwą długość

np. 3 patyki o długości 4, 3, 2 gdy dzielimy na 5 części to maksymalna możliwa długość wynosi 1,5.

Będę bardzo wdzięczny za każdą możliwą pomoc :D
Pozdrawiam

Madras

Nie rozumiem tego zadania...
Ale dopiero się obudziłem...
Spróbuję ponownie za godzinę.

Rogal

Proponuję wyszukiwać tą możliwą długość binarnie.

smas

na pierwszy rzut oka binsearch() załatwia sprawę + sytuacje wyjątkowe, np. gdy patyka najmniejszego w ogóle nie trzeba dzielić.

Madras

Nadal nie rozumiem, ale skoro Rogal mówi binsearch, to pewnie binsearch.

Fidel

nigdy wiecej zadan z asd :P

smas

Madras

A no to teraz rozumiem, k równych części != każdy patyk jest równy ; ].

Skrobocik

Tak jest, binSearch między najmniejszym patykiem, a zerem ;)

edit: między min{ (suma / oczekiwana ilość) , najkrótszy_patyk }, a zerem ;)

peter_89

Rogal

Hmmm to może napiszę algorytm w pseudojęzyku... acz robię to tylko dlatego, że jesteś uprzejmy :wink:

Założmy, że patyki mamy dane w tablicy tab[0..n-1], gdzie n to ilość patyków. Ilość równych części które chcemy uzyskać oznaczę przez k.
Będzie potrzebna funkcja pomocnicza:

Skrobocik

Aha, no tak, czyli jedyna zmiana, to to, że nie liczysz tego minimum, tylko od razu szukasz między (suma / oczekiwana_ilość) a zerem. Bierzesz środek z tych wartości i łamiesz wszystkie patyki, zaczynając od najdłuższych, na maksymalną ilość możliwych części o długości tego środka. Jeśli wyjdzie Ci więcej części niż jest oczekiwane, to trzeba szukać znowu w połowie między tym środkiem, co sprawdzałeś, a (suma/oczekiwana_ilość) (tutaj można spróbować dzielić patyki na większe części), a jeśli wyjdzie za mało części, to szukasz między tym środkiem a zerem (musisz dzielić na mniejsze, bo nie stracza długości z patyków, żeby podzielić). Jeśli wychodzi więcej niż trzeba, to zapamiętuj w dodatkowej zmiennej tę długość złamania i aktualizuj ją za każdym razem, jak znajdziesz lepiej pasujące złamanie.... no i tyle ;)

peter_89

Wielkie dzięki za pomoc. :D

Mam jeszcze jedno pytanie. Jest jakiś algorytm odpowiadający za połączenie kilku miast w taki sposób by każde było połączone (niekoniecznie bezpośrednio) by koszty podróży były jak najmniejsze. Kombinowałem coś z algorytmem Dijkstry ale nie wiem jak go przerobić do obliczania połączeń tzn. on może znaleźć np. najkrótszą drogę z A do D i nie wiem co z tym dalej.

np. w takim połączeniu:

A B C D
A 0 1 2 0
B 1 0 0 3
C 2 0 0 1
D 0 3 1 0

jest to:
A-B 1
C-D 1
A-C 2

Proszę bardzo o jakąś wskazówkę jak się za to zabrać.

PS: Rogal jesteś Wielki.

Pozdrawiam,

Madras

On to wie ; ].
A problem o który pytasz, to [link widoczny dla zalogowanych]
Zakładając, że pisząc "koszty podróży" masz na myśli sumę wszystkich użytych ścieżek.

hansu

Mozesz to jakos sprecyzowac? Co masz dane i co chcesz znalezc? Bo szczerze mowiac tak troche enigmatycznie to napisales, ciezko wywnioskowac o co konkretnie chodzi w problemie...

peter_89

Skrobocik

Jeden ze sposobów (algorytm Kruskala):
Posortuj wszystkie krawędzie rosnąco względem długości/wagi, czy czego tam masz i zaczynasz od pierwszej - najmniejszej.Masz tutaj zbiory (tu trzeba sobie już jakoś obsłużyć te zbiory, polecam pomocniczą tablicę, w której w n-tej komórce trzymamy numer zbioru, do którego należy n-ty wierzchołek - w trakcie tworzenia może być sporo tych zbiorów, na początku = |V|, więc jakoś trzeba sobie poradzić ;) ) i zaczynasz jazdę: na początku wszystkim wierzchołkom dajesz siebie jako numer zbioru, do którego należą, czyli coś w stylu:

Madras

Implementowali ten algorytm chyba wszyscy z tego roku, powiedz tylko, do czego Ci to potrzebne?

Rogal

Najprościej to zrobić to taką Dijkstrą. Masz kolejkę priorytetową Q, tablicę visited[0..n-1] (n = liczba wierzchołków) inicjalizowaną na false i jakoś implementowany graf (nie wnikam jak :D )
W każdym razie pseudokod może wyglądać tak

Robson

moze sobie chyba pozwolic na kolejke o czasie O(n) (zwykłe szukanie liniowe) skoro ma implementacje macierzową grafu...