Оставить среднее

chess

mOleg писал(а):

вообще, речь в данном случае о медианном среднем значении, оно может находиться для любого количества чисел, вот только, если все числа одинаковые, не понятно, зачем его не возвращать-то?

В исходном условии задачи 'среднее' число для 3-х чисел или есть в единственном экземпляре или его нет.
Этот момент единственности среднего числа должен сохраниться и для большего количества чисел. Это мое условие.
Искать какой-то смысл в этой задаче не стоит. Задача-то абстрактная.
Пока оказалось, что решить ее 'неродными' для Форта средствами гораздо проще.

Hishnik

Сортируем массив, можно половину элементов плюс еще один. Средний элемент будет медианой. Если нужно, чтобы он был еще и единственным - проверяем соседей слева и справа. Не забываем вытереть полотенцем обсосанный палец

chess

Хищник писал(а):

Сортируем массив, можно половину элементов плюс еще один. Средний элемент будет медианой. Если нужно, чтобы он был еще и единственным - проверяем соседей слева и справа. Не забываем вытереть полотенцем обсосанный палец

Ну вот очередное определение 'среднего'.
Можно еще вот так:
абсолютное значение разницы количества больших и количества меньших чисел для 'среднего' минимальна, при этом
нет чисел с таким же значением этой разницы.

gudleifr

О времени счета. В случае ближайшего к среднему, сложность On. Точнее 2 прохода: для нахождения среднего, и для поиска ближайшего. В случае медианы - Onlogn, т.к. достаточно отсортировать массив.
О практическом применении. Как припоминаю, в алгоритме быстросорт для разбиения массива рекомендовалось искать медиану из случайной выборки 5 значений.
Об алгоритме для небольшого количества значений. Нужно три слова:
1) сравниватель двух стековых значений:
позиция-1, позиция-2, степень-2-ки -- степень-2-ки | 0
Может вызвать исключение "совпадение".
2) слово преобразующее номер пары в пару позиций
пара -- позиция-1, позиция-2
3) слово выбирающее из массива слов размером 2-в-степени-числа-сравнений слово, выбирающее нужное значение и чистящее стек
..., сумма-успехов -- результат, -1 | 0
Массивы для (2) и (3) могут быть заполнены автоматически при задании числа n.
Остальные слова - очевидные.
Очевидно, число сравнений - число сочетаний из n по 2.
О невозвращении ничего. Очевидно, того, кто вызвал нашу прогу, интересует результат. Заставлять его исследовать глубину стека? За это убивать надо.

chess

gudleifr писал(а):

О времени счета.

Все зависит от того как определено среднее число. При "абсолютное значение разницы количества больших и количества меньших чисел для 'среднего' минимальна, при этом
нет чисел с таким же значением этой разницы" оценка времени счета значительно ухудшится.

gudleifr писал(а):

Об алгоритме для небольшого количества значений.

Существует много алгоритмов примерно одинаковых по эффективности.

gudleifr писал(а):

О невозвращении ничего.

Простенький контроль стека соорудить всегда можно.
Вот например так:

Код:

\ для простого контроля стека
M: S{  ( n -- )  >R DEPTH >R ;
M: }S ( -- n ) DEPTH R> SWAP - R> SWAP - ;

