Witam, mam dość nietypowe zadanie. Muszę napisać program sortujący 5 liczb tylko za pomocą instrukcji if/else. Wymagane jest 5 porównań. Czy ktoś wie jak to zrobić? Proszę o pomoc, pozdrawiam
0
0
Wykonanych 5 czy w tekście programu 5? Bo to różnica.
Tak czy siak wydaje się to za mało
powiedzmy, że # oznacza zamień, jeżeli lewy > prawy
mamy A B C D E
A#B
C#D
B#D // D== max(A,B,C,D)
A#C //A==min(A,B,C,D)
B#C // teraz ABCD posortowane rosnąco
5 porównań i ewentualnie zamian, a posortowane tylko 4
0
7 porównań wykonanych.
0
Może tak:
wpierw sortujemy trzy liczby A,B,C przy pomocy //edit trzech (dwóch) porównań:
(A-B)(B-C)#0 jeśli lewa strona jest większa, to albo oba czynnik są dodatnie stąd wynika kolejność A B C, albo oba są ujemne i mamy kolejność C B A, porównanie A#C rozstrzyga
//edit podróże kształcą, dzisiaj w autobusie olśniło mię
jeśli lewa strona jest ujemna, to jeden z czynników jest dodatni, //edit porównaniem A-B#0 rozstrzygamy czy czynnik A-B jest dodatni, jeśli dodatni jest A-B, to B jest najmniejsze i starczy porównać A oraz B, jeśli dodatni jest B-C, to B jest największe i starczy porównać A z C
Po ewentualnej zmianie oznaczeń i //edit trzech (dwóch) porównaniach mamy A>B>C, porównujemy teraz
(D-A)(D-B)(D-C)#0, jeśli lewa strona jest dodatnia, to albo wszystkie czynniki są dodatnie i wtedy D idzie na czoło, albo jeden jest dodatni - oczywiście największy czyli D-C, porównanie D#B rozstrzyga, która możliwość zachodzi
jeśli lewa strona jest ujemna, to albo wszystkie czynniki są ujemne i D idzie na koniec, albo jeden jest ujemny - oczywiście najmniejszy czyli D-A, znowu porównanie D#B rozstrzyga
Przy pomocy pięciu porównań mamy posortowane cztery liczby: A>B>C>D
Porównujemy (E-A)(E-B)(E-C)(E-D)#0, jeżeli lewa strona jest dodatnia, to albo wszystkie czynniki są dodatnie i E idzie na czoło, albo dwa (największe) są dodatnie, starczy porównać E#B by rozstrzygnąć, jeżeli lewa strona jest ujemna, to ujemny jest jeden czynnik (E-A) lub trzy (E-A),(E-B),(E-C) porównanie
E#B lub E#C rozstrzyga. //edit Zatem starczy 7 porównań.
0
taka mysl mi sie narzucila.. nie weryfikowana
(A-B)(B-C)#0 jeśli lewa strona jest większa, to albo oba czynnik są dodatnie stąd wynika kolejność A B C, albo oba są ujemne i mamy kolejność C B A, porównanie A#C rozstrzyga
potrzebne w ogole jest to rozstrzygniecie? moze jesli po-pozostawiac nieokreslonosci ukladu "mamy rosnaco albo mamy malejaco" przez calosc algo, to moze na koncu wystarczy RAZ porownac glowe z ogonem i wypisac wprost lub reverse ?
0
@up, na postęp raczej nie licz. Przy pomocy 6 porównań można rozróżnić co najwyżej 26 = 64
stany, przy pomocy 7 porównań 27 = 128 stanów. 5 liczb można uporządkować na 5! = 120 sposobów. Jest zatem nadzieja, że odpowiednio dobrane 7 porównań uporządkuje 5 liczb, 6 nie starczy na pewno. Przy pomocy 6 porównań jest nadzieja na uzyskanie ciągu monotonicznego, bez możliwości rozstrzygnięcia czy on rośnie, czy maleje.
pozdrawiam