кроме сравнений - любые действия?

(Reply to this) (Thread) (Expand)

*удивленно* Простите, а что в этом такого? Вы точно уверены, что она будет интересна кому-то старше учеников средней школы?

Сортируем четыре числа, за три сравнения вставляем между ними пятое.

(Reply to this) (Thread) (Expand)

Что понимать под сравнением?
Скажем, процессорная команда cmp позволяет получить больше информации, чем простая операция "<".

(Reply to this) (Thread) (Expand)

Словами сложно :) проще так:

Пусть есть массив a[5] одного из числовых типов и переменная b того же типа. тогда:

{
if ( a[0] > a[1] )
{
b = a[0];
a[0] = a[1];
a[1] = b;
}

if ( a[2] > a[3] )
{
b = a[2];
a[2] = a[3];
a[3] = b;
}

if ( a[1] > a[3] )
{
b = a[0];
a[0] = a[2];
a[2] = b;
b = a[1];
a[1] = a[3];
a[3] = b;
}

if ( a[1] > a[4] )
{
if ( a[0] > a[4] )
{
if ( a[0] > a[2] )
{
if ( a[4] > a[2] )
{
b = a[0];
a[0] = a[2];
a[2] = b;
b = a[1];
a[1] = a[4];
a[4] = a[3];
a[3] = b;
}
else
{
b = a[0];
a[0] = a[4];
a[4] = a[3];
a[3] = a[1];
a[1] = a[2];
a[2] = b;
}
}
else
{
if ( a[1] >= a[2] )
{
b = a[0];
a[0] = a[4];
a[4] = a[3];
a[3] = a[1];
a[1] = b;
}
else
{
b = a[0];
a[0] = a[4];
a[4] = a[3];
a[3] = a[2];
a[2] = a[1];
a[1] = b;
}
}
}
else
{
if ( a[4] > a[2] )
{
if ( a[0] > a[2] )
{
b = a[0];
a[0] = a[2];
a[2] = a[4];
a[4] = a[3];
a[3] = a[1];
a[1] = b;
}
else
{
b = a[1];
a[1] = a[2];
a[2] = a[4];
a[4] = a[3];
a[3] = b;
}
}
else
{
if ( a[1] >= a[2] )
{
b = a[1];
a[1] = a[4];
a[4] = a[3];
a[3] = b;
}
else
{
b = a[1];
a[1] = a[4];
a[4] = a[3];
a[3] = a[2];
a[2] = b;
}
}
}
}
else
{
if ( a[3] > a[4] )
{
if ( a[1] > a[2] )
{
b = a[3];
a[3] = a[4];
a[4] = b;
if ( a[0] > a[2] )
{
b = a[0];
a[0] = a[2];
a[2] = a[1];
a[1] = b;
}
else
{
b = a[1];
a[1] = a[2];
a[2] = b;
}
}
else
{
if ( a[4] >= a[2] )
{
b = a[3];
a[3] = a[4];
a[4] = b;
}
else
{
b = a[2];
a[2] = a[4];
a[4] = a[3];
a[3] = b;
}
}
}
else
{
if ( a[1] > a[2] )
{
if ( a[0] > a[2] )
{
b = a[0];
a[0] = a[2];
a[2] = a[1];
a[1] = b;
}
else
{
b = a[1];
a[1] = a[2];
a[2] = b;
}
}
}
}
}

Проверить легко, если есть любой компилятор :)

(Reply to this) (Thread) (Expand)

Милай мой. Это тест на знание источников.

(Кстати, я одно время задавал эту задачку на интервью; знание источников также приветствовалось, но, к сожалению, ни один интервьюируемый его не проявил.)

(Reply to this) (Thread) (Expand)

эммм я не программист, но вот так работает

числа: а, б, в, г, д

а = о
а + б < в
б + в = г
г < д

(Reply to this) (Thread) (Expand)

А можно ли с ними что-нибудь еще делать, типа складывать/вычитать?

(Reply to this) (Thread) (Expand)

а на количество умножений и сложений ограничения есть?

(Reply to this) (Thread) (Expand)

Должно быть семь сравнений в блок-схеме или по ходу выполнения алгоритма просто должно быть выполнено не более семи?

(Reply to this) (Thread) (Expand)

Прикольная задачка, пришлось даже Excel открыть, чтобы не в голове цифры крутить :)
Пять цифр - A, B, C, D, E
1.Если A>B - меняем значения местами (A=B, B=A)
2.Если B>C - меняем значения местами
3.Если C>D - меняем значения местами
4.Если D>E - меняем значения местами
5.Если C>D - меняем значения местами
6.Если B>C - меняем значения местами
7.Если A>B - меняем значения местами
Т.е. пробегаем снизу вверх и обратно. Уверен, что есть и другие способы.

