Задачка для разминки мозга

← →
SergP © (2014-04-22 15:27) [200]

> Те же условия, решить задачу для неизвестного числа дубликатов
> D=0..3.

Если среди недубликатов нет нулевых, и самих недубликатов не более 3 то ИМХО можно за 1 проход вычислить их, но сам проход будет аналогичен [197], т.е.
for i:=low(Arr) to high(Arr) do for j:=0 to 8 do if odd(Arr[i] shl j) then d[j]:=d[j] xor Arr[i];
только дальше придется подумать...

← →
Sha © (2014-04-22 16:56) [201]

> SergP © (22.04.14 15:27) [200]

если еще чуть дальше подумать, то и нулевой недубликат ничем не мешает )

← →
SergP © (2014-04-22 17:14) [202]

> Sha © (22.04.14 16:56) [201]
>
> > SergP © (22.04.14 15:27) [200]
>
> если еще чуть дальше подумать, то и нулевой недубликат ничем
> не мешает )

Хотя да... Если четность размерности массива совпадает с четностью количества ненулевых недубликатов то значит нулевого дубликата нет, иначе он есть.

← →
Дмитрий СС (2014-04-22 23:38) [203]

> SergP © (22.04.14 11:36) [197]

Я подобный вариант публиковал уже для любых чисел

← →
имя (2014-04-23 10:58) [204]

Удалено модератором

← →
Sha © (2014-04-24 11:41) [205]

тут решение для задачи поиска в массиве 0..3 непарных чисел
http://guildalfa.ru/alsha/node/29

← →
MBo © (2014-04-24 13:26) [206]

>Sha
Не очень хорошо xor называть побитовым сложением - всё же этот термин для or, а "по модулю 2" у тебя не фигурирует. Туда же и неоднократно используемая "cумма" массива.

← →
Sha © (2014-04-24 13:27) [207]

> MBo © (24.04.14 13:26) [206]

Спасибо, исправлю.

← →
Sha © (2014-04-25 09:37) [208]

Для тех, кто все правильно сделал, еще одна пятничная задача:

За один проход по элементам целочисленного массива найти 0..4 непарных числа

← →
имя (2014-04-25 10:39) [209]

Удалено модератором

← →
Sha © (2014-04-25 11:00) [210]

Удалено модератором

← →
имя (2014-04-25 11:03) [211]

Удалено модератором

← →
Гора Фудзияма (2014-04-25 11:16) [212]

Удалено модератором

← →
Sha © (2014-04-25 11:16) [213]

Удалено модератором

← →
Sha © (2014-04-25 11:24) [214]

Удалено модератором

← →
имя (2014-04-25 11:32) [215]

Удалено модератором

← →
Гора Фудзияма (2014-04-25 11:36) [216]

Удалено модератором

← →
Sha © (2014-04-25 11:37) [217]

Тогда, скажи, о чем?
Я теряюсь в догадках, может о том, что O(32*N)=O(N*32)=O(N).
Задай развернутый вопрос.

← →
Гора Фудзияма (2014-04-25 11:39) [218]

> Sha © (25.04.14 11:37) [217]

По твоей логике если итерации не проходят непосредственно по исходному массиву - то решение удовлетворяет условию
Формально да
Но по такой же логике я могу решить задачу в 0 итераций. По-моему просто нужно признать свою ошибку. Представленное тобой решение для 2х элементов выполняется неэффективно и выполняет не за 1 проход

← →
Гора Фудзияма (2014-04-25 11:40) [219]

*в 0 проходов

← →
Sha © (2014-04-25 11:45) [220]

> Гора Фудзияма (25.04.14 11:39) [218]
> я могу решить задачу в 0 итераций.

Код давай.

> Представленное тобой решение для 2х элементов выполняется неэффективно

Предложи более эффективное решение для пары терабайт данных на диске.

> и выполняет не за 1 проход

Вот это бред.

← →
Гора Фудзияма (2014-04-25 11:58) [221]

