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

← →
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 будет легко сделать.

← →
Sandman25 © (2005-01-21 14:25) [29]

[28] MBo © (21.01.05 14:22)

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

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

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);

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

Думкин © (21.01.05 14:35) [30]
я тоже так думал, но это несерьёзно, не работает для всех N
вообщем оли рекурсия

← →
Sandman25 © (2005-01-21 14:40) [32]

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

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

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

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

← →
MBo © (2005-01-21 14:46) [34]

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

← →
wal © (2005-01-21 14:58) [35]

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

С уважнием.

← →
Sandman25 © (2005-01-21 15:04) [36]

Тогда уже можно и универсальную сделать, только с ограничением по максимуму.
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]);

← →
ferr © (2005-01-21 15:05) [37]

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

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

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

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

← →
default © (2005-01-21 15:12) [39]

Sandman25 © (21.01.05 15:04) [36]
ага, прикольно, двоичными весами нужное число строк набирать

← →
Алхимик © (2005-01-21 15:18) [40]

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

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

← →
ferr © (2005-01-21 15:20) [41]

[38]
нет. Он не получил никакой информации.

← →
default © (2005-01-21 15:22) [42]

ferr © (21.01.05 15:20) [41]
обоснуй
а я скажу что получил, и кто прав?!
нужно обосновать

← →
Cosinus © (2005-01-21 15:23) [43]

По логике нет, а по раскладу, да.
Х-Жив, Y,Z-казнены
Y-Жив, X,Z-казнены
Z-Жив, X,Y-казнены

X-Жив, Y,Z-казнены
Z-Жив, X,Y-казнены

Если я правильно понимаю, это уже минимум два раза здесь обсуждалось, что то там с "Поле чудес" и еще какой-то пример. Ветка разраслась тогда немерянно(обе;)). Опять же насколько я помню, народ вроде убедили, что вероятность все же меняется.

Sandman25 © (21.01.05 15:25) [45]
почему?
было три расклада
вероятность того что будет определённый расклад 1/3
он выживает в одном из трёх раскладов
то есть сначала его шансы 1/3
после инфы стало два расклада оба равновероятны независимы и составляют полную группу
в одном из них он останется жив
значит шансы стали 1/2
возросли в 1.5 раза

> Sandman25 © (21.01.05 15:25) [45]

По моему задача ничем не отличается от задачи с открытием дверей. А там пришли к мнению, что меняется.

1)X-спасен, Y-называет
2)XZ
3)YZ
4)YX
5)ZX
6)ZY

Все шансы 1/6.
Y назвать не могут, поэтому реально имеем
2)XZ (шанс 1/3, так как вариант 1 превращается в данный)
3)YZ (1/6)
4)YX (1/6)
5)ZX (шанс 1/3 из-за варианта 6)

Охранник назвал X.
Остается только
4)YX (1/6)
5)ZX (шанс 1/3 из-за варианта 6)

Все равно шанс, что спасен Y, в 2 раза меньше шанса, что спасен Z.
То есть равен 1/3.
Шансы изменились только для X и Z. 1/3 на спасение от X перешли к Z.

А если без теории, то если в прошлой задаче выбор не менять, то вероятность выиграть не поменяется. В новой задаче выбор не меняется, Y не может стать Z.

Sandman25 © (21.01.05 15:50) [48]
согласен что не поменяется, но это в условии равновероятности выбора охранником казнимого среди Y и Z когда они оба будут казнены

X Y Z
К К Ж
К Ж К
Ж К К

при первом раскладе вер-ть которого 1/3 охранник назовёт Y
при втором раскладе вер-ть которого 1/3 охранник назовёт Z
пусть при третьем раскладе вер-ть которого 1/3 охранник называет
Y с вероятностью P1, а Z - с вероятностью P2(P1+P2=1 поскольку
кого-то он обязательно назовёт)
вероятость того что будет назван Y при первом раскладе равна 1/3
вероятость того что будет назван Y при третьем раскладе равна
(1/3)*P1
то есть в (1/3)/[(1/3)*P1]=1/P1 раз чаше будет назван Y при первом раскладе чем при втором
после получения информации о том что будет казнён Y
получаем (1/P1)*X+X=1, где X - вероятность что Y назван при третьем раскладе то есть это вероятность выживания
отсюда X=P1/(P1+1)
когда выполнено [49] то есть при P1=1/2 X=1/3
то есть шансы не меняются

[51] default © (21.01.05 16:46)

В предыдущих постах я спутал X и Y. С точки зрения выживаемости X его не интересует величина P1 в третьем раскладе. Он все равно жив останется.

Sandman25 © (21.01.05 16:51) [52]
не понял твой пост [52](
выживаемость X как раз определяется тем как часто выбирает охранник Y при третьем раскладе
он называет только Y или Z
это ничего не меняет
задача в сущности не определена поскольку не понятно охранник всегда называет Y если имеетрся третий расклад(P1=1-->X=1/2 и верны рассуждения [46]) либо 50/50, P1=1/2-->X=1/3 и шансы не меняются)главно формула X=P1/(P1+1) получена больше тут в принципе искать нечего...

строку "это ничего не меняет" надо выкинуть из поста

Sandman25 © (21.01.05 17:25) [55]
зависит...
она сначала 1/3 потом же она зависит от P1
то есть к примеру из 99 случаев охранник назовёт Y из первого расклада в 66 случае, а в третьем в 33, то есть и шансы выжить будут в два раза меньше то есть X+X/2=1, X=2/3

в [56] посте X это вероятность откинуть коньки

[56] default © (21.01.05 17:30)

Можно с точки зрения симметрии попробовать. Переименуй Z в Y, а Y в Z и докажи, что выживаемость X от этого изменилась.

Sandman25 © (21.01.05 17:35) [58]
допустим имеется 99 опытов
из них по 33 появился каждый расклад
в 33 случая соответ-их второму раскладу Y попросту не может быть назван
в 33 случаях соответ-их первому раскладу Y будет назван во всех 33 разах
допустим что при третьем раскладе охранник называет Y лишь в трети случаев то есть в 11 случаях соответ-их третьему раскладу будет назван Y а не Z
таким образом всего мы получили 33+11=44 случаев называния Y
из них 33 соответ-ют первому случаю а лишь одиннадцать третьему
то есть вер-ть что Y из третьего расклада равна 11/44=1/4
то есть выживает X в одном случае из 4

← →
UUU (2005-01-21 18:25) [60]

С охранником все очень просто. X и так знал, что или Y или Z казнят (если Y казнят ему от этого лучше не станет, и если Z казнят его шансы тоже не возростут), следовательно охранник не дал никакой информации (нужной).

UUU (21.01.05 18:25) [60]
этим и интересна теория вероятности - она часто обламывает интуитивные выводы

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