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

← →
Дмитрий СС (2014-04-20 03:37) [160]

> Sha © (20.04.14 02:58) [156]
>
> вынудил :)
>

Изучил бегло твое решение и пришел к выводу, что ход мыслей одинаковый). Спасибо. С учетом твоего решения еще чуть-чуть оптимизировал свое:

procedure Find(Arr: array of Cardinal); const BitCount = SizeOf(Arr[0]) * 8; var I: Integer; J: Integer; Sums: array[0..BitCount - 1] of Cardinal; F: Cardinal; begin FillChar(Sums, SizeOf(Sums), 0); F := 0; for I := Low(Arr) to High(Arr) do begin for J := 0 to BitCount - 1 do if (1 shl J) and Arr[I] > 0 then Sums[J] := Sums[J] xor Arr[I]; F := F xor Arr[I]; end; if F <> 0 then asm bsf eax, F // В edx позиция младшей единицы из F ( http://asm-book.narod.ru/Stati_NK_IP_BSF.html ) mov J, eax end else J := 0; // Такого, по идее, не может быть по условию задачи, но если вдруг, то выбираем первый элемент. Writeln(Sums[J]:10, Sums[J] xor F:10); end;

← →
Rouse__ (2014-04-20 03:39) [161]

Дим, ты массивчик то убери из локальных переменных, и добро пожаловать к нам с Андреем :)))

← →
Дмитрий СС (2014-04-20 03:41) [162]

> Ребят, вы уточнение от Бориса прочитайте, у обоих решение
> не подходит под заявленное условие

С учетом того, что допустимы несколько проходов:
procedure Find(Arr: array of Cardinal); var I: Integer; J: Integer; S: Cardinal; F: Cardinal; begin F := 0; for I := Low(Arr) to High(Arr) do F := F xor Arr[I]; if F = 0 then raise Exception.Create("Массив не содержит уникальных элементов."); asm bsf eax, F // В edx позиция младшей единицы из F ( http://asm-book.narod.ru/Stati_NK_IP_BSF.html ) mov J, eax end; S := 0; for I := Low(Arr) to High(Arr) do if (1 shl J) and Arr[I] > 0 then S := S xor Arr[I]; Writeln(S:10, S xor F:10); end;

← →
Дмитрий СС (2014-04-20 03:42) [163]

> Rouse__ (20.04.14 03:39) [161]

Так пойдет?)

← →
Rouse__ (2014-04-20 03:44) [164]

Хм, чето похожее, завтра с компа перепроверю, но видимо это оно :)

← →
Дмитрий СС (2014-04-20 03:47) [165]

> Rouse__ (20.04.14 03:44) [164]

Принцип простой:
В первом проходе находим F = A xor B, а так-же определяем по какому биту A и B отличаются.
Во втором проходе находим одно из искомых (A или B) отсеив часть массива со вторым искомым.

P.S. там в комменте опечатка. Вместо edx, конечно eax.

← →
Дмитрий СС (2014-04-20 04:04) [166]

Ну и совсем, чтобы уйти спокойным, привел код в порядок:
program Project1; {$APPTYPE CONSOLE} uses System.SysUtils; type Number = Int64; procedure Find(Arr: array of Number); var I, J: Integer; S, F: Number; begin { Находим F = A xor B, где A и B - искомые числа } F := 0; for I := Low(Arr) to High(Arr) do F := F xor Arr[I]; if F = 0 then raise Exception.Create("Массив не соответствует условию задачи."); { Находим J - номер бита, в котором A и B отличаются } J := 0; while (F shr J) and 1 = 0 do Inc(J); { Находим S - одно из искомых чисел, путем отсеивания части массива с другим числом} S := 0; for I := Low(Arr) to High(Arr) do if (1 shl J) and Arr[I] > 0 then S := S xor Arr[I]; { Находим второе искомое число и выводим } Writeln(S:22, S xor F:22); end; begin Find([0, 1]); Find([Low(Number), 0, 0, High(Number)]); Find([17, 3, 81, 81, 1, 34, 154, 1, 17, 3]); Find([1,2,3,4,1,15,4,2,14,3]); Find([1,2,3,4,1,15,4,2,100,3]); Readln; end.