> Предложи более эффективное решение для пары терабайт данных
> на диске.

для пары терабайт действительно твой алгоритм вне конкуренции
для вменяемых ситуаций любое решение на основе хешей будет эффективней
можно скомбинировать пару алгоритмов, неплохо будет смотреться основа radix-сортировки если сделать по уму

> Вот это бред.

Ну хорошо, ты хочешь чтобы я согласился с формальным О(N)? Никто ведь не спорит. Но во-первых, оценка O(N) мегаупрощенная, а во-вторых, по условию задачи нужно сделать 1 проход; а проходы по служебным массивами, коих у тебя, если не ошибаюсь N+2 - тоже проходы.

> Код давай.

Move(PMyElement^, TempBuffer^, count*sizeof(TMyElement)); // теперь проходы по исходному массиву не нужны

← →
Sha © (2014-04-25 12:22) [222]

> для вменяемых ситуаций любое решение на основе хешей будет эффективней
> можно скомбинировать пару алгоритмов, неплохо будет смотреться
> основа radix-сортировки если сделать по уму

Код давай, с учетом ограничения O(1) на память.

> а проходы по служебным массивами,
> коих у тебя, если не ошибаюсь N+2 - тоже проходы.

Ошибаешься несколько раз.
Повторяться не буду.

> теперь проходы по исходному массиву не нужны

Ты код System.Move видел?

← →
Гора Фудзияма (2014-04-25 12:38) [223]

> Ошибаешься несколько раз.
> Повторяться не буду.

1 проход
for i:=0 to LastBitNo do Sum[i]:=0;

N проходов
q:=p; inc(q,count); //адрес за пределами массива repeat; t:=1; for i:=0 to LastBitNo do begin; //изменяем сумму, при этом инвертируется значение бита-счетчика if p^ and t<>0 then Sum[i]:=Sum[i] xor p^; t:=t+t; end; inc(p); until p=q;

ещё 1
while (i<=LastBitNo) and (Sum[i] and t=0) do begin; //ищем взведенный бит-счетчик inc(i); t:=t+t; end;

и ещё один
repeat; if Sum[i] and t<>0 then Res[0]:=Res[0] xor t; inc(i); t:=t+t; until i>LastBitNo; end;

или что не for уже проходом не является? )))

> Ты код System.Move видел?

Конечно видел
Но согласно твоей логике это проходом не является

> Код давай, с учетом ограничения O(1) на память.

Насколько я понял, расход памяти был не обязательным, а желательным
И потом кто мешает сделать хеш с размером например N/2? Сложности не вижу

P.S. я не пойму, что тебя смущает. Предложенное тобой решение не самое эффективное и производит много проходов. Формально сложность алгоритма O(N). Только на практике профит сомнительный, ибо каждый элемент гарантировано пройдёт минимум 32 итерации. Иначе говоря ты утверждаешь, что
for i := 1 to N do for j := 1 to 32 do

не эквивалентно
for j := 1 to 32 do for i := 1 to N do

Формально да. Но кому нужны формальности?

← →
Sha © (2014-04-25 13:10) [224]

> Гора Фудзияма (25.04.14 12:38) [223]
> 1 проход
> for i:=0 to LastBitNo do Sum[i]:=0;

Это не проход по элементам ИСХОДНОГО массива.
В исходном массиве может быть триллион элементов на диске,
проход по нему займет на порядки больше тех наносекунд,
которые нужны, чтобы обнулить 32 суммы.

> N проходов ...

Ответил уже раньше:
это компилируется в 1 проход по элементам исходного массива.
Ты в этом уже убедился? И теперь заклинаешь компилятор?

> ещё 1...
> и ещё один

Это опять не проход по элементам ИСХОДНОГО массива.

>> Ты код System.Move видел?
> Конечно видел
> Но согласно твоей логике это проходом не является

Разве там не перебираются все элементы ИСХОДНОГО массива?
Но согласно твоему пониманию моей логики это проходом не является.

