Эврика! Наконец-то я нашёл линейный алгоритм пятничной задачки!

← →
default © (2005-01-21 04:49) [0]

Задача:

"Есть массив, упорядоченный по возрастанию, например, 0123456789
Надо его переупорядочить "горкой в центре": 0246897531
Цифры приведены для примера, на самом деле массив может быть любой заданной длины N,
и числа там тоже любые, только что упорядоченные.
Основная проблема - сделать это за время O(N) с затратами памяти меньшими, чем O(N).
Решение лучше всего оформить в виде процедуры ReOrder(var a:array of Integer);"

вот код:

procedure ReOrder(var X: Array of Integer); var i, j, k, c: Cardinal; t: Integer; begin if Length(X) < 3 then Exit; k := High(X); j := 1; c := 1; repeat Inc(c); t := X[j]; X[j] := X[k]; X[k] := t; if Odd(k) then k := High(X) - k div 2 else k := k div 2; if (k = j) and (c < High(X)) then begin Inc(c); repeat Inc(j, 2); k := High(X) - j div 2; if X[j] < X[k] then Break; until j >= High(X); end; until c = High(X) end;

потестить можно кодом:

procedure TForm1.Button1Click(Sender: TObject); var X: Array of Integer; i, j: Cardinal; begin for j := 3 to 10000 do begin SetLength(X, j); for i := 0 to High(X) do X[i] := i; ReOrder(X); for i := 0 to High(X) div 2 do if X[i] <> 2 * i then begin Caption := "BAD"; Exit end; for i := High(X) downto High(X) div 2 + 1 do if X[i] <> 2 * (High(X) - i) + 1 then begin Caption := "BAD"; Exit end; end; Caption := "GOOD"; {SetLength(X, 16); for i := 0 to High(X) do X[i] := i; ReOrder(X); Caption := ""; for i := 0 to High(X) do Caption := Caption + IntToStr(X[i]) + " "} end; P.S. саму идею в двух словах не расскажешь, можно попытаться по коду понять родился он как смесь случайности и догадки которая подтвердилась

← →
MBo © (2005-01-21 08:23) [1]

Поздравляю! Эффективность решения впечатляет.
При простоте формулировки задача, как мне кажется, нетривиальная.
Основные моменты - нахождение позиции обмена (k) в зависимости от четности и новой стартовой позиции (j), до которой все уже готово. Уу тебя эта часть, насколько я разобрался, крутится от 0 до почти N/2 (в зависимости от размерности сильно меняется) раз, а у меня в ней количество операций всегда порядка N/2. Я пытался реализовать аналог твоего Inc(j, 2);, но не удалось найти приемлемого условия

← →
NewDelpher © (2005-01-21 09:17) [2]

Я бы div 2 заменил на shr 1

← →
Alx2 © (2005-01-21 09:20) [3]

>NewDelpher © (21.01.05 09:17) [2]
Без разницы

← →
MBo © (2005-01-21 09:20) [4]

>NewDelpher © (21.01.05 09:17) [2]
Компилятор часто сам это делает.

Есть еще программистcкая похожая задачка, вроде попроще. Нужно?

← →
NewDelpher © (2005-01-21 09:39) [5]

> MBo © (21.01.05 09:20) [4]

конечно

← →
default © (2005-01-21 09:41) [6]

MBo © (21.01.05 08:23) [1]
да уж задачка нехилая
я приличное число дней над ней думал
и самое интересное решение родилось не как результат планомерного анализа, а...да по сути случайно!
даже зацепка за то что в условии дана возрастающая послед-ть мало что дают - можно было предположить что где-то что-то сравнением должно решаться - но это предположение без догадки нужного способа перестановки не фига не даёт
а догадка этой перестановки - случайность - ну почти...

← →
Sandman25 © (2005-01-21 09:52) [7]

default © (21.01.05 04:49)

Офигеть! Поздравляю.
Я даже с отладчиком не понял идею :)
То есть примерно понял, но не понимаю, как можно придумывать такие алгоритмы :)

← →
default © (2005-01-21 09:55) [8]

