back to basics

[thedeemon]

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

sort(xs); return (xs[1], xs[6]);

Надо это сделать за минимальное число действий. Под действиями подразумеваются сравнения, ну и копирования с перестановками, хотя сравнения важнее. На особенности современного железа и его наборов инструкций пока положим, интересует классический теоретический подход. Как положено подходить к решению? Массив можно менять на месте, можно использовать дополнительную память. Я знаю, как это сделать за 14 сравнений. Можно ли за меньшее число? Можно ли доказать, что за меньшее нельзя?

Comments

[worm-ii.livejournal.com]

По грубым подсчётам, для перебора всех алгоритмов, использующих 13 сравнений, надо будет перебрать 26!/(15!) алгоритмов (учёл некоторые симметрии между алгоритмами, но не все), и каждый из них прогнать для 8! вариантов расположения чисел. Итого порядка 10^18 вариантов. Ну, если более вдумчиво использовать симметрии между алгоритмами, наверное, несколько порядков можно будет ещё скинуть. Вполне подъёмная задача для суперкомпьютера, или кластера из множества персоналок. Зато будет получено строгое доказательство, что за 13 сравнений решить задачу нельзя. Ну, или будет найдено решение из 13 сравнений.