Как насчет того, чтобы добавить условие - всего один проход по массиву с тем же условием для переменных?

← →
MBo © (2014-04-20 06:36) [167]

>Борис, насчет нескольких проходов - ты просто нотацию разъяснял,
Да.

(остаток ветки пока не читал)

← →
Sha © (2014-04-20 09:12) [168]

> Rouse__ (20.04.14 03:32) [159]
> Ребят, вы уточнение от Бориса прочитайте, у обоих решение не подходит под заявленное условие

не нашел противоречий с условием

← →
Inovet © (2014-04-20 09:55) [169]

Пока не понял, почему пометка не будет совпадать с другими.

← →
Sha © (2014-04-20 10:05) [170]

какая пометка?

← →
Sha © (2014-04-20 10:14) [171]

> Дмитрий СС (20.04.14 04:04) [166]
> Как насчет того, чтобы добавить условие - всего один проход по массиву с тем же условием для переменных?

Вряд ли это возможно.

Есть другое интересное ограничение. Те же условия, но запрещено вычислять xor для всего массива. Есть 2 способа:
1. вычислять суммы для нулевых значений битов,
2. восстанавливать второе значение по ненулевым суммам.
Первый требует в 2 раза больше памяти под массив - некрасиво,
второй начал вчера писать - срубило в сон.

← →
Sha © (2014-04-20 11:12) [172]

> Sha © (20.04.14 10:14) [171]

сделал без общего xor"а (второй вариант):

procedure Find2(p: PMyElement; count: integer; var res: TMyArray); const bound= SizeOf(TMyElement)*8-1; var Found: array[0..bound] of TMyElement; t: TMyElement; q: PMyElement; i: integer; begin; if (p=nil) or (count<=0) then SetLength(res,0) else if count and 1<>0 then begin; t:=0; while count>0 do begin; t:=t xor p^; inc(p); dec(count); end; SetLength(res,1); res[0]:=t; end else begin; //count and 1=0 for i:=0 to bound do Found[i]:=0; q:=p; inc(q,count); //адрес за пределами массива repeat; t:=1; for i:=0 to bound do begin; //изменяем сумму, при этом инвертируется значение бита-счетчика if p^ and t<>0 then Found[i]:=Found[i] xor p^; t:=t+t; end; inc(p); until p=q; i:=0; t:=1; while (i<=bound) and (Found[i] and t=0) do begin; //ищем взведенный бит-счетчик inc(i); t:=t+t; end; if i>bound then SetLength(res,0) //не нашли else begin; SetLength(res,2); res[0]:=Found[i]; res[1]:=Found[i]; repeat; if Found[i] and t<>0 then res[0]:=res[0] xor t; inc(i); t:=t+t; until i>bound; end; end; end; procedure TForm1.Button1Click(Sender: TObject); var data, res: TMyArray; t: TMyElement; i, j: integer; begin; RandSeed:=1; //Randomize; //отрицательные значения - индикаторы пустых мест SetLength(data, 1002); for i:=0 to Length(data)-1 do data[i]:=-1; //помещаем один или два недубликата i:=(Length(data)-1) div 2; data[i]:=100500; if Length(data) and 1=0 then data[i+1]:=42; //незанятые места заполняем дубликатами for i:=Length(data)-1 downto 0 do if data[i]<0 then begin; t:=Random($1000000); data[i]:=t; if i>0 then begin; j:=Random(i); if data[j]<0 then data[j]:=t else for j:=i-1 downto 0 do if data[j]<0 then begin; data[j]:=t; break; end; end; end; //ищем недубликаты Find2(@data[0],Length(data),res); Memo1.Lines.Add(Format("найдено %d",[Length(res)])); for i:=0 to Length(res)-1 do Memo1.Lines.Add(IntToStr(res[i])); end;

