Задачка

← →
default © (2005-11-13 19:34) [0]

За семь сравнений отсортировать пять разных чисел

← →
Zeqfreed © (2005-11-13 19:47) [1]

А за нуль сравнений считается?

← →
default © (2005-11-13 19:48) [2]

допустимая операция над числами тут одна: попарное сравнение(ответ: больше, меньше)

← →
Zeqfreed © (2005-11-13 19:59) [3]

default © (13.11.05 19:48) [2]
Не, ну просто за нуль сравнений можно, зачем нам 7 лишних?

← →
DrPass © (2005-11-13 20:01) [4]

> default © (13.11.05 19:34)

А с напрягалкой мозгов проблема?

← →
default © (2005-11-13 20:02) [5]

Zeqfreed © (13.11.05 19:59) [3]
покажи что ты там придумал

← →
default © (2005-11-13 20:03) [6]

DrPass © (13.11.05 20:01) [4]
это не призыв о помощи, кому интересно решают кому нет гуляют в сторонке

← →
MBo © (2005-11-13 20:05) [7]

Хорошая задачка - очень трудная.

← →
Zeqfreed © (2005-11-13 20:11) [8]

default © (13.11.05 20:02) [5]
Это не я придумал, это называется сортировка подсчетом.

function Sort(const Source : TWordArray) : TWordArray; var i, j, idx : Integer; cntarr : array[0..High(Word)] of Word; begin for i := 0 to High(Word) do begin cntarr[i] := 0; end; for i := Low(Source) to High(Source) do begin cntarr[Source[i]] := cntarr[Source[i]] + 1; end; idx := 0; for i := 0 to High(Word) do for j := 1 to cntarr[i] do begin Result[idx] := i; Inc(idx); end; end;

← →
Zeqfreed © (2005-11-13 20:12) [9]

Zeqfreed © (13.11.05 20:11) [8]
type TWordArray = array[0..4] of Word;

← →
default © (2005-11-13 20:20) [10]

MBo © (13.11.05 20:05) [7]
кстати, Борис, хотел спросить: вторая задачка в Ваших пятничных решается на компе или есть короткий перебор
я вижу моменты на которых можно прилично сократить перебор, но есть ли какая тонкость которая даёт возможность быстро дать ответ на вопрос задачи?

← →
default © (2005-11-13 20:23) [11]

Zeqfreed © (13.11.05 20:11) [8]
в условии не сказано что только целые сравниваются

← →
MBo © (2005-11-13 20:30) [12]

>default © (13.11.05 20:20) [10]
>вторая задачка в Ваших пятничных решается на компе или есть короткий перебор

Если не найти правильный путь, то на компе нереально или очень долго, а если найти - то утверждается, что можно и на бумаге. Мне не удалось с наскока.

← →
default © (2005-11-13 20:38) [13]

MBo © (13.11.05 20:30) [12]
вот что пока есть
можно сугубо аналитически показать что в сотом подъезде дома любой этажности нет престижных квартир
перебирать этажи домов разной этажности можно за разумное время
на второй этаж уйдёт где-то 4*30=120c
на третий 6*30=180c
на четвертыё 8*30=240с
и тд
уже не так мало времени уйдёт

← →
Иван Шихалев © (2005-11-14 01:30) [14]

> default © (13.11.05 19:34)

Сортировать обязательно на месте?

← →
Fenik © (2005-11-14 01:49) [15]

Пока только за 8 сравнений получается...

← →
Fenik © (2005-11-14 01:51) [16]

> Иван Шихалев © (14.11.05 01:30) [14]
> Сортировать обязательно на месте?

А где ещё можно??

← →
default © (2005-11-14 19:21) [17]

так никто и не догадался?;)

← →
Sandman29 © (2005-11-15 12:21) [18]

default © (14.11.05 19:21) [17]

Давай уже ответ, не томи душу :)

← →
MBo © (2005-11-15 12:50) [19]

