Algorytm MIN=MAX

0

Już 2 tydzień siedzę nad tym zadaniem, ale nie mogę wszystkiego ogarnąć. Treść zagadnienia:
"Proszę napisać funkcję, która dla tablicy jednowymiarowej o rozmiarze n, wyznacza
punkt podziału tej tablice na dwie podtablice spełniające własność: minimalna
wartość lewej podtablicy ( od indeksu 0 do indeksu k ) jest równa maksymalnej
wartości prawej podtablicy( tej od indeksu k+1 do n-1). Jeśli istnieje taki podział,
funkcja zwraca punkt podziału (indeks k). W przeciwnym przypadku zwraca
wartość –1.
0 1 2 3 4 5 6 7
Np. dla tablicy A={5, 4, 6 7, | 3,-4, 4,0 } takim punktem podziału jest indeks k=3.
Wartość minimalna lewej podtablicy od indeksu 0 do 3 wynosi 4. Maksymalna
wartość w prawej podtablicy od indeksu 4 do 7 wynosi również 4."

Proszę o pomocy. Wiem że trzeba(można) podzielić tablice na dwie podtablicy, i szukać min, max. A na koniec porównać ci 2 liczby, ale nie wiem jak to dokładniej napisać w kodzie?

1

Posortuj, poszukaj pierwszych dwóch powtarzających się elementów. Jak takie są, to pierwsza tablica jest od początku do pierwszego powtórzonego, a druga od drugiego powtórzonego do końca.

0
kq napisał(a):

Posortuj, poszukaj pierwszych dwóch powtarzających się elementów. Jak takie są, to pierwsza tablica jest od początku do pierwszego powtórzonego, a druga od drugiego powtórzonego do końca.

Dzieńki.

0
kq napisał(a):

Posortuj, poszukaj pierwszych dwóch powtarzających się elementów. Jak takie są, to pierwsza tablica jest od początku do pierwszego powtórzonego, a druga od drugiego powtórzonego do końca.

No chyba nie bardzo zgadza się z warunkami zadania.
Według Twojego algorytmu dla danych (1, 3, 4, 9, 9, 3, 2, 6, 7), zakładając, że miałeś na myśli sortowanie rosnące, dostajesz
(1, 3) oraz (3, 2, 6, 7)
Po pierwsze Twój podział nie wyczerpuje całej tablicy na wejściu, po drugie min(pierwsza) < max(druga).

0

Dla każdego k wyliczasz minimum prefiksu tablicy o długości k i maksimum sufiksu tablicy o długości n - k. Potem tylko iterujesz po tablicy i szukasz indeksu k, dla którego minimum prefiksu jest równe maksimum sufiksu. Złożoność czasowa liniowa, pamięciowa liniowa.

0

A teraz jeżeli można, jak dla 1 rocznika studiów? Czuli jak dla dziecka)

0

       A={5, 4, 6, 7, | 3, -4, 4,  0 }
 minA={5, 4, 4, 4,   3, -4, -4, -4 }
maxA={7, 7, 7, 4,   4,  4,  0,  -inf }
Tniemy tam, gdzie wartości są równe.

1
Afish napisał(a):

Dla każdego k wyliczasz minimum prefiksu tablicy o długości k i maksimum sufiksu tablicy o długości n - k. Potem tylko iterujesz po tablicy i szukasz indeksu k, dla którego minimum prefiksu jest równe maksimum sufiksu. Złożoność czasowa liniowa, pamięciowa liniowa.

Czy przypadkiem złożoność czasowa nie będzie n^2? W każdej iteracji szukanie min i max jest liniowe, a musimy je zrobić dla każdego k.

2

Może być i n^10, ale jak zaimplementujesz poprawnie, to będzie liniowa.

0
Afish napisał(a):

Może być i n^10, ale jak zaimplementujesz poprawnie, to będzie liniowa.

Żeby to było liniowe, to każda iteracja Twojego opisu "Dla każdego k wyliczasz ..." (a k jest zależne bezpośrednio od n) musiałaby odbywać się w stałym, niezależnym od n czasie.
Podaj przykład tej "poprawnej implementacji".

0
[enedil napisał(a)]

To jest proste do wykminienia, usiądź przez 5 minut nad tym, wyjdzie. Najprostszy algorytm zachłanny, jaki się da zrobić.

Widzę dwie opcje:

  1. Istnieje "prosty do wykminienia przez 5 minut" algorytm, który spełnia wcześniejsze założenia (dla każdego k ze zbioru [1..n-1] szuka max w podzbiorze (a[0],...,a[k]) i min w zbiorze (a[k+1], ..., a[n]) w liniowym czasie).
  2. Nie poświęciłeś 5 minut na proste do wykonania przeczytanie kilku zdań ze zrozumieniem.
0
costamcostam napisał(a):
[enedil napisał(a)]

To jest proste do wykminienia, usiądź przez 5 minut nad tym, wyjdzie. Najprostszy algorytm zachłanny, jaki się da zrobić.

Widzę dwie opcje:

  1. Istnieje "prosty do wykminienia przez 5 minut" algorytm, który spełnia wcześniejsze założenia (dla każdego k ze zbioru [1..n-1] szuka max w podzbiorze (a[0],...,a[k]) i min w zbiorze (a[k+1], ..., a[n]) w liniowym czasie).
  2. Nie poświęciłeś 5 minut na proste do wykonania przeczytanie kilku zdań ze zrozumieniem.

Opcja trzecia:
Istnieje "prosty do wykminienia przez 5 minut" algorytm, który spełnia wcześniejsze założenia (dla każdego k ze zbioru [1..n-1] szuka max w podzbiorze (a[0],...,a[k]) i min w zbiorze (a[k+1], ..., a[n]) w czasie stałym, gdzie operacją elementarną jest porównanie dwóch liczb).

0
enedil napisał(a):

Opcja trzecia:
Istnieje "prosty do wykminienia przez 5 minut" algorytm, który spełnia wcześniejsze założenia (dla każdego k ze zbioru [1..n-1] szuka max w podzbiorze (a[0],...,a[k]) i min w zbiorze (a[k+1], ..., a[n]) w czasie stałym, gdzie operacją elementarną jest porównanie dwóch liczb).

Pokaż to cudo, które wyszukuje w stałym czasie. Stałym, a więc niezależnym od rozmiaru danych wejściowych.

0
[enedil napisał(a)]

Tak, znam takie podstawy teorii złożoności, by wiedzieć co to znaczy "czas stały" - po to zaakcentowałem czym są operacje elementarne. Jednakże, zamiast próbując udowodnić mi, że nie potrafię, bo się nie da, spróbuj samemu wymyślić algorytm - będzie to dużo bardziej owocny czas.

Tak, znam podstawy fizyki. Ale twierdzę, że istnieje perpetum mobile. I zamiast próbować mi udowodnić, że nie istnieje, bo się nie da, spróbuj sam je wymyślić. I będzie to dużo bardziej owocny czas.

Więc pokaż po prostu swój algorytm. Będzie spełniał założenia - pokażesz, że masz rację. I tyle. Mi, póki co wydaje się, że się tak nie da.

1
def min_prefix_table(array):
    assert len(array) > 0
    res = [array[0]]
    for item in array[1:]:
        res.append(min((item, res[-1])))
    return res

Tylko już nie duś

0

Racja. Da się.

0

Dzięki wielkie wszystkim! Otrzymałem za ten projekt 32/40 pkt.! Zamykam temat!

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