: middle ( a b c -- m s | s ) 3 ( число параметров, с которым работает слово ) S{
 3|123mm`1+123MM  5\145Hi1t245Hi2t345Hi3t }S ;

-21 45 0 middle ( 0 1 ) \ 0 - на стеке осталось число  0   1 - одно число
   2 3 2 middle ( 0 )   \ на стеке ничего не осталось  0 - 0 чисел

gudleifr

chess писал(а):

При "абсолютное значение разницы количества больших и количества меньших чисел для 'среднего' минимальна, при этом нет чисел с таким же значением этой разницы" оценка времени счета значительно ухудшится.

Нет, достаточно отсортировать, посчитать сумму, ~~разделить пополам и найти ближайшее~~.

chess писал(а):

Простенький контроль стека соорудить всегда можно.

Я и говорю: убивать!

gudleifr

Вместо зачеркнутого - просто перебор с изменением левой (от нуля) и правой (от общей суммы) сумм. Могут ли быть числа с одинаковыми полусуммами? Пусть последовательность A(0..n) упорядочена, а Ai и Aj такие числа и i < j (Ai =< Aj).
S(i..N] - S[0..i) = S(j..N] - S[0..j);
S(i..j) + Aj + S(j..N] - S[0..i) = S(j..N] - S[0..i) - Ai - S(i..j);
Ai + Aj + 2S(i..j) = 0;
Т.е. такое возможно только на отрезке перехода от отрицательных членов к положительным. Причем в точке 0 будет максимум - самое "несреднее" значение.

WingLion

gudleifr писал(а):

Я и говорю: убивать!

Зачем так жестоко? оторвать яйца, и этого достаточно...

WingLion

вариантов решения всего 4
1. результат - верхнее число из 3-х
2. результат - нижнее число из 3-х
3. результат - среднее из 3-х
4. - результат отсутствует

для 4-го надо сравнить числа и, если среди них есть равные - значит результата нет
а три остальные получаются сортировкой и выборкой среднего из трех упорядоченных чисел

Код:

/ вспомогательные слова

/ копировать 3 элемента
/ на асме проще, но Forth-only
: 3DUP 
ROT DUP >R -ROT R>
ROT DUP >R -ROT R>
ROT DUP >R -ROT R> ;
/ или так
: 3DUP ROT DUP >R -ROT 2DUP R> -ROT ;

/ неразрушающе сравнить два из трех
: 32= 2DUP = ;

/ элемент "пузырька" на двух верхних словах
: MAX 2DUP < IF SWAP THEN ;
/ сортировка 3-х элементов
: 3BUBBLE
/ первый проход "пузырька"
ROT MAX -ROT MAX 
/ второй проход "пузырька"
ROT MAX -ROT MAX
/ а больше и не надо
;

/ главное слово - то, которое middle
: MAIN-WORK ( a b c --> result | NULL )

/ сравнить числа и, если среди них есть равные - значит результата нет
32= IF 3DROP EXIT THEN \ удалить все и выйти, если есть равные числа
ROT 32= IF 3DROP EXIT THEN \ удалить все и выйти, если есть равные числа
ROT 32= IF 3DROP EXIT THEN \ удалить все и выйти, если есть равные числа

/ возвращать порядок чисел на стеке третьим ROT не обязательно 
/ сортировке на это плевать результат должен быть 

/ остается только отсортировать 3 элемента 

3BUBBLE
/ первый проход "пузырька"
ROT MAX -ROT MAX 
/ второй проход "пузырька"
ROT MAX -ROT

/ выкинуть верхнее и нижнее
DROP SWAP DROP
/ результат готов если он есть 
/ а если нет, то уже вышли раньше по EXIT
;

код не проверялся, писал спросонья

Alex

немного подправил очепятку в выше приведенном коде

Код:

: 3DROP 2DROP DROP ;

\ вспомогательные слова

\ копировать 3 элемента
\ на асме проще, но Forth-only
: 3DUP 
ROT DUP >R -ROT R>
ROT DUP >R -ROT R>
ROT DUP >R -ROT R> ;
\ или так
: 3DUP ROT DUP >R -ROT 2DUP R> -ROT ;

\ неразрушающе сравнить два из трех
: 32= 2DUP = ;

\ элемент "пузырька" на двух верхних словах
: MAX 2DUP < IF SWAP THEN ;
\ сортировка 3-х элементов
: 3BUBBLE
\ первый проход "пузырька"
ROT MAX -ROT MAX 
\ второй проход "пузырька"
ROT MAX 
\ а больше и не надо
;

\ главное слово - то, которое middle
: MAIN-WORK ( a b c --> result | NULL )

\ сравнить числа и, если среди них есть равные - значит результата нет
    32= IF 3DROP EXIT THEN \ удалить все и выйти, если есть равные числа
ROT 32= IF 3DROP EXIT THEN \ удалить все и выйти, если есть равные числа
ROT 32= IF 3DROP EXIT THEN \ удалить все и выйти, если есть равные числа

\ возвращать порядок чисел на стеке третьим ROT не обязательно 
\ сортировке на это плевать результат должен быть 
\ остается только отсортировать 3 элемента 

3BUBBLE

\ выкинуть верхнее и нижнее
DROP SWAP DROP
\ результат готов если он есть 
\ а если нет, то уже вышли раньше по EXIT
;

chess

Alex писал(а):

немного подправил очепятку в выше приведенном коде

А как используется 3DUP?

Мой вариант на форте(алгоритм тот же, что и в манипуляторном варианте):

Код:

: 3DUP ( a b c -- a b c a b c ) >R 2DUP R@ -ROT R> ;
: middle ( a b c -- middle | _ )
3DUP 3DUP MIN MIN 1+ >R MAX MAX >R
DUP 2R@ WITHIN IF RDROP RDROP NIP NIP EXIT ELSE DROP THEN
DUP 2R@ WITHIN IF RDROP RDROP NIP EXIT ELSE DROP THEN
DUP 2R> WITHIN 0= IF DROP THEN ;

Ps. Написать было на порядок сложнее чем на манипуляторах(на них мгновенно).

Mihail

: 3DUP ( x1 x2 x3 -- x1 x2 x3 x1 x2 x3 )
DUP 2OVER ROT ;

chess

Mihail писал(а):

: 3DUP ( x1 x2 x3 -- x1 x2 x3 x1 x2 x3 )
DUP 2OVER ROT ;

С помощью манипулятора можно записать проще:

Код:

: 3DUP 3|123 ;

gudleifr

chess писал(а):

...
DUP 2R@ WITHIN IF RDROP RDROP NIP NIP EXIT ELSE DROP THEN
...
5\145Hi1t245Hi2t345Hi3t
...

Не знаю, только у меня обе записи вызывают идиосинкразию?
Или рассуждаем по принципу: "Идиотской задаче - идиотское решение!"
P.S. На мой взгляд стековые манипуляторы "не работают" по одной простой причине. Они естественны только в случае использования стека в качестве маленького однородного массива. Но, как только мы от массива из 3-х элементов переходим к 117 или n элементам, вся естественность пропадает - нам приходится размещать на стеке не столько элементы, сколько адреса, счетчики, флаги. А для разнородной информации лучше имена, чем номера.
P.P.S. Но Вам, коллега, удалось доказать: манипуляторы страшны и при своем природном использовании.

chess

gudleifr писал(а):

Не знаю, только у меня обе записи вызывают идиосинкразию?

Идиосинкразия (от греч. idios — своеобразный, особый, необычный и synkrasis — смешение),
болезненная реакция, возникающая у отдельных людей на раздражители, которые у большинства других не вызывают подобных явлений.
Я наверное отношусь к большинству, а вы к отдельным людям.

gudleifr писал(а):

Или рассуждаем по принципу: "Идиотской задаче - идиотское решение!"

Задача абстрактная это да. По отношению к абстрактной задаче термин идиотский не имеет смысла.
К чему ее все-таки можно отнести? Ну, например, к определению функции пороговой логики.

gudleifr писал(а):

P.S. На мой взгляд стековые манипуляторы "не работают" по одной простой причине. Они естественны только в случае использования стека в качестве маленького однородного массива. Но, как только мы от массива из 3-х элементов переходим к 117 или n элементам, вся естественность пропадает - нам приходится размещать на стеке не столько элементы, сколько адреса, счетчики, флаги. А для разнородной информации лучше имена, чем номера.

Манипуляторы это инструмент, который нужно применять в определенных условиях, как и все остальное. Для данной задачки подходит. А также, подходят к разнообразной работе с параметрами на стеке независимо от типа этих параметров. Могут сочетатся со всем остальным инструментарием форта, в том числе и с именами. Насчет стека, это все-таки не массив и параметры на нем не всегда однородны. 117 элементов размещать на стеке ни к чему. Стек не для этого.

gudleifr писал(а):

P.P.S. Но Вам, коллега, удалось доказать: манипуляторы страшны и при своем природном использовании.

У страха глаза велики.

Оставить среднее

Кто сейчас на конференции