>> Код давай, с учетом ограничения O(1) на память.
> Насколько я понял, расход памяти был не обязательным,
> а желательным
> И потом кто мешает сделать хеш с размером например N/2?
> Сложности не вижу

См. [127].
Это самое N и мешает, когда N=10^9. И чем это лучше битовой карты?

> ... Но кому нужны формальности?

Мне. Чтобы не шерстить 32 раза огромный файл.

← →
Гора Фудзияма (2014-04-25 14:30) [225]

> Ega23 © (17.04.14 00:06) [36]

function Foo(arr: array of Integer): Integer; var i: Integer; begin Result := arr[0]; for i := 1 to Length(arr) - 1 do Result := Result xor arr[i]; end;

Итак:
Есть массив чисел. Размер массива 2N+2. В этом массиве 2N дубликаты, а два значения уникально. Надо написать код, который найдет значение этого уникального числа за одну итерацию, т.е. за один проход. Пример ряда: "3, 1, 5, 6, 1, 3".
В этом ряду {3, 3}, {1,1} дубликаты, а 5б 6 — уникальные.

Попросили уточнить требования про два уникальных числа в массиве дубликатов.
Числа целые 32 или 64 разряда.
Хорошо бы решить за линейное время O(n) и с O(1) дополнительной памяти.
(т.е. один или несколько проходов по массиву допустимы, и несколько вспомогательных переменных, но не, например, массив из n битов)

Насколько я понял, нужно сделать типа того, что сделал Ega23. Т.е. ВООБЩЕ в один проход. Но okey, если MBo допускает тысячу вложенных циклов - то решение значительно проще, чем я предполагал.

> Ответил уже раньше:
> это компилируется в 1 проход по элементам исходного массива.
>
> Ты в этом уже убедился? И теперь заклинаешь компилятор?

jnz -$10
jnz -$27

где ты умудрился увидеть один проход - я не знаю. Ни теоретически, ни практически. p^ кешируется в регистре. Почему по твоей логике N*32 стало не равно 32*N - я не знаю.

> Это самое N и мешает, когда N=10^9. И чем это лучше битовой
> карты?
> Мне. Чтобы не шерстить 32 раза огромный файл.

Твой алгоритм хорош тем, что вообще не потребляет дополнительной памяти в нотации O(). Собственно это единственный и последний плюс предложенного тобой алгоритма, поскольку теоретически позволяет обрабатывать терабайты данных. Но если элементов скажем до миллиона, то твой алгоритм если не продует, то будет на уровне производительности машины уровня Pentium I c реализованным хешем. И зачем это отрицать - не ясно.

← →
MBo © (2014-04-25 15:04) [226]

>Гора Фудзияма (25.04.14 14:30) [225]
Я решал с двумя проходами.

procedure FindPair(a: array of Integer; var n1, n2: Integer); var i, Mask: Integer; begin n1 := 0; n2 := 0; for i := 0 to High(a) do n1 := n1 xor a[i]; if n1 = 0 then Exit; Mask := 1; while (n1 and Mask) = 0 do Mask := Mask shl 1; for i := 0 to High(a) do if (a[i] and Mask) <> 0 then n2 := n2 xor a[i]; n1 := n1 xor n2; end;

← →
Sha © (2014-04-25 15:19) [227]

> Гора Фудзияма (25.04.14 14:30) [225]
> ...Почему по твоей логике N*32 стало не равно 32*N - я не знаю.

Цитату приведешь?

В текущей версии p^ считывается в регистр один раз для каждого p.
Для каждого считанного значения выполняется конечное количество операций.
Это один проход по элементам массива. И ничего не изменится,
даже если для каждого p я буду заполнять таблицу умножения трехзначных чисел.

Если с одним проходом мы разобрались,
то прежде, чем говорить о производительности, хочу для себя уточнить,
ты правда считаешь, что двухпроходный алгоритм мне неизвестен?

