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

← →
Inovet © (2014-04-19 17:02) [120]

> [119] Inovet © (19.04.14 16:51)

В смысле, второй массив можно заводить или есть решение без него?

← →
Rouse_ © (2014-04-19 17:13) [121]

> Inovet © (19.04.14 17:02) [120]
> > [119] Inovet © (19.04.14 16:51)
>
> В смысле, второй массив можно заводить или есть решение
> без него?

Решения у меня пока нету - сам думаю, на использование локальных переменных ограничений нет.

← →
Inovet © (2014-04-19 18:07) [122]

> [121] Rouse_ © (19.04.14 17:13)

Ну тогда можно универсально сделать хоть для скольки хоть как повторяющихся, в пределах байта это 256 возможных значений. 2 вспомогательных массива обнуляем - один счётчики на 256 элементов, пусть будут байты для этой задачи, второй сортированные значения счётчиков. Идём по первому и увеличиваем значение в массиве счётчиков по индексу = значению из исходного. Что получилось 1 или 2 пишем во вспомогательный второй. В сортированном пулучим значения отсортированные по количеству встреченных раз.

Ну что-то такое.

← →
Rouse_ © (2014-04-19 18:36) [123]

> Inovet © (19.04.14 18:07) [122]

Это все в один проход?

← →
Inovet © (2014-04-19 18:38) [124]

> [123] Rouse_ © (19.04.14 18:36)

Ну

← →
Rouse_ © (2014-04-19 18:43) [125]

Показывай

← →
Sha © (2014-04-19 18:44) [126]

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

← →
MBo © (2014-04-19 19:16) [127]

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

← →
Rouse_ © (2014-04-19 19:18) [128]

Ну Боря и выдал блин задачку, целый день втыкаю, уже более 30 вариантов откинул...
ЗЫ: я исхожу из XOR, т.к. он сказал что для получения результата массив нужно проксорить, как это было в оригинале...

← →
Rouse_ © (2014-04-19 19:29) [129]

Единственно на что смог более-менее разумное выйти и с чем можно работать, это вот такое:

procedure T47; const Buff: array [0..9] of Byte = (17, 154, 1, 17, 3, 3, 81, 81, 1, 35); var I, A, B: Byte; begin A := 0; B := 0; for I := 0 to 9 do begin A := A xor Buff[I]; B := B xor (Buff[I] + 1); end; ??? end;

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

← →
Rouse_ © (2014-04-19 19:34) [130]

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

procedure T3; const Buff: array [0..9] of Byte = (17, 3, 81, 81, 1, 35, 154, 1, 17, 3); var I, A, B, C: Byte; begin A := 0; B := 0; C := 0; for I := 0 to 9 do begin C := C xor Buff[I]; if I and 1 = 0 then A := A xor Buff[I] else B := B xor Buff[I]; end; Writeln(A xor 80); // << осталось понять каким образом рассчитывается число (80 в данном случае) Writeln(B xor 80); // << для нивелирования мусора в обоих блоках end;

← →
MBo © (2014-04-19 19:38) [131]

> целый день втыкаю, уже более 30 вариантов откинул..
Я долго решал, не с одного подхода (не одним ксором пытался). Но после осознания некого ключевого факта всё быстро решилось. И непонятно стало - как же раньше этого не увидел

← →
Rouse_ © (2014-04-19 19:40) [132]

> MBo © (19.04.14 19:38) [131]

Не подсказывай :)
Я сам понимаю, что тут где-то есть нюанс (ну как вчера, в задаче с лягушками на пруду :)

← →
Sha © (2014-04-19 19:49) [133]

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

← →
Rouse_ © (2014-04-19 20:11) [134]

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

← →
Inovet © (2014-04-19 22:08) [135]

> [127] MBo © (19.04.14 19:16)
> Попросили уточнить требования

Это совсем друге условия. Что-то мне подсказывает, что надо найти разность и сумму, только какие и как.

Как-то так?

#pragma hdrstop
#pragma argsused

#include <tchar.h>
#include <stdio.h>

int _tmain(int argc, _TCHAR* argv[])
{
const int size = 10; // Чётное
int src [size] = {1,2,3,4,1,15,4,2,12,3};

int sum = 0;
int dif = 0;
for (int i = 0; i < size; i += 2) {
sum ^= src[i] ^ src[i + 1];
dif ^= (src[i] + 1) ^ (src[i + 1] + 1);
}
dif -= 2;

printf("Source %i:\n", size);
for (int i = 0; i < size; i++) {
printf("%4i", src[i]);
}

printf("\n");
printf("sum = %i, dif = %i\n", sum, dif);
printf("a = %i, b = %i\n", (dif - sum) / 2, (dif + sum) / 2);

getchar();

return 0;
}