← →
Inovet © (2014-04-20 11:28) [173]

> [170] Sha © (20.04.14 10:05)
> какая пометка?

Вот этот номер бита отличия для опознавания первого уникального. Щас подумаю.

← →
Sha © (2014-04-20 11:40) [174]

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

← →
Inovet © (2014-04-20 11:58) [175]

> [174] Sha © (20.04.14 11:40)

Ага. Вот я вчера думал в сторону определения одного искомого на втором проходе по готовой сумме, но показалось, что ловить так не получится.

← →
Sha © (2014-04-20 12:12) [176]

> Inovet © (20.04.14 11:58) [175]

Можно и за один проход.
Просто запускаем параллельно подсчет 32 / 64 сумм для каждого единичного бита, а потом берем первую подходящую.
По остальным суммам легко восстановить второе число.

← →
Inovet © (2014-04-20 12:21) [177]

> [176] Sha © (20.04.14 12:12)

А так неправильно что-то? Без выделения битов
int _tmain(int argc, _TCHAR* argv[]) { const int size = 10; // Чётное int src[size] = {1,2,3,4,1,15,4,2,100,3}; // int src[size] = {1,100,3,4,1,15,4,2,2,3}; int d = 0; int s = 0; printf("Source %i:\n", size); for (int i = 0; i < size; i++) { printf("%4i ", src[i]); } printf("\n"); printf("Source %i:\n", size); for (int i = 0; i < size; i++) { printf("%04x ", src[i]); } printf("\n"); printf("Pass 1\n"); for (int i = 0; i < size; i++) { d ^= src[i]; printf("%04x ", d); } printf("\n"); printf("Pass 2\n"); for (int i = 0; i < size; i++) { if (src[i] & d != 0) { s ^= src[i]; printf("%04x ", s); } else { printf("---- "); } } printf("\n"); printf("d = %4i, s = %4i\n", d, s); printf("a = %4i, b = %4i\n", d ^ s, s); getchar(); return 0; } Вывод: Source 10: 1 2 3 4 1 15 4 2 100 3 Source 10: 0001 0002 0003 0004 0001 000f 0004 0002 0064 0003 Pass 1 0001 0003 0000 0004 0005 000a 000e 000c 0068 006b Pass 2 0001 ---- 0002 ---- 0003 000c ---- ---- ---- 000f d = 107, s = 15 a = 100, b = 15

Вот эти пропуски на втором проходе меня и смутили, до написания кода не довёл.

← →
Sha © (2014-04-20 12:45) [178]

Да, так будет неправильно.
Например, для недубликатов 1 и 2 получишь 3.
Достаточно одной суммы.

← →
Inovet © (2014-04-20 12:58) [179]

> [178] Sha © (20.04.14 12:45)
> Например, для недубликатов 1 и 2 получишь 3.

результат правильный
d = 3, s = 1 a = 2, b = 1

← →
Inovet © (2014-04-20 13:01) [180]

> [179] Inovet © (20.04.14 12:58)

1,3 неправильный

← →
Дмитрий СС (2014-04-20 15:41) [181]

Я, пожалуй, начну записывать сложные и интересные задачки. Возможно сборничек соберу:)

← →
junglecat (2014-04-20 16:20) [182]

а где решение в 1 проход?) а то ведь можно отсортировать массив и просто сравнивать 2 элемента, двигаясь с шагом 2

← →
Дмитрий СС (2014-04-20 16:27) [183]

> junglecat (20.04.14 16:20) [182]

А сортировка массива по твоему сколько займет проходов?

