[Algorytmy] Szukanie trójkątów

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Algorytmy] Szukanie trójkątów

Post autor: adambak »

Mamy nieposortowaną tablicę \(\displaystyle{ A}\) wypełnioną \(\displaystyle{ n}\) liczbami naturalnymi, które utożsamiamy z długościami odcinków.. Napisz algorytm sprawdzający czy:
(a) z każdych 3 odcinków, których długości są reprezentowane w \(\displaystyle{ A}\) da się zbudować trójkąt
(b) istnieją takie trzy odcinki, z których da się zbudować trójkąt

czy da radę to zrobić szybciej niż \(\displaystyle{ O(n^3)}\)? ciężko mi sobie wyobrazić to dla podpunktu (a), ale (b) jest już sporo inny, więc tak się zastanawiam..
Xitami

[Algorytmy] Szukanie trójkątów

Post autor: Xitami »

a) \(\displaystyle{ sort(A); A[1]+A[2]>A[n]}\) wystarczy? coś mnie tu uwiera, śpiącym już

b) \(\displaystyle{ sort(A); \frac{n\cdot n}{2}}\) par, logarytmicznie poszukać mniejszego od sumy?

ɔouɐɹqop
Ostatnio zmieniony 14 lis 2011, o 08:35 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Algorytmy] Szukanie trójkątów

Post autor: adambak »

a) mnie to nawet boli trochę.. \(\displaystyle{ A=[1,2,3,4,5,6]; \ A[1]=1; \ A[2]=2; \ A[n]=6;}\), a mamy tutaj trójkę z której się da skonstruować trójkąt..
b) niezłe.. ale dzisiaj przewinęło się przez myśl:

\(\displaystyle{ 1) \ sort(A);}\)

\(\displaystyle{ 2) \ i \le n-2}\)

\(\displaystyle{ \text{if }( \ A+A[i+1]>A[i+2] \ ) \\ \ \ \text{ to mamy trojkat;} \\ \text{else} \\ \ \ \text{ nie da sie skonstruowac;}}\)

a więc koszt liniowo-logarytmiczny tylko (sortowanie + jedna pętla do \(\displaystyle{ n-2}\)), ale nie wiem czy działa..


fajny napis
Xitami

[Algorytmy] Szukanie trójkątów

Post autor: Xitami »

a) no mamy, ale mamy też trójki nietrójkątne (1,2,n) a pytamy czy z dowolnych
sortowanie można zastąpić tańszym szukaniem dwu min i jednego max, razem O(n)

b) buduję ciąg dla którego twój sposób nie zadziała 1,2,4,7,11,18,29
wydaje mnie mi się, że brak w nim trójkątnych trójek, czyli chyba dowód poprawności
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Algorytmy] Szukanie trójkątów

Post autor: adambak »

a) masz rację! przepraszam, myślałem chyba o innej treści.. czyli wystarczy O(n), bo wyszukanie dwóch minimów i maksa.. odważnie, aczkolwiek brzmi bardzo rozsądnie.. chyba zadziała

b) brak w nim trójkątnych trójek.. sprawdzamy każde trzy kolejne, bo to są najlepsi kandydaci.. czyli działa? bo sam nie jestem do końca przekonany chyba.. ale wątpię, żeby tutaj dało się też zejść do liniówki..
Xitami

[Algorytmy] Szukanie trójkątów

Post autor: Xitami »

tylko dla porządku, oczywiście zamiast
1,2,4,7,11,18,29 powinno być
1,2,4,7,12,20,31, ... czyli \(\displaystyle{ a_{n}=1+a_{n-1}+a_{n-2}}\)
oraz
\(\displaystyle{ a_i+a_{i+1} \ge a_{i+2}}\) obaj użyliśmy ostrej relacji

b) czy możliwe liniowo? coś mi mówi że tak
Afish
Moderator
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

[Algorytmy] Szukanie trójkątów

Post autor: Afish »

Co do b, to metoda z sortowaniem i jedną pętlą wydaje się okej. Jeżeli istniałaby trójka niekolejnych liczb, z której da się zbudować trójkąt, to zwiększając najmniejszą liczbę i zmniejszając największą ciągle da się zbudować trójkąt. Z drugiej strony jeżeli trzy kolejne liczby nie pozwalają na zbudowanie trójkąta, to zmniejszając najmniejszą albo zwiększając największą na pewno nie damy rady tego zmienić. Koniec dowodu przez machanie rękami.
Czy można zrobić liniowo? Pomijając możliwość zbicia złożoności sortowania, to wydaje się, że nie. Aczkolwiek poranna intuicja może się mylić.
ODPOWIEDZ