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..
[Algorytmy] Szukanie trójkątów
[Algorytmy] Szukanie trójkątów
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
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.
Powód: Poprawa wiadomości.
-
- 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
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
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
[Algorytmy] Szukanie trójkątów
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
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
-
- 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
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..
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..
[Algorytmy] Szukanie trójkątów
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
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
-
- 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
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ć.
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ć.