← →
Inovet © (2014-04-19 22:11) [136]

Фу, не выделил кодовыми тегами.
int _tmain(int argc, _TCHAR* argv[]) { const int size = 10; // Чётное int src [size] = {1,2,3,4,1,15,4,2,12,3}; int sum = 0; int dif = 0; for (int i = 0; i < size; i += 2) { sum ^= src[i] ^ src[i + 1]; dif ^= (src[i] + 1) ^ (src[i + 1] + 1); } dif -= 2; printf("Source %i:\n", size); for (int i = 0; i < size; i++) { printf("%4i", src[i]); } printf("\n"); printf("sum = %i, dif = %i\n", sum, dif); printf("a = %i, b = %i\n", (dif - sum) / 2, (dif + sum) / 2); getchar(); return 0; }

← →
Inovet © (2014-04-19 22:20) [137]

Это в смысле не решение, а вопрос о направлении.

← →
Rouse_ © (2014-04-19 22:36) [138]

> Inovet © (19.04.14 22:20) [137]
> Это в смысле не решение, а вопрос о направлении.

В итоге приходим к тому что у меня и было в [129], только у тебя пары + 1.
Просто возьми бумашку и посчитай на масиве из 6 чисел.
Но... раз уже 2 человека двинулось в эту сторону, по всей видимости где-то тут и закрыто решение (ну не совсем же бы дауны, алгоритмику то боее-менее знаем :)

← →
Sha © (2014-04-19 22:44) [139]

если хотите, могу запостить решение, но боюсь обломать удовольствие от решения )

← →
Rouse_ © (2014-04-19 22:53) [140]

> Sha © (19.04.14 22:44) [139]

ни в коем разе... сам буду думать :)

← →
Inovet © (2014-04-19 22:54) [141]

> [138] Rouse_ © (19.04.14 22:36)
> только у тебя пары + 1

Ну, пары(Ы) эти от размышлений остались. Рядом она где-то, истина.

← →
Rouse_ © (2014-04-19 22:56) [142]

> Sha © (19.04.14 22:44) [139]

У себя в блоге лучше опубликуй, его, конечно, подсмотрят и с ответом нас с Андрюхой опередят, но потом скажут - что нас было четверо :)

← →
Sha © (2014-04-19 23:00) [143]

> MBo © (19.04.14 19:16) [127]
> т.е. один или несколько проходов по массиву допустимы

Борис, насчет нескольких проходов - ты просто нотацию разъяснял,
или твое решение в самом деле требует несколько проходов?

← →
Inovet © (2014-04-19 23:02) [144]

> [140] Rouse_ © (19.04.14 22:53)
> сам буду думать :)

У меня не думается уже. Тут циклические надо суммы и разности, вполне себе они суммы и разности, и XOR этот как раз оттуда.

← →
Sha © (2014-04-19 23:04) [145]

> Rouse_ © (19.04.14 22:56) [142]
> У себя в блоге лучше опубликуй

Лень че-то, сегодня на сериалы подсел, расслабляюсь )

← →
Rouse_ © (2014-04-19 23:05) [146]

> Inovet © (19.04.14 23:02) [144]
> У меня не думается уже.

У меня тоже, но я не привык бросать задачу. Да, пусть не сразу, но... решу.

Кстати в связи с последними событиями я обновил свой список предпочтений.
Теперь я не люблю: "высоту, гороховый суп и MBo".

← →
Sha © (2014-04-19 23:05) [147]

> Inovet © (19.04.14 23:02) [144]
> У меня не думается уже.

Во, сдавайтесь скорее )

← →
Rouse_ © (2014-04-19 23:12) [148]

Мне кстати здается что там есть два варинта, либо Боря это делал через какую-то хитрую константу (врятли, хотя когда я спрашивал, он хитро улыбался) либо, он просто ушел в истоки, от которых работает процессор (всего две инструкции) т.е. выходим либо на штрих Шеффера, либо стрелку Пирса и там как-то хитро обиграл работу с данными, эмулируя работу того-же ксора, где есть возможность вклинится непосредственно в момент выполнения инструкции.

ЗЫ: а может я уже просто загнался и я не вижу чего-то очевидного :))))

загнался

да