← →
Гора Фудзияма (2014-04-25 15:25) [228]

> MBo © (25.04.14 15:04) [226]
> >Гора Фудзияма (25.04.14 14:30) [225]
> Я решал с двумя проходами

Как это работает?
Выглядит очень круто

Первый цикл - сумма по модулю два (ксор) всех элементов. Парные взаимоуничтожаются, а результат будет Z = X xor Y.
Eдиничные биты Z показывают, какими битами отличается искомая пара чисел.
Второй цикл - поиск единичного бита в Z (младшего, но можно брать любой)
Третий цикл считает ксор тех чисел, у которых этот бит установлен, т.е. выделяет одно из искомых чисел (пусть Y)
X получается как Z xor Y

← →
Гора Фудзияма (2014-04-25 15:38) [230]

> MBo © (25.04.14 15:32) [229]

да, действительно гениально
но зачем было условие про 1 проход и памяти O(1)?
Вы же нас всех спутали ))))

В один проход можно и в память O(1)... Но они будут медленнее, чем предложенный Вами

>но зачем было условие про 1 проход и памяти O(1)?
Я на одном проходе не настаивал, требование было только о линейном времени и о памяти O(1)

← →
Гора Фудзияма (2014-04-25 15:45) [232]

А как такой подход будет выглядеть для 3-4-5 элементов?

такой - никак (например, 1 xor 2 xor 3 = 0), в этих случаях уже нужны побитовые действия

← →
Гора Фудзияма (2014-04-26 14:30) [234]

Не плохая идея - делать пятничные задачки

← →
junglecat (2014-04-26 14:36) [235]

> делать пятничные задачки

когда-то это было здесь традицией

Освежим немного:
Zero-Matrix
Дана квадратная матрица NxN, содержащая единицы и нули. Требуется без использования дополнительной памяти (т.е. с O(1)) обнулить те столбцы и строки, в которых есть нули.

Пример - из
1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1

должно получиться:
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0

Pretty List
Нужно оформить вывод списка красивым образом. Причем длина списка заранее неизвестна (например, получаем список файлов в папке, пока FindNext не обломится). Для простоты можно пользоваться while по входному открытому массиву, но использовать знание о том, что элемент, например, предпоследний - нельзя.

Красота должна быть такая -
а) Если список пуст - выводится {}
б) Один элемент с именем A - {A}
в) Два элемента A B - {A и B}
г) Более двух - {A, B и С}, или {A, B, C, D и E}
NB: запятой перед "и" нет.

Сохранять весь список и форматировать его потом - нельзя

P.S. В оригинале было нечто, поддерживающее IEnumerable.

> MBo © (25.04.14 15:04) [226]

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

Mask:=n1 and not (n1-1);

> [236] MBo © (30.04.14 13:28)
> Pretty List

Если тупо, то
#include <stdio.h> char aLong[] = "Very pretty list"; char a0[] = ""; char a1[] = "L"; char a2[] = "L2"; char a3[] = "ShL"; void VeryPrettyList(char *pc) { char lc1 = 0; char lc2 = 0; char lc3 = 0; printf("{"); while (*pc != 0) { if (lc3 != 0) { printf("%c,", lc3); } lc3 = lc2; lc2 = lc1; lc1 = *pc; pc++; } if (lc3 != 0) { printf("%c,%c,%c", lc3, lc2, lc1); } else if (lc2 != 0) { printf("%c and %c", lc2, lc1); } else if (lc1 != 0) { printf("%c", lc1); } printf("}\n"); } int main(int argc, char* argv[]) { VeryPrettyList(aLong); VeryPrettyList(a0); VeryPrettyList(a1); VeryPrettyList(a2); VeryPrettyList(a3); getchar(); return 0; }

Да, вывод:
{V,e,r,y, ,p,r,e,t,t,y, ,l,i,s,t} {} {L} {L and 2} {S,h,L}

Задачка для разминки мозга Найти похожие ветки