Sandman25 © (21.01.05 09:52) [7]
я сам думал щас на какой-нибудь длине массива будет облом
и НЕТ!думал наконец-то, а то столько времени потратил
всё-таки идею давайте изложу если интересно(

← →
Sandman25 © (2005-01-21 10:18) [9]

[8] default © (21.01.05 09:55)

Давай, конечно, интересно!

← →
default © (2005-01-21 11:21) [10]

рассмотрим идею алгоритма на примере массива длины 16 элементы которого принимают значения по возрастанию следующим образом(для простоты):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
задача состоит в получении перестановки:
0 2 4 6 8 10 12 14 15 13 11 9 7 5 3 1
1)нулевой элемент массива(индексацию начинаем с 0) уже занимает своё конечное место поэтому его не трогаем(не сам элемент, а его значение, но это не принципиально поэтому в дальнейшем буду говорить так, сам элемент физически конечно неподвижен к тому же
можно представлять массив как набор бумажных карточек со значениями, которые можно как угодно переставлять)
2)теперь меняем местами первый элемент массива с последним
получим:
0 15 2 3 4 5 6 7 8 9 10 11 12 13 14 1
0 2 4 6 8 10 12 14 15 13 11 9 7 5 3 1
то есть последний элемент массива тот который и должен быть в конечной перестановке
на данный момент свои места заняли два элемента
3)теперь меняем местами первый элемент массива с восьмым
получим:
0 8 2 3 4 5 6 7 15 9 10 11 12 13 14 1
0 2 4 6 8 10 12 14 15 13 11 9 7 5 3 1
то есть восьмой элемент массива на нужном месте
на данный момент свои места заняли три элемента

то есть фактически мы сейчас зацепились за элемент массива с индексом 1 и меняем его с другими элементами для установки элементов на нужные места покуда сможем
это значит что мы будем переставлять до возникновения ситуации когда нужно будет переставлять первый элемент с первым - то есть когда первый элемент окажется на своём месте, но тут возникает сложность - в подобные моменты могут не все элементы находиться в нужных местах и казалось бы неизвестно за какой элемент потом зацепляться - за второй?а вдруг он уже на своём месте и мы только этим всё испортим, за третий?эту проблему мы решим использую то что элементы идут в порядке возрастания
а то как определять какой элемент куда должен быть переставлен
видно из строки "if Odd(k) then k := High(X) - k div 2 else k := k div 2;", где k - индекс элемента массива, это просто понять

пока будем просто переставлять
4)теперь меняем местами первый элемент массива с четвёртым
получим:
0 4 2 3 8 5 6 7 15 9 10 11 12 13 14 1
0 2 4 6 8 10 12 14 15 13 11 9 7 5 3 1
то есть четвёртый элемент массива на нужном месте
на данный момент свои места заняли четыре элемента
5)теперь меняем местами первый элемент массива со вторым
получим:
0 2 4 3 8 5 6 7 15 9 10 11 12 13 14 1
0 2 4 6 8 10 12 14 15 13 11 9 7 5 3 1
то есть второй элемент массива на нужном месте
на данный момент свои места заняли пять элементов
(второй элемент не будем считать установленным так как мы его лишь косвенно установили - так сказать случайно он так быстро на своё место попал)
6)теперь меняем местами первый элемент массива с первым
получим:
0 2 4 3 8 5 6 7 15 9 10 11 12 13 14 1
0 2 4 6 8 10 12 14 15 13 11 9 7 5 3 1
то есть первый элемент массива на нужном месте
на данный момент свои места заняли шесть элементов
вот как раз та ситуация о которой я говорил ранее!
надо как-то выбрать за какой элемент будем цепляться следующим!
будем пробовать по-порядку - слева-направо
то есть мы должны сейчас как-то решить цепляться-ли за элемент с индексом 2 либо пропускать и пробовать другой
очевидно это должно зависеть от того на своей-ли позиции стоит элемент с индексом 2
но тут можно увидеть оптимизацию, то самое Inc(j, 2) о котором говорил MBo!
дело в том что элементы с чётными индексами мы можем при поиске элемента зацепки не брать во внимание
к примеру: если закончилась зацепка элемента с индексом 3 то очивидно(что следует из процедуры перестановки) что зацеплены 0, 1 и 2 элементы, а элемент с индексом 4 должен занимать позицию 2 но она уже зацеплена - так что он уже на своём месте
так что перебираем только нечётные элементы
для нечётного элемента вычисляем позицию куда он должен быть переставлен и если элемент в этой нечётной позиции меньше элемента в позиции куда он должен быть переставлен то третий элемент не на своём месте и мы цепляемся за него иначе проверяем на зачепку элемент с индексом 5(4-ый чётный номер игнорируем как невозможный для зацепки)
почему это так несложно сообразить
ну вот вообщем-то и всё
в нашем примере элемент с индексом три должен быть поставлен в позицию 14 и X[3]=3, X[14]=14 X[3]<X[14] так что цепляемся за элемент с индексом три и так далее