int _tmain(int argc, _TCHAR* argv[]) { const int size = 10; // Чётное int src [size] = {1,2,3,4,1,15,4,2,100,3}; // здесь будут два искомых разных элемента int u1, u2; // здесь будут два каких-то разных элемента int a1, a2; // здесь разности без них int d1 = 0; int d2 = 0; // А найдём-ка мы 2 разных и не будем их учитывать. // Ну, типа, знаем их, а по нормальному во время прохода и найдём for (int i = 0; i < size - 1; i++) { d1 ^= src[i]; d2 ^= src[i + 1]; } // Это, типа, нашли a1 = src[0]; a2 = src[size - 1];; // А здесь посчитаем искомые уникальные, на бумажке, ага, а то отупел уже u1 = 0; u2 = 0; printf("Source %i:\n", size); for (int i = 0; i < size; i++) { printf("%4i", src[i]); } printf("\n"); printf("d1 = %i, d2 = %i\n", d1, d2); printf("a1 = %i, a2 = %i\n", a1, a2); printf("u1 = %i, u2 = %i\n", u1, u2); getchar(); return 0; }

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

Выставляю на суд решение.
В основе решения лежит метод разбиения массива на две части со следующим условиями:
1. Одинаковые числа должны попасть в одну часть.
2. Искомые числа должны попасть в разные части.
Например, предположим, что имеется дополнительное условие о том, что искомые числа разной четности (отличаются первые биты). Тогда массив можно разбить на две части по признаку четности.
Т.к. условия из примера у нас нет, то я делаю множество различных разбиений, таких, что хотя бы в одном из них искомые числа окажутся в разных частях. Подсчитывают XOR сумму, а затем нахожу подходящее разбиение.
Циклы по J не зависят от размера массива и, при необходимости, могут быть развернуты, поэтому условие задачи не нарушено.

program Project1; {$APPTYPE CONSOLE} {$R *.res} uses System.SysUtils; procedure Find(Arr: array of Cardinal); const BitCount = SizeOf(Arr[0]) * 8; var I: Integer; J: 0..BitCount - 1; D: 0..1; Sums: array[0..BitCount-1] of array[0..1] of Cardinal; begin FillChar(Sums, SizeOf(Sums), 0); for I := Low(Arr) to High(Arr) do for J := 0 to BitCount - 1 do begin D := ((1 shl J) and Arr[I]) shr J; Sums[J][D] := Sums[J][D] xor Arr[I]; end; for J := 0 to BitCount - 1 do begin if (Sums[J][0] > 0) and (Sums[J][1] > 0) then begin Writeln(Sums[J][0]:10, Sums[J][1]:10); Exit; end; end; Writeln(Sums[0][0]:10, Sums[0][1]:10); end; begin try Find([17, 154, 1, 17, 3, 3, 81, 81, 1, 35]); Find([17, 3, 81, 81, 1, 35, 154, 1, 17, 3]); Find([1,2,3,4,1,15,4,2,12,3]); Find([1,2,3,4,1,15,4,2,100,3]); except on E: Exception do Writeln(E.ClassName, ": ", E.Message); end; Readln; end.

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

Прошу прощения за орфографию.

> Дмитрий СС

вынудил :)

type TMyElement= integer; PMyElement= ^TMyElement; TMyArray= array of TMyElement; procedure Find(p: PMyElement; count: integer; var res: TMyArray); const bound= SizeOf(TMyElement)*8-1; var Found: array[-1..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:=-1 to bound do Found[i]:=0; q:=p; inc(q,count); //адрес за пределами массива repeat; Found[-1]:=Found[-1] xor p^; 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] xor Found[-1]; end; end; end;

> Дмитрий СС (20.04.14 02:26) [154]

какой у тебя результат для массива [0, 1] ?

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

> Sha © (20.04.14 03:08) [157]

0 1

P.S.:
Небольшая оптимизация:
program Project1; {$APPTYPE CONSOLE} {$R *.res} uses System.SysUtils; procedure Find(Arr: array of Cardinal); const BitCount = SizeOf(Arr[0]) * 8; var I: Integer; J: Integer; D: 0..1; Sums: array[0..BitCount-1] of array[0..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 begin D := ((1 shl J) and Arr[I]) shr J; Sums[J][D] := Sums[J][D] xor Arr[I]; end; F := F xor Arr[I]; end; // Теперь в F единицами обозначены биты, в которых искомые числа отличаются // По номеру любого этого бита можем определить какой элемент массива Sums нам выбирать // Для простоты поиска воспользуемся 32битной инструкцией BSF 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][0]:10, Sums[J][1]:10); end; begin try Find([17, 154, 1, 17, 3, 3, 81, 81, 1, 1]); 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]); except on E: Exception do Writeln(E.ClassName, ": ", E.Message); end; Readln; end.

← →
Rouse__ (2014-04-20 03:32) [159]

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

← →
Дмитрий СС (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;

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