Mamy dane dwie tablice rzeczywiste długości \(\displaystyle{ n}\) , oznaczmy je przez \(\displaystyle{ A,B}\) . \(\displaystyle{ A}\) jest posortowana niemalejąco, a \(\displaystyle{ B}\) nierosnąco. pary \(\displaystyle{ A[k],B [k]}\) interpretujemy jako boki pewnego prostokąta i chcemy znaleźć taki indeks, który da prostokąt o najkrótszej przekątnej.
Wiadomo, że chodzi nam o jakąś pochodną wyszukiwania binarnego i koszt \(\displaystyle{ O(\ln(n))}\) . Ale nie mogę znaleźć żadnego punktu zaczepienia. Jeśli potraktujemy te przekątne jako funkcję \(\displaystyle{ f: [0,...,n] \rightarrow \RR}\) , gdzie \(\displaystyle{ f(k)}\) , to długość przekątnej \(\displaystyle{ k}\) -tego prostokąta i pozostałe wartości otrzymujemy przez łączenie punktów łamanymi, to ta funkcja zdaje się nie mieć absolutnie żadnych sensownych własności (wypukłość itp).
[Algorytmika] Przekątne prostokątów
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmika] Przekątne prostokątów
Przy podanych założeniach nie da się binarnie. Weź takie dane:
Po sprawdzeniu środkowej pary możesz podjąć decyzję o skierowaniu swych kroków w prawo (do większych indeksów) lub w lewo. W tym wypadku pasuje w prawo, ale jak weźmiemy takie dane:
to wypadałoby w lewo. Nie jesteś w stanie podjąć decyzji na podstawie pojedynczego indeksu.
Kod: Zaznacz cały
A = [5, 5, 5]
B = [10, 5, 1]
Kod: Zaznacz cały
A = [1, 5, 5]
B = [5, 5, 5]
-
- Użytkownik
- Posty: 8
- Rejestracja: 6 paź 2017, o 21:36
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 2 razy
[Algorytmika] Przekątne prostokątów
No właśnie, to miałem na myśli. Czyli co – prymitywny liniowy algorytm?