Konkursy, zadanie nr 271
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
andu post贸w: 2 |  2017-07-20 19:38:22Mamy pi臋膰 z艂otych samorodk贸w nieznacznie r贸偶ni膮cych si臋 wag膮. Ile potrzeba wa偶e艅, na wadze szalkowej bez odwa偶nik贸w, by je uporz膮dkowa膰 od najci臋偶szej do najl偶ejszej? (Ten sam algorytm mo偶na zastosowa膰 do uporz膮dkowania 5 dru偶yn lub zawodnik贸w w turnieju np tenisowym przy pomocy najmniejszej ilo艣ci rozegranych mecz贸w.) |
rockstein post贸w: 33 | 2017-11-16 19:29:31 Problem sprowadza si臋 do tego, po ilu wa偶eniach, czyli bezpo艣rednich por贸wnaniach mas dw贸ch obiekt贸w, b臋dzie mo偶na uporz膮dkowa膰 pi臋膰 r贸偶nych obiekt贸w pod wzgl臋dem zmniejszaj膮cych si臋 mas. Jak wiadomo 5 obiekt贸w mo偶na uszeregowa膰 na 5! sposob贸w, czyli mo偶e by膰 120 r贸偶nych uporz膮dkowa艅. Z kolei ka偶de wa偶enie daje jeden z dw贸ch mo偶liwych wynik贸w, zatem w wa偶e艅 mo偶e da膰 2^w wynik贸w. St膮d wniosek, 偶e najmniejsza ilo艣膰 wa偶e艅 w musi spe艂nia膰 nier贸wno艣膰: 2^(w-1)<n!<2^w. Skoro w naszym przypadku n!=120, to 64<120<128, czyli 2^6<120<2^7. Zatem odpowied藕 na postawione pytanie brzmi: Aby uporz膮dkowa膰 5 samorodk贸w, z kt贸rych ka偶de dwa r贸偶ni膮 si臋 mas膮, w kierunku od najci臋偶szego do najl偶ejszego (lub odwrotnie), potrzeba co najmniej 7 wa偶e艅. S膮dz臋 jednak, 偶e ta odpowied藕 dok艂adnie odpowiadaj膮ca na postawione pytanie, nie w pe艂ni usatysfakcjonuje pytaj膮cego, bowiem w dopisku jest mowa o algorytmie post臋powania. Ot贸偶 s膮 mo偶liwe dwa sposoby post臋powania: Spos贸b 1. Por贸wnanie mas i uporz膮dkowanie trzech dowolnie wybranych samorodk贸w (w wi臋kszo艣ci przypadk贸w 3 wa偶enia), por贸wnanie masy czwartego samorodka ze 艣rednim z pierwszej tr贸jki, a nast臋pnie ze skrajnym (2 wa偶enia), wreszcie por贸wnanie masy pi膮tego samorodka z mas膮 jednego ze 艣rodkowych i w niekorzystnym przypadku z masami dw贸ch przeciwleg艂ych (3 wa偶enia). Jak wida膰, w wi臋kszo艣ci przypadk贸w b臋dzie potrzeba o艣miu wa偶e艅, mimo 偶e post臋powanie jest w pe艂ni racjonalne. Spos贸b 2. Por贸wnujemy masy samorodk贸w S1 i S2 oraz S3 i S4 (2 wa偶enia), por贸wnujemy samorodki ci臋偶sze z obu par, np S2 i S4 (1 wa偶enie), por贸wnujemy samorodek S5 z l偶ejszym z poprzedniego wa偶enia (1 wa偶enie). Uzyskujemy w ten spos贸b szkielet nier贸wno艣ci, kt贸ry daje si臋 ostatecznie uporz膮dkowa膰 w 3 nast臋pnych wa偶eniach. Tym sposobem post臋powania uzyskujemy wynik w wyliczonej uprzednio, minimalnej ilo艣ci 7 wa偶e艅. |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj