9742848621

Wyszukiwanie i porządkowanie informacji nieź wykazać, że algorytmy Min-i-Max i Min-i-Max_rec są optymalne, tzn. wykonują możliwie najmniejszą liczbą por-wnafi.

Na I i II Olimpiadzie Informatycznej (patrz materiały z tych olimpiad [1] i |2j) pojawiły sią dwa zadania związane z istnieniem tr-jkąt-w o zadanych długościach bok-w. lak wiemy, z trzech odcink-w można zbudować tr-jkąt wtedy i tylko wtedy, gdy suma długości każdych dw-ch odcink-w jest większa od

W swych pełnych, konkursowych sformułowaniach, zadania te są dość trudne, wiązać. Szczeg-łowe om-wienie tych zadań i ich rozwiązań znajduje się w cy-

Zadanie A. W pliku dany jest skończony, co najmniej trzyelementowyzbi-rA odcin-

ry drukuje odpowiedź TAK. jeśli z każdych trzech odcink-w ze zbioru A można zbudować tr-jkąt. lub odpowiedź NIE wprzeciwnymprzypadku.

runek tr-jkąta dla przypadku uporządkowanych długości jego bok-w, a na-liczb, wczytywanym z pliku. To ostatnie założenie jest związane z tym, że plik

Zadanie B. W pliku dany jest ciąg przynajmniej trzech liczb całkowitych dodatnich, nie większych niż miliard (tj. nie większych niż 10⁹ = lOOOOOOOOO). Uł-ż

pliku istnieją trzy takie, z kt-rych można zbudować tr-jkąt.

Wskaż wko. To zadanie tylko pozornie jest podobne do poprzedniego jedyne ich podobieństwo ogranicza się do wykorzystania warunku tr-jkąta w rozwiązaniu. Rozwiązanie tego zadania może być pewnym zaskoczeniem dla uczni-w

<17>

5. PORZĄDKOWANIE PRZEZ WYB R | ITERACJA ALGORYTMU

nadal uporządkowany.

Dane: Liczba naturalna n i ciągn liczbx₁,x₂,..