(Reply to this) (Thread) (Expand)

Сначала сравнить два произвольных числа, потом сравнивать числа из оставшийся с наибольшим, а потом с предыдущим.

За 7 сравнений в самом неприятном случае, когда сначала попадается наименьшее и наибольшее, получается за 7 сравнений.

1>5
1 5

2>5
2>1
1 2 5

3>5
3>2
1 2 3 5

4>5
4>3
1 2 3 4 5

(Reply to this) (Thread) (Expand)

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

(Reply to this) (Thread) (Expand)

Цифровая сортировка позволяет сортировать числа с фиксированной точкой вообще без сравнений.

Но задачка интересная, да. Очень спасибо. :)

(Reply to this) (Thread) (Expand)

Я тебе по внутреннему емейлу шибко развернутый ответ послал. Там я накатал программу, которая берет множество всех перестановок из 5 чисел и делит его надвое при помощи результата одного сравнения. Сравнение выбирается так, чтоб две части были максимально близки по размеру. Потом каждая из частей тоже делится пополам итп.

А потом я прикинул и понял, что простой merge sort тоже подойдет.

Делишь числа на группу из двух и группу из трех. Сортируешь их по отдельности. (3 числа сортируется за 1 сравнение, 3 числа - за 3). Потом обе группы сливаются в одну. Это еще максимум 3 сравнения. Итого как раз 7.

(Reply to this) (Thread) (Expand)

а логарифм чисел можно брать?

(Reply to this) (Thread) (Expand)

Бинарный поиск среди 5! перестановок.

(Reply to this) (Thread) (Expand)

И решать ее проще именно в терминах есть весы и 5 гирек разных по весу. Задача простая, IMHO.

(Reply to this) (Thread) (Expand)

Для начала: 5 чисел могут лечь в ряд 5! = 120 вариантами.
7 взвешиваний рассекают 2^7 = 128 вариантов
Должны успеть.

Тактика решения подобных задач: каждое рассечение вариантов как можно ровней, чтобы после рассечения множества вариантов не делились на "удачное" и "неудачное". Идеально, если рассечение бьет множество симметрично. Тогда не надо рассматривать различные исходы.

Поехали:

A, B, C, D, E

1. A ? B
A < B

2. C ? D
A < B
C < D

3. B ? D
A   <   B
      < 
C < D

4.a. D ? E

A   <   B
      <
C < D
E <

5.a. C ? E

        A < B
          <
C < E < D

далее A за два сравнения доставляем в ряд C,E,D,B

4.b. D ? E

    A < B
      <
C < D < E

5.b. B ? E

        A <
C < D < E < B

или
    A <
C < D < B < E

в любом случае доставляем A за два сравнения

(Reply to this) (Thread) (Expand)

Выбираем две пары 1 и 2. Упорядочиваем каждую за 2 сравнения: m1<M1, m2<M2.
Сравниваем M1 и M2 (3ье сравнение). Без ограничения общности можно считать, что M2 больше:

m1 < M1
     ^
m2 < M2

Сравниваем теперь оставшееся ещё неиспользованным пятое число (x) с M1. Возможны 2 варианта:
(1)

m1 < M1 < x
     ^
m2 < M2

(2)

     x
     ^
m1 < M1
     ^
m2 < M2

Легко видеть, что оставшихся трех сравнений достаточно, чтобы сделать эти частичные порядки полными.

(Reply to this) (Thread) (Expand)

отсоротровать 3 числа (3 сравнения), оставшиеся 2 (одно). сравнить минимум из двух с максимумом трех (одно). если больше - все. если меньше - сравнить максимум двух с минимумо трех (одно). если меньше - все. если больше - сравнить два со средним их трех (два).

(Reply to this) (Thread) (Expand)

Разделим 5 чисел на группы:
A,B - группа1, C, D - группа 2, Е - группа 3

Далее, предположим, что "победитель" группы - который больше. Тогда максимум можно выбрать за 4 сравнения:
А,B -> Win1
-> Win3
C,D -> Win2
-> Win4
E

И вот здесь вопрос: могу ли я проверить, что Win4 "is" Win3?

(Reply to this) (Thread) (Expand)

i understand that swapping places etc is allowed?

(Reply to this) (Thread) (Expand)

AB, DE, BD, BC, CD , AB, DE.

(Reply to this) (Thread) (Expand)

Метод вставки

(Reply to this) (Thread)

Метод вставки дает 9, сорри

(Reply to this) (Thread)