Вроде когда-то давно мне попадалась именно такая олимпиадная задача.
Вот её условие:
| Цитата | "Интеллект против QSort"
Для сортировки последовательности чисел широко используется быстрая сортировка - QSort. Ниже приведена программа, которая сортирует массив a, используя данный алгоритм.
Хотя QSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго.
Будем оценивать время работы алгоритма количеством сравнений, сделанных с элементами массива (т.е. суммарным количеством сравнений в первой и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
| Код | procedure QSort(left, right : integer);
var m, i, j, t : integer;
begin
m := a[(left+right) div 2];
i := left; j := right;
repeat
while a[i] < m do inc(i); {первый while}
while a[j] > m do dec(j); {второй while}
if i <= j then
begin
t := a[i]; a[i] := a[j]; a[j] := t;
inc(i); dec(j);
end;
until i > j;
if j > left then QSort(left, j);
if i < right then QSort(i, right);
end; |
|
Не знаю как решали эту задачу другие, а я написал перебор, выдающий все такие "плохие" перестановки, и долго вкуривал их. Через пару часов выявил одну из закономерностей, и закодил её:
| Код | int n;
cin >> n;
vector<int> a (n);
if (n == 1)
a[0] = 1;
else if (n == 2)
(a[0] = 1), (a[1] = 2);
else if (n == 3)
(a[0] = 2), (a[1] = 1), (a[2] = 3);
else
{
a[1] = 1; a[2] = 3;
for (int step=4; step<=n; step++)
if ((step & 1) == 0)
a[step-1] = a[(step>>1)-1];
else
{
a[step-1] = a[step>>1];
a[step>>1] = step;
}
for (int i=0; i<(n>>1); i++)
a[i] = i+i+2;
}
for (int i=0; i<n; i++)
printf ("%d ", a[i]); |
|
)