← →
Sandman25 © (2005-01-21 11:39) [11]

[10] default © (21.01.05 11:21)

Большое спасибо!
Очень понятно и логично. Поневоле начинаешь чувствовать себя глупым, что не смог сам такое придумать :)
Главное было догадаться, что нужно переставлять 1 с 15, потом с 8, потом с 4 и наконец с 2. Дихотомия какая-то, класс!

← →
КаПиБаРа © (2005-01-21 11:55) [12]

А еще можно в обратном порядке переставлять
по закону
function GetNewK(t: Integer): Integer;
begin
if t > mid then
Result := (n - t) * 2 + 1
else
Result := t * 2;
end;

например
0 1 2 3 4 5 6 0 2 1 3 4 5 6 0 2 4 3 1 5 6 0 2 4 3 5 1 6 0 2 4 1 5 3 6 0 2 4 6 5 3 1

В этом случае по массиву перемещается только первый элемент первый элемент. Зная это можно секономить на одном присваивании.

← →
default © (2005-01-21 12:09) [13]

Sandman25 © (21.01.05 11:39) [11]
да уж
тут на возенение
если начнёшь переставлять таким способом то можно найти решение а так можно дофига голову ломать

← →
MBo © (2005-01-21 12:22) [14]

Еще задачки:

1. Дан массив, содержащий некоторую перестановку чисел 0.. N-1
Отсортировать его за О(N) операций и с O(1) доп. памяти.

2. Пусть получение случайного числа - сильно затратная операция.
Нам требуется заполнить случайными числами треугольник. Найти хороший алгоритм (даны 3 точки - координаты вершин)

3. Написать программу, 100 (или другое большое число) раз выводящую строку "Hello, world!", не использующую циклов и goto.

Задачки, которые были несколько лет назад, но могут представлять определенный интерес, и не особо сложные. Рекомендую подумать над задачами начинающим:

4. Нарисовать на форме яйцо (не эллипс!)

5. Создать простой аналог скринсейвера "Геометрический вальс" (Marquee, кажется, в англ. версии виндов) - т.е. на форме PaintBox или TImage, и летает четырехугольник (можно из двух линий)

6. Написать программу, выводящую разложение на множители чисел до 10000 в виде
6=2*3
7=простое

← →
MBo © (2005-01-21 12:24) [15]

>Sandman25 © (21.01.05 11:39) [11]
Метод резиновой бомбы ;))

← →
MBo © (2005-01-21 12:35) [16]

Пардон, во 2 задаче фигню написал.
Вместо:
>Нам требуется заполнить случайными числами треугольник.
должно быть:
Требуется заполнить треугольник равномерно распределенными случайными точками
function GetRndPointInTriangle(pA,pB,pC:TPoint):TPoint;

← →
Sandman25 © (2005-01-21 12:39) [17]

3. Написать программу, 100 (или другое большое число) раз выводящую строку "Hello, world!", не использующую циклов и goto.

function hello(I: integer)
begin
if I < N then
begin
writeln(S);
hello(I-1)
end
end;

← →
Sandman25 © (2005-01-21 12:40) [18]

Торможу.

function hello(I: integer)
begin
if I > 0 then
begin
writeln(S);
hello(I-1)
end
end;

← →
Sandman25 © (2005-01-21 12:40) [19]

[15] MBo © (21.01.05 12:24)

Похоже :)

← →
MBo © (2005-01-21 12:43) [20]

>Sandman25 © (21.01.05 12:40) [18]
ОК, один способ - с рекурсией - найден.
Есть по крайней мере еще один принципиально отличный.

← →
default © (2005-01-21 13:28) [21]

MBo © (21.01.05 12:43) [20]
WriteLn("Hello, world!");
WriteLn("Hello, world!");
WriteLn("Hello, world!");
и так 100 раз
принципиально другой подход!
1.
это задача шутка что-ли?
for i := 0 to High(DynArray) do DynArray[i] := i

← →
MBo © (2005-01-21 13:49) [22]

>default © (21.01.05 13:28) [21]
нет, 100 раз Writeln не пойдет. Задача должна решаться и для миллиона.

