Algorytm - problem z zadaniem

Cześć wszystkim. Mam takie oto zadanko do rozwiązania do piątku, ale nie mam pojęcia jak mogę je rozwiązać. Jakieś pomysly/sugestie/rozwiązania?

Druid33 napisał(a):

Jakieś pomysly/sugestie/rozwiązania?

Powiedz co już masz, czego nie rozumiesz, czego spróbowałeś, jaki miałeś tok myślenia. W tym momencie podanie jakiegoś rozwiązania to będzie wprost podanie gotowca, skoro wymagany jest jedynie opis.

Na początek możesz spróbować zdefiniować, jakie będzie to najprostsze rozwiązanie, dla którego masz znaleźć lepszą alternatywę - i je opisać. Podpowiem, że chodzi o rozwiązanie naiwne / brute force :) Zastanowiłbym się też, czy w celu opracowania lepszego algorytmu łatwiej będzie się pracowało z nieuporządkowanymi, czy też posortowanymi liczbami.

Rzeczywiście, sortując można zejść do złożoności kwadratowej, pseudokod:

fun three_sum(xs, n):
    sort(xs)
    limit = length(xs)
    for i = 0 to limit - 1:
        s = n - xs[i]
        ys = xs[0, ..., i - 1, i + 1, ...] # skip i-th element
        st = 0
        end = length(ys) -1
        while st < end:
            if ys[st] + ys[end] == s:
                return ys[st], ys[end], xs[i]
            else if ys[st] + ys[end] < s:
                st += 1
            else:
                end -= 1
    return NULL

Brute force odpada to za mały zakres danych do analizy.

Mariusz Bruniewski napisał(a):

Brute force odpada to za mały zakres danych do analizy.

No jak za mały?

Zadanie

• Masz ciąg P zawierający N liczb całkowitych dodatnich mniejszych niż X
• Znajdź taką trójkę liczb w P, która w wyniku da X

Rozwiązaniem naiwnym / brute force sprawdzasz wszystkie możliwe warianty, czyli iloczyn kartezjański P x P x P by sprawdzić wszystkie możliwe trójki. Nawet eliminując powtórzenia zostaje złożoność rzędu O(N^3) :P

Czy ciągi są odseparowane znakiem np "," , jaki jest najdłuższy ciag jeśli chodzi o separatory?
100, 21, 1000, 30, 2000, 7, 3

Co z sortowaniem przez zliczanie? Znamy zakres liczb, a będzie szybkie

Ale dalej będzie plus O(n^2), czyli całościowo też kwadrat.

Rozłóż liczbę na czynniki pierwsze. Jeśli liczba będzie miała 3 dzielniki. Określa to algorytm. Następnie szukaj ich w ciągu -1
43x47 = 2021

A jakby zrobić tak:
Najpierw stworzyć dodatkową tablicę o długości takiej jak tablica wyjściowa.
W każdym elemencie tej tablicy trzymać strukturę o polach sum (która będzie trzymać sumę) oraz tablicę na 3 liczby.

Czyli masz główną tablicę + tablicę trójek liczb wraz z sumą dla każdej trójki.

I potem przejeżdżasz przez liczby i dla każdej liczby jedziesz po dodatkowej tablicy (czyli O(n^2) ) i sprawdzasz, czy jest miejsce w danej trójce, jeśli tak to dodajesz liczbę do tablicy oraz zwiększasz sumę o tę liczbę. I teraz - jeśli w jakiejś tablicy sum == 2021, to znaczy, że mamy naszą trójkę.

Choć nie wiem, czy to działa, tak mi się wymyśliło teraz na sucho, ale nie sprawdzałem. Ale myślę, że można by sprawdzić.

No i jeszcze modyfikacja Najpierw stworzyć dodatkową tablicę o długości takiej jak tablica wyjściowa. - to też można by przemyśleć, po co od razu tworzyć tablicę o długości n, lepiej niech ta tablica się powiększa dynamicznie, wtedy byłoby mniej iteracji po dodatkowej tablicy.

Lub zliczanie za pomocą kombinacji bez powtórzeń.

Jak mogę określić złożoność algorytmu, w którym biorę losową liczbę_1 <2021, następnie biorę liczbę_2 < (2021-liczba_1), a na koniec liczba_3 = (2021-liczba_1-liczba_2)?
Jak na razie wpadłem na tylko takie rozwiązanie

@Druid33 to ciekawe rozwiązanie. Najpierw posortować (żeby umożliwić wyszukiwanie binarne, które będzie wydajniejsze niż liniowe), a potem wymyślać sobie liczby i szukać kolejnych trójek w tablicy.

Tylko problem z tym jest taki, że to nie będzie przewidywalne, jeśli będzie ci się coś losować.

Mając posortowane dane¹ można szukać w O(n²) - iterując po wszystkich kombinacjach 2 liczb a i b i sprawdzając czy istnieje w tablicy taka liczba c, że 2021-a-b=c

¹Zakładając radix sort, albo inny pozwalający na szukanie w posortowanej tablicy w O(1)

Ogólnie sytuacja wygląda tak:
Wykładowca mocno wiekowy, najprawdopodobniej nie uzna zadnych funkcji(rozwiazywanie wszystkich problemow tylko jego sposobami, kreatywnosc to zlo), wiec wszystko trzeba wklepac recznie.
Jeśli będę chciał zrobić to sposobem, o którym napisałem wyżej, a wcześniej posortować tę tablicę, jaka to będzie złożoność.
Szczerze powiedziawszy jestem z algorytmow lewy, a od tego zadania zalezy stypendium :D

To tak, pseudokod, który podałem, (rozumiesz go? Czy objaśnić) ma złożoność: sortowanie + O(n^2), czyli O(n^2), (bo sortowanie będzie max nlogn)zewnętrzna pętla idzie n razy i wewnętrzna n, w sumie n * n; problem sumy trzech jest zamieniony na n * suma dwóch.

Możesz to zrobić w złożoności n * 2021, więc O(n) (Jeśli się mylę to bardzo proszę mnie poprawić :D), wystarczy użyć techniki programowania dynamicznego, i sprawdzać czy istnieje taka suma pośród tych liczb
http://kompendium.meetit.pl/kurs#dp1

Trzeba lekko zmodyfikować żeby było wiadomo ile liczb używamy żeby uzyskać tą sumę, jest tam także specjalny błąd w implementacji tego algorytmu (o którym wspominają na kursie) ale sam go znajdź :)

a + b + c = 2021, dla: a,b,c < 2021

zatem biorąc takie coś o razu mamy:
c = 2021 - a-b, co wystarczy, bo wymaga n^2 operacji - sprawdzamy teraz kolejne pary a i b z tym warunkiem.

liniowo pewnie też pójdzie... dynamicznie?

jakiś taki graf z trzema przejściami

2  -> 2 -> 2 - trzy identyczne kolumny x n
3 ...
..
334 -> do wszystkich innych!
2000 ...

przeliczamy to od tyłu, no i tam wyjdzie co potrzeba - na początku.

https://www.google.pl/amp/s/www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/amp/

Ograniczoność zbioru wartości raczej niewiele daje w kontekście złożoności obliczeniowej, bo i bez tego można wszystko wrzucić do hashmapy.