Как вариант (формально 1 проход:)):
procedure Find(Arr: array of Number); var I, J: Integer; S, F: Number; begin F := 0; J := 0; S := 0; for I := 0 to (Length(Arr) shr 1) - 1 do { Первая половина прохода } F := F xor Arr[I shl 1] xor Arr[I shl 1 or 1]; while ((F shr J) and 1 = 0) and (F <> 0) do Inc(J); for I := (Length(Arr) shr 1) to Length(Arr) - 1 do { Вторая половина прохода } S := S xor (Arr[(I - (Length(Arr) shr 1)) shl 1] * ((Arr[(I - (Length(Arr) shr 1)) shl 1] shr J) and 1)) xor (Arr[(I - (Length(Arr) shr 1)) shl 1 or 1] * ((Arr[(I - (Length(Arr) shr 1)) shl 1 or 1] shr J) and 1)); Writeln(S:22, S xor F:22); end;

← →
Дмитрий СС (2014-04-20 16:40) [184]

Не знаю сложная или нет задача.
Необходимо раскрыть скобки:
(a + 1) xor b

← →
Inovet © (2014-04-20 17:14) [185]

> [184] Дмитрий СС (20.04.14 16:40)
> Необходимо раскрыть скобки:

Символьно?

← →
Дмитрий СС (2014-04-20 17:16) [186]

> Inovet © (20.04.14 17:14) [185]

Ну начнем с этого.
Другими словами представить в виде выражения без скобок, с использованием доступных в delphi операторов.

← →
Sha © (2014-04-20 17:58) [187]

> Дмитрий СС (20.04.14 16:40) [184]

а зачем они там, если можно просто a + 1 xor b ?

← →
Sha © (2014-04-20 18:04) [188]

> junglecat (20.04.14 16:20) [182]
> а где решение в 1 проход?)

[154], [156], [158], [160], [172]

7 лет назад ;)

> Sha © (2007-11-16 11:53) [43]
> 5б аналогично.
> На первом проходе XOR-ом отыскиваем бит, в котором наши
> числа не совпадают.
> На втором проходе вычисляем XOR0 для всех чисел, содержащих
> 0 в этом бите, и XOR1 для чисел, содержащих 1.
> Это и будут искомые числа.

Я при решении (двухпроходном) долго упускал смысл результата первого прохода. И дотумкал, только когда подумал о значении единичных битов в нём.

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

И чего тут такого?
Упорядочить по возрастанию за время O(n), пройти и посмотреть. И все: и мудрить не надо, и сколько хочешь недубликатов найдет.

> Romkin © (21.04.14 12:41) [190]

неизвестно, можно ли изменять массив,
плюс непонятно, как упорядочить за время O(N) и память O(1)

> а где решение в 1 проход?)

Ну можно и в 1 проход сделать. Если учесть то что у нас массив значений строго определенного типа.

только решение будет некрасивое и сложное.

← →
Дмитрий СС (2014-04-21 18:42) [193]

> Rouse_ © (19.04.14 12:26) [113]
> MBo вчера филосовски рассудил - задачки не сильно сложные и предложил модифицировать вторую из них.

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

* НЕДУБЛИКАТОВ

> Ну так в студию)

Времени нет на написание кода, да и жена злая рядом не дает компом пользоваться.
Но суть та же как и в предлагаемом решении с двумя проходами. Только вы в первом проходе ищете нужный бит, по которому выбираете данные во втором проходе. а можно сразу в одном проходе делать и общий xor, а так же и 8 xorов по всем битам, а после прохода анализировать полученные данные уже без проходов по исходному массиву

что-то типа этого:

procedure Find(Arr: array of byte); var d:array[0..8] of byte; i,j,w1:integer; begin for j:=0 to 8 do d[j]:=0; 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]; w1:=d[0]; for j:=1 to 7 do if (d[j]<>0) and (d[j]<>d[8]) then w1:=d[j]; Writeln(w1, w1 xor d[8]); end;

[197] это на [193]

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

Т.е. ты хотел сказать для "неизвестного числа недубликатов"?

думаю будет проблематично, хотя бы из-за того что одним из недубликатов вполне может быть 0

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

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