Algorytm - problem z zadaniem

0

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?
algo.png

2
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.

1

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
0

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

0
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

0

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

0

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

2

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

0

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

0

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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0