• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm dzielący odcinek na części

VPS Starter Arubacloud
0 głosów
631 wizyt
pytanie zadane 3 stycznia 2017 w C i C++ przez Akdx Początkujący (310 p.)

Hej, postaram się jak najkrócej opisać problem. Zaciekawił mnie i zastanawia mnie jak to rozwiązać. Otóż mamy podany zbiór X (elementy mogą się w nim powtarzać), a my mamy symulować cięcie odcinka na takie fragmenty, że ich sumy długości pojedynczo, potem parami obok siebie, potem trójkami itd. dają razem ten pierwszy zbiór X. Matematyka przy okazji mówi, że z tego powodu X=A(A+1)/2, jeśli chodzi o liczbę elementów. Na pewno brzmi to enigmatycznie, więc wyjaśnię przykładem:
zbiór X = {2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18}, odpowiedź brzmi (na przykład, bo może ich być więcej, ale wystarczy jedna): (3, 4, 2, 6, 3). Widać, że to dobra odpowiedź, bo utworzymy takie zbiory (dla pojedynczych sum, sum dwójkami, trójkami itd.: {3, 4, 2, 6, 3}, {7, 6, 8, 9}, {9, 12, 11}, {15,15}, {18} (nota bene ostatni element to zawsze długość odcinka).

Dla zbioru X={1, 2, 3} nasza kombinacja będzie dwuelementowa (równanie X=A(A+1)/2) i jest postaci po prostu (1, 2).

No i mam problem, jak zaimplementować takie wyszukiwanie poprawnej kombinacji? Nie chodzi mi o kod, tylko chciałbym wytłumaczenie samego postępowania. Z góry dzięki za pomoc, a w razie pytań i niejasności służę wyjaśnieniami. Liczę, że znajdzie tu się dobry człowiek, który rozumie problem. :D

3 odpowiedzi

0 głosów
odpowiedź 3 stycznia 2017 przez CzikaCarry Szeryf (75,340 p.)
No to zapisujesz ten zbiór X do tablicy, tworzysz jakiś bufor, aby sprawdzić sumy pojedyncze, dwójki, trójki itd, i po prostu iterujesz po tej tablicy.
komentarz 3 stycznia 2017 przez Akdx Początkujący (310 p.)
Nie do końca rozumiem, a w trakcie iteracji po tablicy kiedy rozwiązanie jest tworzone? Czy mówisz na razie o wstępnym znalezieniu odpowiednich liczb, a ich kolejność zostawić na później?
komentarz 3 stycznia 2017 przez CzikaCarry Szeryf (75,340 p.)

Czy mówisz na razie o wstępnym znalezieniu odpowiednich liczb, a ich kolejność zostawić na później?

Tak, właśnie to mam na myśli. 

komentarz 3 stycznia 2017 przez Akdx Początkujący (310 p.)
No dobra, a pytanie jak wybierać te liczby? Kilka początkowych często jest obowiązkowych i nie trzeba decydować, po prostu muszą być w wyniku, ale co z resztą, co do których nie mamy pewności, że mają się pojawić w odpowiedzi?
komentarz 3 stycznia 2017 przez CzikaCarry Szeryf (75,340 p.)
sprawdzasz po kolei wszystkie kombinacje. Aby to zoptymalizować możesz też odrzucić niektóre kombinacje prostymi unstrukcjami warunkowymi.
komentarz 3 stycznia 2017 przez Akdx Początkujący (310 p.)
Ja tu widzę jedynie taką optymalizację, że poszukiwanie można przerwać, gdy iterując po tablicy suma przekroczy długość odcinka (wartość ostatniego elementu zbioru X), przyspieszenia widzę podczas szukania odpowiedniej kolejności wynikowej kombinacji, ale gdy dopiero się wybiera elementy, to trudno mi zauważyć jeszcze jakieś warunki "ucinające" gałęzie rozwiązań.
0 głosów
odpowiedź 3 stycznia 2017 przez morele123 Gaduła (4,790 p.)
Pomyśl najpierw jak byś to sam chciał zrobić, co robisz żeby rozwiązać ten, problem jak masz zadanie taki zbiór znaleźć. Na początek wybierasz jakieś liczby. Ty wybrałeś akurat 3,4,2,6,3. Następnie dodajesz pary i sprawdzasz, czy ten drugi ciąg, który z nich wyjdzie będzie podzbiorem X. Następnie bierzesz trójki itd. No to pozostaje ci już tylko wykombinować jak masz wybierać liczby do sprawdzenia i jak w miarę optymalnie sprawdzać.

Z wybieraniem liczb, no to najprościej sprawdzać każdą możliwą parę, czyli jak masz ten zbiór X podany, to wybierasz jego pierwszy element i dodajesz do drugiego, następnie sprawdzasz czy otrzymasz element zbioru X, jak tak to wybierasz sobie kolejny element i dodajesz do poprzedniego jak należy do X, to analogicznie, a jak nie należy to szukasz innego jak innego już nie ma, to usuwasz poprzedni element i szukasz nowego i analogicznie.
komentarz 4 stycznia 2017 przez Akdx Początkujący (310 p.)
Chodzi o to, że nawet jeśli zbiór X zawiera się w tym większym, to nie ma jednej kombinacji, dla której powstaje zbiór X. Np. wszystkie elementy zbioru X powstają, ale tylko w wyniku zsumowania wyników dla dwóch kombinacji jednocześnie. Np. (czysto teoretycznie) X = {1,2,4,5}, a dla dwóch kombinacji są zbiory {1,2,3,4} i {1,2,3,5}, w tym zbiorze potencjalnych sum będą zatem elementy 1,2,3,4,5, a więc zawierające zbiór X, ale żadna kombinacja sama, pojedyncza, tego nie spełni. Może moje rozumowanie jest błędne i czegoś nie widzę, ale tak mi się wydaje.
komentarz 4 stycznia 2017 przez morele123 Gaduła (4,790 p.)
A jak uzyskasz zbiór 1,2,3,4 albo 1,2,3,5 ? Jeżeli 3 nie należy do X.

Po za tym, skąd te dwie sumy ? Jeżeli program wygeneruje ci ciąg trójelementowy a,b,c to a,b,c zawiera się w X , a+b , b+c - zawiera się w X , a+b+c - zawiera się w X. I jeśli są to wszystkie możliwe elementy zbiory X no to to jest twój ciąg.
komentarz 4 stycznia 2017 przez morele123 Gaduła (4,790 p.)
W sumie to ten twój algorytm to sprowadza się do znalezienia takich liczb a1,a2,a3 ... an , że elementy ciągu X będą takie jak elementy ciągu:

{ a1,a2,a3 .... , an , a1+a2, a2+a3, a3+a4 ... an-1 + an , a1+a2+a3 , a2+a3+a4 ... , an-2 , an-1,an }

O chodzi tu tylko o elementy, nie o ich kolejność.
komentarz 4 stycznia 2017 przez Akdx Początkujący (310 p.)
edycja 4 stycznia 2017 przez Akdx
No właśnie problem jest z tym, że np. dla kolejności
(1,3,2) mamy zbiór X = {1, 2, 3, 3, 4, 6},
a dla kolejności
(1,2,3) jest już zbiór X = {1, 2, 3, 3, 5, 6}, dla większych instancji te zbiory różnią się znacznie bardziej,
no i problem jest jak szybko sprawdzić, że uzyskane liczby potrafią odtworzyć zbiór X, można po prostu sprawdzić wszystkie możliwe kolejności, ale jeśli co chwilę będziemy natrafiać na potencjalnie dobre liczby (suma całego odcinka się zgadza), będzie to bardzo wolne.

Wezmę jeszcze jeden przykład i pokażę jak działa algorytm:
X = {1,2,3,7,8,8,10,15,16,18}
Wybieram 1 i 2, będą należeć do wyniku. Przy 3 nie ma pewności, więc na razie stopujemy. Oczywiście liczb, które mamy znaleźć są cztery, bo wtedy liczba sum dwójek, trójek itd. się zgadza, tak więc mamy już 1 i 2. Zostały pozostałe dwie do znalezienia. Wykorzystujemy to, że łączna suma tych czterech liczb wynosi 18 (ostatni element X), więc pozostała suma (bez 1 i 2) to 15. Dodatkowa optymalizacja: biorąc nawet najmniejszy możliwy element tj. 3, wtedy elementu 15 już nie możemy wziąć, bo będzie za duża suma, czyli przeszukiwanie ograniczamy do zbioru {3,7,8,8,10}. Teraz sprawdzamy dwójki z tego zbioru, jeśli suma nie jest równa 15, to od razu idziemy do następnej, no i tak dochodzimy do pary (7,8) (być może są jeszcze jakieś inne - tutaj nie, w ogólności pewnie tak). Czyli mamy liczby: 1, 2, 7, 8.
Tutaj jest właśnie zasadniczy problem: jak sprawdzić, że to poprawne liczby? Póki co wiemy, że ich suma wynosi 18. Tworzą one w tej kolejności zbiór X' i niestety łatwo zauważyć, że nie ma w nim 10 (2 i 8 nie są koło siebie), a w oryginalnym zbiorze X jest.
I dlatego wpadłem na pomysł, że tworzymy z tych znalezionych liczb zbiór wszystkich możliwych sum S (nie tylko pary obok siebie, tj. 1-2, 2-7, 7-8, ale też 1-7, 1-8 itp.) i jeśli zbiór X się zawiera w S, to być może mamy dobre liczby. Ale że ten większy zbiór S jest jakby złożeniem wszystkich zbiorów X' dla każdej możliwej permutacji, to nie ma pewności, że da się uzyskać oryginalny zbiór X wyłącznie jedną kombinacją (póki co nie mogę znaleźć przykładu na potwierdzenie, może jestem w błędzie?).
Po prostu chcę uniknąć sytuacji, że mam tysiące potencjalnie dobrych zestawów liczb, i dla każdego zestawu robię tysiące permutacji, żeby się upewnić. Muszę jakoś to ominąć.
komentarz 5 stycznia 2017 przez morele123 Gaduła (4,790 p.)
No tak jak mówiłem, to najprostszy sposób. Możesz spróbować, sprowadzić to do postaci macierzy i rozwiązać, czy coś w tym stylu, może będzie szybciej. No ale to już matematyka, jeżeli masz czas i chęci to możesz się w to pobawić.
0 głosów
odpowiedź 5 stycznia 2017 przez Akdx Początkujący (310 p.)
Może ktoś się dołączy do debaty jak to zrobić? :D

Podobne pytania

0 głosów
1 odpowiedź 764 wizyt
0 głosów
1 odpowiedź 247 wizyt
0 głosów
1 odpowiedź 178 wizyt

92,452 zapytań

141,262 odpowiedzi

319,080 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...