>это задача шутка что-ли?
Ну и в предыдущей можно таким образом заполнить без труда. Нужен честный путь ;)

← →
Думкин © (2005-01-21 14:05) [23]

1. program Project1;

{$APPTYPE CONSOLE}

uses
SysUtils;

var s,s1 : string;
begin
SetLength(s,3);
FillChar(s[1],3,"1");
s1 := StringReplace(s,"1","Hello, World!"+#13#10,[rfReplaceAll]);
writeln(s1);
readln
end.

← →
default © (2005-01-21 14:14) [24]

Думкин © (21.01.05 14:05) [23]
в подпрограмме всё-равно цикл есть

← →
Думкин © (2005-01-21 14:14) [25]

Ну это 3. конечно. И 3 можно заменить на 100. :)

← →
Думкин © (2005-01-21 14:16) [26]

> [24] default © (21.01.05 14:14)

Ну...условия то решения не прописаны. Или нет?

← →
default © (2005-01-21 14:20) [27]

Думкин © (21.01.05 14:16) [26]
можно было самому подобную подпрограмму написать и вызвать
но может в этой задаче стандартные подпрограммы можно использовать фиг знает
хотя наверно это старая задача и рассчитана на Турбо Паскаль в частности, а там такой подпрограммы я не помню

← →
MBo © (2005-01-21 14:22) [28]

>Думкин
хитрый ;)
Есть все же путь еще один. Для каждого конкретного числа, правда, программа будет слегка отличаться.
Наводка - для N=256 будет легко сделать.

[28] MBo © (21.01.05 14:22)

Ага, количеством строк с writeln. Нет уж, либо программа работает с любым N, либо она не работает.

s := "Hello, World!"+#13#10;
s := s + s + s + s;
s := s + s + s + s;
s := s + s + s + s;
s := s + s + s + s;
writeln(s);

Я пытался использовать OnException, в котором возникало деление на 0, но выяснилось, что внутри OnException генерировать Exception нельзя.

> [31] default © (21.01.05 14:37)

Я исходя из подсказки. Исключительно. Что программы будут отличаться - слегка. Записываем чсило в двоичном и пишем новую программу. Ясно, что камнями бить можно. :)

Sandman25 © (21.01.05 14:25) [29]
default © (21.01.05 14:37) [31]
Я как раз имел в виду способ типа Думкин © (21.01.05 14:35) [30]
Не слишком общо, но забавно...

3. код писать не буду, на словах.
Программа запускается с параметром п, если параметра нет, считаем, что п=1
Пргограмма проверяет, если п больше 100, то выход, иначе вывод хеловорда и запуск себя с параметром п+1.

С уважнием.

Тогда уже можно и универсальную сделать, только с ограничением по максимуму.
var Hello: array[0..3] of string;

Hello[0] := "hello"#13#10;
Hello[1] := Hello[0] + Hello[0];
Hello[2] := Hello[1] + Hello[1];
Hello[3] := Hello[2] + Hello[2];
if N and 1 > 0 then
writeln(hello[0]);
if N and 2 > 0 then
writeln(hello[1]);
if N and 4 > 0 then
writeln(hello[2]);
if N and 8 > 0 then
writeln(hello[3]);

Возможно 1-ое так. Выглядит не сложно. Где собака?
812304657
712304658
512304678
412305678
012345678

Начальник тюрьмы выбрал одного из трёх заключённых
X, Y и Z, чтобы отпустить его на волю. Остальные двое будут казнены. Страж знает, кто из троих выйдет на свободу, но не имеет права сообщать никакому из узников информацию о его судьбе.
Заключённый X просит стража назвать ему имя одного из заключённых Y или Z, который будет казнён, объясняя, что ему и так известно, что один из них точно будет казнён, а, значит он не получит никакой информации о своей судьбе. Страж сообщает X, что Y будет казнён. Заключённый X радуется, считая, что его шансы остаться в живых возросли до 1/2(освобождён будет или он, или Z). Прав ли он?

вот тоже забавная задачка хоть и очень простая

> 5. Создать простой аналог скринсейвера "Геометрический вальс"
> (Marquee, кажется, в англ. версии виндов) - т.е. на форме
> PaintBox или TImage, и летает четырехугольник (можно из
> двух линий)

Чистааа для разминки
http://www.karat.aero/geometria.rar

Эврика! Наконец-то я нашёл линейный алгоритм пятничной задачки! Найти похожие ветки