Oberon space
General Category => Общий раздел => Тема начата: ilovb от Июнь 05, 2012, 08:20:08 am
-
Возможно уже многие решали. В первый раз решать довольно забавно.
В интернеты и кнуты не подглядывать.
Дан массив из 5 чисел. Отсортировать максимум за 7 сравнений.
-
Возможно уже многие решали. В первый раз решать довольно забавно.
В интернеты и кнуты не подглядывать.
Дан массив из 5 чисел. Отсортировать максимум за 7 сравнений.
А че так много то (сравнений)... ;) ? фильтрационная задача, не далее как вчера дал первокурсникам на зачет... в такой формулировке -пусть поэлементно обрабатывается поток положительных чисел (завершает поток число 0).. определить три максимума (в вашей формулировке их 5).
-
Ну тык код в студию ;)
Задачу решат все. Интерес представляет красивость решения.
-
Ну тык код в студию ;)
Задачу решат все. Интерес представляет красивость решения.
;) щас, разбежался... в оригинальной задаче, студентам(решившим ее) хватило 2 сравнений, в вашей трактовке хватит 4...
-
Ну тык код в студию ;)
Задачу решат все. Интерес представляет красивость решения.
;) щас, разбежался... в оригинальной задаче, студентам(решившим ее) хватило 2 сравнений, в вашей трактовке хватит 4...
Вру, конечно, 3 и 5, соответственно.
-
За 5? :o
Вы ведь о худшем случае?
-
О произвольном... но на решение отводилось 12 минут. ;)
-
Да у вас вундеркинды учатся. Я эту задачу с нахрапа не осилил, когда она мне первый раз попалась.
-
Да у вас вундеркинды учатся. Я эту задачу с нахрапа не осилил, когда она мне первый раз попалась.
В вашей формулировке и не осилили (а я бы им и не дал) за отведенное время.
-
Код на Обероне. Не проверял компиляцию.
PROCEDURE Sort (VAR a: ARRAY 5 OF INTEGER);
VAR
NumLeaders: INTEGER;
PROCEDURE Exchange (LeftInd, RightInd: INTEGER);
VAR
TransfValue: INTEGER;
BEGIN
TransfValue := a[LeftInd];
a[LeftInd] := a[RightInd];
a[RightInd] := TransfValue;
END Exchange;
PROCEDURE MoveLeaderRight (FromInd: INTEGER);
VAR
i: INTEGER;
BEGIN
FOR i := FromInd TO LEN(a) - 1 - NumLeaders DO
Exchange(i, i + 1);
END;
END MoveRight;
(* Makes ChainLen - 1 comparisons *)
PROCEDURE FindLeader (LeftInd, ChainLen: INTEGER);
BEGIN
(* A B C => A MAX(B, C) MIN(B, C) *)
IF ChainLen = 3 THEN
IF a[LeftInd + 1] > a[LeftInd + 2] THEN
Exchange(LeftInd + 1, LeftInd + 2);
END;
END;
(* A B *)
IF a[LeftInd] > a[LeftInd + 1] THEN
MoveLeaderRight(LeftInd);
ELSE
MoveLeaderRight(LeftInd + 1);
END;
END FindLeader;
BEGIN
NumLeaders := 0;
FindLeader(0, 3); (* [A B C] D E => A B D E 1? *)
FindLeader(2, 2); (* A B [D E] 1? => A B D 1? 1? *)
FindLeader(3, 2); (* A B D [1? 1?] => A B D 2 1 *) NumLeaders := 2;
FindLeader(0, 3); (* [A B D] 2 1 => [A B] 3 2 1 *) NumLeaders := 3;
FindLeader(0, 2); (* [A B] 3 2 1 => 5 4 3 2 1 *)
(* 2 + 1 + 1 + 2 + 1 = 7 comparisons *)
END Sort;
-
Прикольно! Первый раз решали?
-
Да. Обычно использую рукописную быструю сортировку с одноветочной рекурсией.
-
Хороший код. Очень наглядно.
А я первый раз большой IF сгородил :)
-
Спасибо :) Мне тоже пришлось рассмотреть несколько вариантов. Вложенные IF-ELSE росли слишком быстро, чтобы их воспринимать на чтение потом.
-
Решение наглядное, но не самое эффективное.
1. Вызов процедуры (ежели без оптимизаций)
2. Лишнее сравнение "IF ChainLen = 3 THEN" (можно конечно избавиться сделав две процедуры FindLeader)
3. Много перемещений.
В более эффективном решении конечно сильно пострадает наглядность.
Али не пострадает? ;)
-
Непонятно.
Каков возможный диапазон значений последовательности?
-
Любой