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

Podzielność kombinacji sum ciągów

VPS Starter Arubacloud
+1 głos
250 wizyt
pytanie zadane 10 stycznia 2019 w C i C++ przez osek916 Nowicjusz (140 p.)
Witam. Mam problem z uproszczeniem następującego algorytmu. Mamy np. ciąg 5 liczb nie większych niż dzielnik:  1,4,3,2,1 przy dzielniku równym 5. Z tego robimy wszystkie możliwe kombinacje dodawania i odejmowania tych liczb np: 1+4+3+2+1, 1+4+3+2-1, 1+4+3-2-1 itd. Mamy sprawdzić czy jakikolwiek wynik będzie podzielny przez dzielnik, jeżeli tak to nie musimy sprawdzać dalej. Problem mam przy większych liczbach, bo mam to sprawdzić dla 10000 liczb czyli złożoność jest rzędu 2^9999 prób przy zwykłym sumowaniu i sprawdzaniu. Ktoś mi powiedział, że można to zamienić na złożoność: ilość liczb * dzielnik tylko nie wiem jak i siedzę nad tym trzeci dzień. Z góry dziękuję za odpowiedź.
komentarz 10 stycznia 2019 przez DragonCoder Nałogowiec (36,500 p.)
dzielnik to 10 000, czy maksymalny dzielnik to 10 000?
komentarz 10 stycznia 2019 przez Benek Szeryf (90,690 p.)

Opisz dokładniej problem, bo na razie z tego stwierdzenia:

Mamy np. ciąg 5 liczb nie większych niż dzielnik:  1,4,3,2,1 przy dzielniku równym 5. Z tego robimy wszystkie możliwe kombinacje dodawania i odejmowania tych liczb np: 1+4+3+2+1, 1+4+3+2-1, 1+4+3-2-1 itd. Mamy sprawdzić czy jakikolwiek wynik będzie podzielny przez dzielnik, jeżeli tak to nie musimy sprawdzać dalej.

wynika, że mogę zawsze wziąć ciąg samych jedynek, tj. 1 + 1 + 1 + 1 + 1, których suma jest zawsze podzielna przez dzielnik (w tym przypadku 5). I dalej sprawdzać nie muszę. Amen.

komentarz 10 stycznia 2019 przez osek916 Nowicjusz (140 p.)

@DragonCoder,

komentarz 10 stycznia 2019 przez osek916 Nowicjusz (140 p.)
Co do tego to doszedłem do wniosku, że mogę każdą liczbę podzielić przez dzielnik i brać pod uwagę tylko liczby różne od zera co skraca nam tablice. Np: przy liczbach 7,10 i dzielniku 5 nie interesuje mnie w ogóle 10, bo nie nie zmienia w podzielności a w 7 mogę wziąć modulo z 5 co daje mi 2 i zmniejsza skomplikowanie. Problem jest dla 10000 cyfr gdzie zwykłym algorytmem liczyłoby wszystkie sumy miliony lat.
komentarz 10 stycznia 2019 przez osek916 Nowicjusz (140 p.)

@DragonCoder, dzielnik jest od 2 do 100

 

1 odpowiedź

0 głosów
odpowiedź 10 stycznia 2019 przez mkornas Użytkownik (640 p.)
Rozwiązanie będzie zastosowanie algorytmu plecakowego z drobnymi modyfikacjami (opisany jest tu jeden przypadek jego wykorzystania, po więcej odsyłam do internetu)

Gwaizdki w nawiasach (*) oznaczają porady implementacyjne. Radzę je dopiero przeczytać po zrozumieniu działania algorytmu.

Rozwiązanie opiera się na programowaniu dynamicznym (tak jak i cały plecak). Będziemy patrzeć jakie reszty z dzielenia przez dzielnik możemy uzyskać po wybraniu jednej, dwóch, trzech  ... wszystkich liczb. W tym celu deklarujemy sobie tablicę dwuwymiarową o wielkości: liczba liczb w ciągu * dzielnik (*). Na początku ma ona same zera i będziemy wstawiać jedynki w miejsca do których możemy dojść wystawiając znaki między liczby w ciągu. Pierwszy wymiar będzie oznaczał którą liczbę w ciągu rozpatrujemy, a drugi sumę dotychczas wybranych liczb.

Na początku wstawiamy 1 w miejscu [0][0]. Nie wybierając żadnej liczby (pierwsze 0) możemy otrzymać resztę 0 (drugie 0). (Tego co właśnie napisałem nie trzeba pisać w kodzie, ma to jedynie pomóc w zrozumieniu algorytmu). Teraz bierzemy pierwszą liczbę. Niech ma ona wartość a. Nie możemy wstawić przed nią minusa, więc wstawiamy 1 w miejsce [1][a].

I teraz właściwa część algorytmu. Bierzemy po kolei liczby. Niech aktualnie rozpatrywana liczba będzie na b-tym miejscu w ciągu i ma wartość c. Żeby sprawdzić jakie wartości możemy uzyskać po dostawieniu tej liczby musimy przejść się po całym rzędzie [b-1][od 1 do k] (***) . Za każdym razem gdy znajdziemy (załóżmy że znalazłem w miejscu [b-1][d]) to możemy wstawić 1 w miejsca [b][d - c] oraz [b][d + c] (**) . Otrzymamy to po wystawieniu - i + przed rozpatrywaną liczbą do wcześniej otrzymanego ciągu.

Na końcu jeżeli w miejscu [n] [K] jest 1 to ciąg jest podzielny. Pamiętaj o czyszczeniu tablicy przed każdym testem.

 

Porady implementacyjne

Bez gwiazdki - warto zmodulować każdą liczbę ciągu przez dzielnik

(*) polecam powiększyć o 5 oba wymiary na wszelki wypadek, aby nie okazało się, że przypadkiem wyjdziemy poza tablicę

(**) WAŻNE - może się okazać, że d - c < 0 lub d+c>k. Wtedy trzeba zmodulować przez k. Niestety w c++ modulowanie liczb ujemnych nie działa tak jak w matematyce dlatego przed zmodulowaniem d-c trzeba dodać dzielnik.

(***) możesz rozpatrywać przedział od 1 do k lub od 0 do k-1, nie ma to w zasadzie znaczenia. Pamiętaj tylko aby w dobrym miejscu sprawdzić wynik.

PS: zadanie można zrobić w mniejszej złożoności pamięciowej, ale wolałem opisać prostszą wersję

Podobne pytania

0 głosów
1 odpowiedź 1,514 wizyt
pytanie zadane 6 lutego 2020 w C i C++ przez bagietka_ Nowicjusz (120 p.)
0 głosów
1 odpowiedź 1,043 wizyt
pytanie zadane 29 października 2019 w C i C++ przez Hubertius Bywalec (2,970 p.)
0 głosów
2 odpowiedzi 5,610 wizyt
pytanie zadane 9 lutego 2016 w C i C++ przez sadurszczak Nowicjusz (150 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 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!

...