>Sandman29 © (15.11.05 12:21) [18]
>Давай уже ответ, не томи душу :)

Задача трудная, но интересная ;)
7 сравнений дают 7 бит информации, т.е. 128 возможных исходов, а перестановок 5 чисел - 5!=120, т.е. видно, что в принципе возможно составить сеть принятия решения. Обозначим числа a,b,c,d,e.
Вначале сравним и переставим при необходимости пары
A<B
C<D
теперь меньшие из этих пар:
A<C
Получили:
b>a<c<d
Теперь оставшееся e сравниваем с С и в зависимости от результата выполняем еще три сравнения - заранее неопределенные.
Дальше писать?

← →
Sandman29 © (2005-11-15 13:03) [20]

MBo © (15.11.05 12:50) [19]

Ну до этого шага я тоже дошел :)
Вот как раз дальше самое интересное и начинается. Особенно с учетом того, что иногда теряется часть информации - например, при сравнении E с C мы используем методику деления пополам, но середины в последовательности с четным количеством элементов нет.

← →
MBo © (2005-11-15 13:13) [21]

>иногда теряется часть информации
Да, это так, варианты не точно пополам делятся, но у нас есть запас в несколько долей бита ;)

После трех сравнений я уже выписывал возможные варианты на бумаге и строил дерево снизу вверх (от листьев).

← →
MBo © (2005-11-15 13:41) [22]

Если не запутался, то что-то в этом роде:
1 E<C
1.1 B<C
1.1.1 E<A EABCD
1.1.2 E>A
1.1.2.1 E<B AEBCD
1.1.2.2 E>B ABECD
1.2 B>C
1.2.1 A<>E B<>D

2. E>C
D<>E
(B<>E или B<>C) или (B<>D или еще что там осталось)

MBo © (15.11.05 13:41) [22]
рано ответ дали! ну да ладно
а задача в принципе не сильно долгим перебором решается
(ставлю под сомнение пост [7])
можно было так:
пойдём с конца, то есть сколько должно быть вариантов перед 7 сравнением чтобы гарантировано оно дало ответ на вопрос задачи
это 2 или 1
перед шестым сравнением должен иметь место один из вариантов
4(2:2),3,2,1
a:b означает, что должно существовать сравнение дающее разбиение набора вариантов(размера a+b) в отношении a к b
перед пятым сравнением должен быть один из вариантов
8(4:4),7(3:4),6(2:4,3:3),5,4,3,2,1
и тд до 2 сравнения(назовём эту последовательность - фильтром)
до второго сравнения потому что нам пофиг какое число с каким сравнивать на первом сравнении, обозначим меньшее из них a, а большее b(по результатам первого сравнения)
остальные c,d,e
итак второе сравнение мы можем провести по следующим вариантам:
c,d;c,e;d,e;a,c;b,c;a,d;b,d;a,e;b,e
для каждого варианта беглым взором подсчитываем разбиентие k1:k2
и смотрим подходит ли данный вариант по фильтру
фильтр оставит только сравнения
c,d;c,e;d,e и тд
фильтр даёт нам возможность заметно сократить перебор

Не бейте только ногами, но я, кажется на алголисте, читал, что меньше чем за n-1 простых сравнений n чисел не отсортировать никак.

> Marser © (16.11.05 19:59) [25]
> Не бейте только ногами, но я, кажется на алголисте, читал,
> что меньше чем за n-1 простых сравнений n чисел не отсортировать
> никак.

Конечно. Как минимум каждое надо сравнить. :)

Раз решение уже написали, то приведу две ссылки:
http://www.rsdn.ru/Forum/?mid=110745 - здесь решалась
http://www.rsdn.ru/Forum/?mid=486107 - здесь безуспешно пытались обобщить

А вот другая задача: для массива N разных чисел найти наименьшее число сравнений, с помощью которых этот масив можно отсортировать. :)

Задачка Найти похожие ветки