Форум: "Прочее";
Текущий архив: 2014.12.14;
Скачать: [xml.tar.bz2];
ВнизЗадачка для разминки мозга Найти похожие ветки
← →
Rouse_ © (2014-04-16 21:37) [0]Итак, дано, есть функция вида:
function T(A, B: Byte): Boolean;
begin
Result := ???
end;
Данной функции могут быт переданы любые значения параметров А/В, но только на два из них она должна вернуть результат False, это должно случится при условии что (A = 90 и В = 77) или наоборот (A = 77 и В = 90). Во всех остальных случаях данная функция должа вернуть True.
Важный нюанс, код функции не должен содержать логических переходов.
Т.е. нельзя использовать метки и операторы GOTO, нельзя использовать условия IF..THEN, нельзя использовать циклы (т.к. переход на след итерацию происходит именно ввиде сравнения и перехода).
Нельзя использовать блоки CASE или SET, т.к. они также основаны на проверках.
Т.о. вот такой код не валиден:function T(A, B: Byte): Boolean;
begin
Result := not ((A in [77, 90]) and (B in [77, 90]) and (A <> B));
end;
и такой тоже:function T(A, B: Byte): Boolean;
begin
Result := True;
if (A = 90) and (B = 77) then
Result := False
else
if (A = 77) and (B = 90) then
Result := False;
end;
Победит тот кто напишет наименее краткий и понятный код.
ЗЫ: особое условие.
Огромная просьба не писать варианты решений нашим мэтрам (ИШ/ЮЗ/Sha/0xFFFF) вам это как семечку пощелкать, а народу станет не интересно :)
← →
Rouse_ © (2014-04-16 21:41) [1]Зы, а MBo сюда доже вообще даж не смотреть, бо он будет знать вариат решения даже не дочитав до последней строчки первого поста :)
← →
SergP © (2014-04-16 21:46) [2]А так тоже нельзя:
result:=((a=77) and (b=90)) or ((a=90) and (b=77))
?
← →
Rouse_ © (2014-04-16 21:59) [3]Да, так тоже нельзя, ибо тоже будут логические переходы (под ними я подразумеваю условные переходы в виде инструкций JXX в асм коде, где нужно будет купировать результаты вычислений двух блоков - первой и второй проверки, чтобы над ними выполнить OR)
← →
Rouse_ © (2014-04-16 22:00) [4]В оригинале задача стояла так - написать алгритм сравнения на ассемблере без использования операторов JXX, а тут я уже причесал постановку задачи под Delphi
← →
Rouse_ © (2014-04-16 22:07) [5]Грубо чтоб понять смысл, вот дизасм этой функции:
Project6.dpr.17: Result := ((a=77) and (b=90)) or ((a=90) and (b=77));
00418A02 807DFF4D cmp byte ptr [ebp-$01],$4d
00418A06 7506 jnz $00418a0e <<< нельзя
00418A08 807DFE5A cmp byte ptr [ebp-$02],$5a
00418A0C 7410 jz $00418a1e <<< нельзя
00418A0E 807DFF5A cmp byte ptr [ebp-$01],$5a
00418A12 7506 jnz $00418a1a <<< нельзя
00418A14 807DFE4D cmp byte ptr [ebp-$02],$4d
00418A18 7404 jz $00418a1e <<< нельзя
00418A1A 33C0 xor eax,eax
00418A1C EB02 jmp $00418a20
00418A1E B001 mov al,$01
00418A20 8845FD mov [ebp-$03],al
Project6.dpr.18: end;
00418A23 8A45FD mov al,[ebp-$03]
00418A26 59 pop ecx
00418A27 5D pop ebp
00418A28 C3 ret
← →
Rouse_ © (2014-04-16 22:17) [6]ЗЗЫ: в догонку
> SergP © (16.04.14 21:46) [2]
оператор OR в данном случае эквивалентен блоку ELSE из второго примера.
← →
Германн © (2014-04-16 22:32) [7]Интересные числа 90 и 77. У каждого тетрады зеркальны в негативе.
← →
Павиа (2014-04-16 22:36) [8]А в чём прикол детской задачке?
← →
Rouse_ © (2014-04-16 22:37) [9]
> Германн © (16.04.14 22:32) [7]
> Интересные числа 90 и 77. У каждого тетрады зеркальны в
> негативе.
Таких чисел много, могу выбрать и другие если хочешь :)
А так эти числа обозначают инициалы Марка Збиковски "MZ" или "ZM", т.е. то что должно находится в _IMAGE_DOS_HEADER.e_magic каждого уважающего себя экзешника:)
← →
Rouse_ © (2014-04-16 22:38) [10]
> Павиа (16.04.14 22:36) [8]
> А в чём прикол детской задачке?
Дык эта... в ее решении.
← →
имя (2014-04-16 22:48) [11]Удалено модератором
← →
имя (2014-04-16 22:52) [12]Удалено модератором
← →
Inovet © (2014-04-16 22:54) [13]A xor B = 23
коротко?
← →
Inovet © (2014-04-16 22:55) [14]> [13] Inovet © (16.04.14 22:54)
или чё там джамп будет?
ну -23 тогда
← →
Jeer © (2014-04-16 23:03) [15]>Длиннее по условию
У тебя очень короткий, но вот длиннее или длиньше?
Result := boolean((A and $7F)*(B and $7F) mod ($1B12));
← →
Inovet © (2014-04-16 23:06) [16]> [15] Jeer © (16.04.14 23:03)
> and $7F
Не пойдёт
← →
Rouse_ © (2014-04-16 23:08) [17]
> Jeer © (16.04.14 23:03) [15]
Решение не верное, есть коллизии.
← →
Rouse_ © (2014-04-16 23:10) [18]Для простоты, можно проверить свои варианты сразу вот таким кодом:
var
A, B: Integer;
begin
for A := 0 to 255 do
for B := 0 to 255 do
if not T(A, B) then
Writeln(IntToHex(A, 2), IntToHex(B, 2));
Readln;
end.
Если выведет:4D5A
5A4D
Значит все сделано правильно.
← →
Dimka Maslov © (2014-04-16 23:11) [19]function T(A, B: Byte): Boolean;
var
F: Byte;
N: Integer;
begin
F := (A + B) + 90;
N := F * A * B - 6930 + (A xor B) - 23;
Result := N = 0;
end;
← →
Rouse_ © (2014-04-16 23:15) [20]
> Dimka Maslov © (16.04.14 23:11) [19]
Решение практически верное (в последней строчке ты перепутал, и в итоге результат инвертирован).
← →
Rouse_ © (2014-04-16 23:16) [21]ЗЫ: можно сделать еще проще, ждем варианты :)
← →
Dimka Maslov © (2014-04-16 23:16) [22]Вернее N <> 0, и без это сравнения никак, из представления boolean в дельфе
← →
Дмитрий К © (2014-04-16 23:18) [23]Result := Boolean(((a + b) xor 167) or (abs(a - b) xor 13) or ((a or b) xor 95));
← →
Dimka Maslov © (2014-04-16 23:18) [24]Ну да, первая строка не нужна, остаётся только
N := A * B - 6930 + (A xor B) - 23;
← →
Rouse_ © (2014-04-16 23:21) [25]
> Дмитрий К © (16.04.14 23:18) [23]
Класс, да это практически что и ожидается, но... Abs?
← →
Rouse_ © (2014-04-16 23:26) [26]
> Dimka Maslov © (16.04.14 23:18) [24]
You Win :))function T(A, B: Byte): Boolean;
begin
Result := (A * B - 6930 + (A xor B) - 23) <> 0;
end;
← →
Dimka Maslov © (2014-04-16 23:30) [27]Я вот что подумал, это новая тенденция в программировании такая что ли пошла - избавляться от if. Мне вот тут на днях тоже задачку задали, где условием правильности решения являлось минимально возможное количество проверок, ибо они "очень медленные" ???
← →
Dimka Maslov © (2014-04-16 23:34) [28]А ещё забавно, что подобное прокатывает не для всех пар чисел...
← →
SergeyIT © (2014-04-16 23:36) [29]Учат писать код, чтобы никто не разобрался что он делает (есть много примеров на Си)
← →
Rouse_ © (2014-04-16 23:37) [30]Раз уж ты так быстро все решил, то подкину для разминки еще одну задачку, а то ветка скучная получится :)))
Есть массив чисел. Размер массива 2N+1. В этом массиве 2N дубликаты, а 1 значение уникально. Надо написать код, который найдет значение этого уникального числа за одну итерацию, т.е. за один проход. Пример ряда: "3, 1, 5, 1, 3".
В этом ряду {3, 3}, {1,1} дубликаты, а 5 — уникальное.
← →
Rouse_ © (2014-04-16 23:38) [31]
> SergeyIT © (16.04.14 23:36) [29]
> Учат писать код, чтобы никто не разобрался что он делает
> (есть много примеров на Си)
Нивкоем разе - этож чистая алгоритмика. Если так писать в боевой задаче, то нафих вон из профессии... (кто это будет сопровождать?)
← →
Dimka Maslov © (2014-04-16 23:42) [32]Как я понимаю решение с предварительной сортировкой не канает? В любом случае эта задача на завтра, а то уже спать пора.
← →
Inovet © (2014-04-16 23:43) [33]> [30] Rouse_ © (16.04.14 23:37)
Идём по массиву, сравниваем текущее с предыдущими 2-мя, если отличается - значит, нашлось. Ну или тоже с XOR, если надо хуже читаемость.
← →
Rouse_ © (2014-04-16 23:44) [34]
> Inovet © (16.04.14 23:43) [33]
В виде кода будет гораздо наглядней, чем на словах :)
← →
Rouse_ © (2014-04-16 23:48) [35]
> Inovet © (16.04.14 23:43) [33]
Да, ну и не забывай, что у нас массив в виде 2N+1 элементов, т.е. это может быти и такое:
"1, 2, 3, 4, 5, 1, 2, 3, 4"
← →
Ega23 © (2014-04-17 00:06) [36]
> Есть массив чисел. Размер массива 2N+1. В этом массиве 2N
> дубликаты, а 1 значение уникально. Надо написать код, который
> найдет значение этого уникального числа за одну итерацию,
> т.е. за один проход.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;
← →
Ega23 © (2014-04-17 00:11) [37]Первая, ИМХО, интереснее была. Правда меня не в ту степь понесло, я с shr начал экспериментировать. Ну, типа, ((a shr 2) or (b shr 2)) <> (a xor b)
← →
Inovet © (2014-04-17 00:22) [38]> [35] Rouse_ © (16.04.14 23:48)
> "1, 2, 3, 4, 5, 1, 2, 3, 4"
А, понял. Дубликатов 2N. Они упорядочены? Тогда просто максимальное ищем. Нет тогда в другой массив что ли пихать с индексом нового уникального, тут подумать надо.
ПС. Писать сейчас нет времени.
← →
Ega23 © (2014-04-17 00:27) [39]
> А, понял. Дубликатов 2N. Они упорядочены? Тогда просто максимальное
> ищем. Нет тогда в другой массив что ли пихать с индексом
> нового уникального, тут подумать надо.
Да тут всё просто.
1. X xor X = 0;
2. X xor 0 = X;
3. xor - коммутативен.
← →
тупой компилятор (2014-04-17 00:27) [40]> Dimka Maslov © (16.04.14 23:34) [28]
> А ещё забавно, что подобное прокатывает не для всех пар чисел...
//прокатывает для всех пар
Result:=(A*B-(77*90)) or ((A+B)-(77+90))<>0;
← →
int64 © (2014-04-17 00:34) [41]Решение на уровне пятиклассника:
Result := ((A - 90) * (B - 90) + (B - 77) * (A - 77) + 1) * (A + B - 77 - 90 + 1) = 1
← →
Hidden (2014-04-17 09:47) [42]
function T(A, B: Byte): Boolean;
begin
Result:=A*B+(A xor B)<>6953;
end;
← →
SergP © (2014-04-17 09:55) [43]const Arr:array[0..255,0..255] of boolean = ......
function T(A, B: Byte): Boolean;
begin
Result:=Arr[A,B];
end;
)))
← →
SergP © (2014-04-17 09:57) [44]> Важный нюанс, код функции не должен содержать логических переходов.
А разве они не создаются при использовании сравнения =, <> ?
← →
Hidden (2014-04-17 10:01) [45]Нет
← →
Юрий Зотов © (2014-04-17 10:20) [46]> Задачка для разминки мозга
Описание задачи заказчиком.
X и Y должны суммироваться. Но если сегодня среда, то они должны вычитаться. А если позавчера был дождь, то должны умножаться. А если завтра выходной, то надо X делить на Y. А если грачи уже прилетели, то Y надо обнулить. А если оператор - блондинка, то ее надо перекрасить в брюнетку, причем считать, что брюнеткой она стала еще неделю назад. И т.п.
Вот это - действительно задачка для разминки мозга. При том, что, решая ее, надо еще учитывать, что через неделю добавятся новые требования типа "а если хочу неизвестно чего, то надо сделать неизвестно что".
:o)
← →
junglecat (2014-04-17 10:56) [47]> [46] Юрий Зотов © (17.04.14 10:20)
это из реального проекта? o)
← →
Dimka Maslov © (2014-04-17 11:09) [48]
> тупой компилятор (17.04.14 00:27) [40]
or по условию задачи применять нельзя для сравнения логических значений.
← →
Hidden (2014-04-17 11:28) [49]> Dimka Maslov ©
там битовая операция
← →
Дмитрий СС (2014-04-17 11:45) [50]Ну вот, все задачи решили пока я спал :)
← →
Rouse_ © (2014-04-17 11:45) [51]
> Dimka Maslov © (17.04.14 11:09) [48]
В данном случае все нормально, JXX не генерируется:Project1.dpr.51: Result:=(A*B-(77*90)) or ((A+B)-(77+90))<>0;
0041886A 33C0 xor eax,eax
0041886C 8A45FF mov al,[ebp-$01]
0041886F 33D2 xor edx,edx
00418871 8A55FE mov dl,[ebp-$02]
00418874 F7EA imul edx
00418876 2D121B0000 sub eax,$00001b12
0041887B 33D2 xor edx,edx
0041887D 8A55FF mov dl,[ebp-$01]
00418880 33C9 xor ecx,ecx
00418882 8A4DFE mov cl,[ebp-$02]
00418885 03D1 add edx,ecx
00418887 81EAA7000000 sub edx,$000000a7
0041888D 0BC2 or eax,edx
0041888F 0F9545FD setnz byte ptr [ebp-$03]
← →
Rouse_ © (2014-04-17 11:47) [52]А вот мой вариант решения:
function T(A, B: Byte): Boolean;
asm
and eax, $FF
and edx, $FF
mov ecx, eax
xor ecx, edx
sub ecx, $17
imul edx
lea ecx, [eax + ecx - $1B12]
cmp ecx, 0
setnz al
end;
← →
ТНЕ картман (2014-04-17 12:01) [53]... должен пригодиться для парсинга больших хмл))
← →
Sapersky (2014-04-17 12:06) [54]setXX можно использовать и в варианте [2], другое дело что компилятор не соображает это сделать. Он похоже умеет их применять только в простых выражениях, в одно действие.
Или если пнуть особым пинком:
Result:=Boolean( (Byte(a=77) and Byte(b=90)) or (Byte(a=90) and Byte(b=77)) );
(как я понимаю, Byte(a=77) и т.д. - простые выражения, and/or делается уже между числами и поэтому не в счёт)
← →
Sha © (2014-04-17 12:19) [55][24] и [52] можно упростить, если использовать одну константу 6953 вместо двух
← →
Rouse_ © (2014-04-17 12:20) [56]
> ТНЕ картман (17.04.14 12:01) [53]
> ... должен пригодиться для парсинга больших хмл))
Ты меня ни с кем не путаешь? :)
← →
ТНЕ картман (2014-04-17 12:23) [57]
> Rouse_ © (17.04.14 12:20) [56]
> Ты меня ни с кем не путаешь? :)
надо ж мне в угоду нику поязвить))
← →
Rouse_ © (2014-04-17 12:25) [58]
> Sha © (17.04.14 12:19) [55]
> [24] и [52] можно упростить, если использовать одну константу
> 6953 вместо двух
Кстати да, тогда:function T(A, B: Byte): Boolean;
asm
and edx, $FF
mov ecx, eax
xor ecx, edx
imul edx
lea ecx, [eax + ecx - $1B29]
cmp ecx, 0
setnz al
end;
← →
Юрий Зотов © (2014-04-17 12:49) [59]> junglecat (17.04.14 10:56) [47]
Практически да. Причем на вполне резонный вопрос "а что делать, если сегодня среда, позавчера был дождь, завтра выходной, а грачи уже прилетели?" получить вразумительный ответ не удается.
← →
Дмитрий СС (2014-04-17 13:05) [60]
> Юрий Зотов © (17.04.14 12:49) [59]
Сложить, вычесть, поделить и умножить, понятно же:))
← →
Sha © (2014-04-17 13:34) [61]еще вариант
Result:=i*i+j*j<>(77*77)+(90*90);
← →
Inovet © (2014-04-17 14:17) [62]> [52] Rouse_ © (17.04.14 11:47)
> А вот мой вариант решения:
А чё короткий? Надо же длинный и запутанный.
← →
Rouse_ © (2014-04-17 14:25) [63]
> Inovet © (17.04.14 14:17) [62]
> А чё короткий? Надо же длинный и запутанный.
А зачем? :)
← →
Inovet © (2014-04-17 14:31) [64]> [63] Rouse_ © (17.04.14 14:25)
> А зачем? :)
> [0] Rouse_ © (16.04.14 21:37)
> Победит тот кто напишет наименее краткий и понятный код.
← →
Rouse_ © (2014-04-17 14:36) [65]
> Inovet © (17.04.14 14:31) [64]
Ну у меня всяко не самый краткий и не самый понятный :))))
← →
Дмитрий СС (2014-04-17 15:11) [66]
function T(A, B: Byte): Boolean;
asm
mov dh, al
xor eax, eax
cmp dx, $5a4d
setz al
cmp dx, $4d5a
setz ah
or al, ah
end;
← →
Дмитрий СС (2014-04-17 15:18) [67]Обнуление eax можно стереть, получаем 6 строк
function T(A, B: Byte): Boolean;
asm
mov dh, al
cmp dx, $5a4d
setz al
cmp dx, $4d5a
setz ah
or al, ah
end;
← →
Mystic © (2014-04-17 15:32) [68]Непонятно, неужели тупой прямой метод настолько плох по производительности?
leal -90(%rdi), %edx
leal -77(%rsi), %eax
orl %eax, %edx
sete %al
subl $77, %edi
subl $90, %esi
orl %esi, %edi
sete %dl
orl %edx, %eax
ret
← →
Hidden (2014-04-17 15:45) [69]> Дмитрий СС (17.04.14 15:18) [67]
к сожалению по условию задачи ещё нужно будет инвентировать бит
а вообще даёшь ЯВУ и integer. Возможно кстати данный вариант сработает быстрее, чем твой на такт-другойfunction T(A, B: integer): Boolean;
begin
B := B shl 8;
inc(B, A);
Result := Boolean((byte(B=$5a4d) or byte(B=$4d5a)) xor 1);
end;
← →
Hidden (2014-04-17 16:26) [70]7 команд, 2 регистра
function T(A, B: integer): Boolean;
begin
B := B shl 8;
inc(B, A);
Result := (B<>$634d);
dec(byte(Result), byte(B=$4d63));
end;
← →
Sha © (2014-04-17 17:42) [71]function F(A, B: integer): boolean;
asm
mov ecx,eax
imul ecx,edx
xor eax,edx
xor eax,$ffffe4fa
xor eax,ecx
inc eax
shr eax,31
end;
← →
Hidden (2014-04-17 17:58) [72]> Sha © (17.04.14 17:42) [71]
минимум 8 тактов
вариант [70] ориентировочно 6 тактов
← →
Дмитрий СС (2014-04-17 18:26) [73]
> к сожалению по условию задачи ещё нужно будет инвентировать
> бит
Невнимательно прочел, тогда так
function T2(A, B: Byte): Boolean;
asm
mov dh, al
cmp dx, $5a4d
setnz al
cmp dx, $4d5a
setnz ah
and al, ah
end;
Реально 6 команд и два регистра.
В твоем случае, компилятор со включенной оптимизацией превратил твой код примерно в то, что я написал ранее + инверсия бита
← →
Дмитрий СС (2014-04-17 18:29) [74]
> Hidden (17.04.14 16:26) [70]
P.S.
И если привести параметры функции к тем, что указаны в условиях:
function T(A, B:Byte
): Boolean;, то дельфи генерирует больше строк
Project1.dpr.12: B := B shl 8;
00419A88 0FB6D2 movzx edx,dl
00419A8B C1E208 shl edx,$08
Project1.dpr.13: inc(B, A);
00419A8E 02D0 add dl,al
Project1.dpr.14: Result := Boolean((byte(B=$5a4d) or byte(B=$4d5a)) xor 1);
00419A90 0FB6C2 movzx eax,dl
00419A93 663D4D5A cmp ax,$5a4d
00419A97 0F94C1 setz cl
00419A9A 663D5A4D cmp ax,$4d5a
00419A9E 0F94C0 setz al
00419AA1 0AC8 or cl,al
00419AA3 80F101 xor cl,$01
00419AA6 8BC1 mov eax,ecx
← →
Rouse_ © (2014-04-17 18:31) [75]
> Дмитрий СС (17.04.14 18:26) [73]
Ну да, тож вариант, или вот мой, если рассматриваем 6 строк.function T(A, B: Byte): Boolean;
asm
movzx ecx, dl
xor cl, al
imul dl
lea ecx, [eax + ecx - $1B29]
or ecx, ecx
setтz al
end;
← →
Rouse_ © (2014-04-17 19:19) [76]О!! Получилось до 5 свернуть :))
function T1(A, B: Byte): Boolean;
asm
movzx ecx, dl
xor cl, al
imul dl
lea eax, [eax + ecx - $1B29]
or al, ah
end;
← →
Rouse_ © (2014-04-17 19:24) [77]Технически наверное можно выйти на 4 строки ASM, но по всей видимости нужно придумать другой вариант получения хэша, в три уже ИМХО не реально.
← →
тупой компилятор (2014-04-17 20:00) [78]> Rouse_ © (17.04.14 19:19) [76]
так то ж не boolean :)function f076(A, B: Byte): Boolean;
asm
movzx ecx, dl
xor cl, al
imul dl
lea eax, [eax + ecx - $1B29]
or al, ah
end;
procedure TForm1.Button1Click(Sender: TObject);
var
b1, b2: byte;
begin;
for b1:=0 to 255 do
for b2:=0 to 255 do
if f076(b1, b2) xor true
then Memo1.Lines.Add(Format("%d %d",[b1, b2]));
end;
← →
Rouse_ © (2014-04-17 20:06) [79]
> тупой компилятор (17.04.14 20:00) [78]
Компилятор не тупой и работает по принципу False = 0, True = not False.
Т.о. он никогда не делает проверку с единицей, а делает прверку с нулем.
Впрочем шанс выстрелить себе в ногу он оставляет.
← →
Rouse_ © (2014-04-17 20:09) [80]Точнее "False = 0, True <> False".
Таким образом данный вариант решения полностью совпадает с изначальной постановкой, а именно - вернуть False в случае 90 и 77.
← →
Rouse_ © (2014-04-17 20:12) [81]ЗЗЫ: а побочная сверка с константой 1 (что кстати не верно, ибо TRUE не везде равно 1, и стало быть жертвуем переносимостью) есть уже навесной код за рамками функции и к самой функции не относится.
← →
тупой компилятор (2014-04-17 20:34) [82]Саш, ты не понял:
true xor true всегда должно давать false,
а что дает f076 xor true?
← →
Rouse_ © (2014-04-17 20:41) [83]
> тупой компилятор (17.04.14 20:34) [82]
Чтоб не было придирок можно вернуть изначальное условие, которое я тут не правильно поставил - функция должна возвращать ноль при входных параметрах 90 и 77 :)
← →
тупой компилятор (2014-04-17 20:45) [84]тогда не обманывай себя - пиши
function T(A, B: byte): byte;
← →
Rouse_ © (2014-04-17 20:47) [85]Дословно: "Написать алгоритм, сравнивающий строку из двух символов на равенство "MZ" или "ZM", используя не более одного if (т.е. else if использовать нельзя), имеется в виду, написать код на ассемблере, где JXX используется только при проверке и выводе результата. Алгоритм должен возвращать ноль, в случае если текущая строка не совпадает с одной из двух в условии".
Я это попытался причесать под условия Delphi, бо мало кто будет это на асме реализовавать, а задачка интересная.
← →
Rouse_ © (2014-04-17 20:48) [86]
> тупой компилятор (17.04.14 20:45) [84]
Согласен, так было бы проще, не подумал.
← →
тупой компилятор (2014-04-17 20:51) [87]это совсем другая задача, отличная от [1], и тогда все приведенные в данной ветке алгоритмы можно упростить
← →
тупой компилятор (2014-04-17 21:49) [88]например:
function TestMZ(w: word): integer;
asm
mov dh,al
mov dl,ah
imul dx
sub eax,59410
end;
← →
Rouse_ © (2014-04-17 22:21) [89]
> тупой компилятор (17.04.14 21:49) [88]
> например:
Плохой пример:program Project1;
{$APPTYPE CONSOLE}
{$R *.res}
uses
SysUtils;
function TestMZ(w: word): integer;
asm
mov dh,al
mov dl,ah
imul dx
sub eax,59410
end;
var
I: Integer;
begin
for I := 0 to $FFFF do
if TestMZ(I) = 0 then
Writeln(IntToHex(I, 4));
Readln;
end.
← →
Rouse_ © (2014-04-17 22:25) [90]ЗЫ: ну т.е. пример не выводит даже то, что должен (ибо есть нюанс :)
Грубо от перестановки типа результата ничего в итоге не поменяется (впрочем можно и поэксперементировать, кому не лень).
← →
тупой компилятор (2014-04-17 22:50) [91]у меня нормально выводит без нюансов
procedure TForm1.Button3Click(Sender: TObject);
var
i: integer;
begin
for i:=0 to $FFFF do
if TestMZ(i)=0 then
Memo1.Lines.Add(Format("%d %d",[i shr 8, i and 255]));
end;
← →
Rouse_ © (2014-04-17 23:37) [92]
> тупой компилятор (17.04.14 22:50) [91]
На ХЕ4 ничего не выводится.
← →
Rouse_ © (2014-04-17 23:48) [93]
> тупой компилятор (17.04.14 22:50) [91]
> у меня нормально выводит без нюансов
Зы, дам подсказку, в отличие от Boolean, где достаточно работы с регистром AL, здесь используется весь регистр EAX целиком, а ты в своем алгоритме работаешь только с AL/AH, а шапка может быть заполнена мусором, что в итоге приведет к ложному срабатыванию на проверке test eax, eax на выходе из твоей функции.
← →
Rouse_ © (2014-04-17 23:58) [94]Т.е. грубо все сводится к тем-же 5 строчкам ASM код с контролем старших разрядов EAX, т.к. EAX будет содержать результат от прошлых операций, на показанном выше коде, а именно значение $B9A54D5A на итерации 19802 в показанном выше примере (в виде консоли).
function TestMZ(w: word): integer;
asm
mov dh,al
mov dl,ah
imul dx
sub eax,59410
and eax, $FFFF << из-за отсутствия данной строки работать не будет
end;
← →
тупой компилятор (2014-04-17 23:59) [95]Интересное кино: у меня в D7 шапка после умножения равна нулю, даже если до умножения была ненулевая. Значит, тогда проблему решит and eax,65535
function TestMZ(w: word): integer;
asm
mov dh,al
mov dl,ah
imul dx
and eax,65535
xor eax,59410
end;
← →
Rouse_ © (2014-04-18 00:14) [96]
> тупой компилятор (17.04.14 23:59) [95]
Получим те-же 5 инструкций, а вот если результат изменить на Byte вместо Integer... ;)
← →
тупой компилятор (2014-04-18 00:18) [97]ну, могем и 4 получить
function TestMZ2(w: word): integer;
asm
mov dh,al
mov dl,ah
imul edx
sub eax,457762834
end;
← →
тупой компилятор (2014-04-18 00:20) [98]или опять шапка на XE4?
← →
тупой компилятор (2014-04-18 00:29) [99]так без шапки, но снова 5 команд
function TestMZ3(w: word): integer;
asm
mov dh,al
mov dl,ah
imul edx
and eax,65535
xor eax,59410
end;
← →
тупой компилятор (2014-04-18 00:42) [100]ларчик просто открывался
function TestMZ4(w: word): word;
asm
mov dh,al
mov dl,ah
imul dx
sub eax,59410
end;
← →
тупой компилятор (2014-04-18 02:10) [101]вот еще одно решение в 4 команды
function TestMZ5(a, b: byte): word;
asm
lea ecx, [eax+edx-167]
imul dl
xor ax, 6930
or al, cl
end;
но предыдущее лучше, т.к. там всего 1 параметр
← →
имя (2014-04-18 09:38) [102]Удалено модератором
← →
имя (2014-04-18 10:05) [103]Удалено модератором
← →
имя (2014-04-18 10:13) [104]Удалено модератором
← →
имя (2014-04-18 10:25) [105]Удалено модератором
← →
SergP © (2014-04-18 12:05) [106]
> SergP © (17.04.14 09:57) [44]
>
> > Важный нюанс, код функции не должен содержать логических
> переходов.
>
> А разве они не создаются при использовании сравнения =,
> <> ?
> Hidden (17.04.14 10:01) [45]
>
> Нет
Я об ассемблере имею ограниченное представление. Мои знания в нем ограничены знанием ассемблера 8080, Z80 + еще немножко. Поэтому возник вопрос:
a,b:byte;
c:boolean;
c:=a=b
Там имеются команды позволяющие в случае равенства получить $FF, а в случае неравенства $00 , чтобы обойтись без переходов?
← →
Ega23 © (2014-04-18 12:17) [107]
> в случае равенства получить $FF
Почему $FF? Не $00 вроде как
← →
SergP © (2014-04-18 12:20) [108]
> Ega23 © (18.04.14 12:17) [107]
>
>
> > в случае равенства получить $FF
>
>
> Почему $FF? Не $00 вроде как
ну суть в том, чтобы без переходов получить либо $00, либо $FF а не что-то другое...
← →
Ega23 © (2014-04-18 12:33) [109]Почему -1 то? True - не ноль, вроде как.
← →
SergP © (2014-04-18 12:48) [110]
> Ega23 © (18.04.14 12:33) [109]
>
> Почему -1 то? True - не ноль, вроде как.
Ну в принципе да, но что будет с этим true, если он не ноль, но и не -1 , если его придется использовать в дальнейших логических операциях, типа:
function1 or function2
true and true должно давать true
а если первый true равен допустим $10, а второй $01 то получим $00, т.е. false
← →
Ega23 © (2014-04-18 12:55) [111]
> Ну в принципе да, но что будет с этим true, если он не ноль,
> но и не -1 , если его придется использовать в дальнейших
> логических операциях, типа:
Ord(Boolean(Ordinal))
← →
Sapersky (2014-04-18 14:34) [112]
> Там имеются команды позволяющие в случае равенства получить
> $FF, а в случае неравенства $00 , чтобы обойтись без переходов?
Да:
http://faydoc.tripod.com/cpu/setz.htm
Но, как я уже писал, компилятор не всегда их применяет.
Также подобные команды есть в MMX/SSE/AVX, точнее, там команды сравнения выдают битовые маски, и на их основе делаются псевдо-ветвления.
Ещё начиная с P2 есть условный MOV (CMOV), но почему-то используют его редко.
← →
Rouse_ © (2014-04-19 12:26) [113]MBo вчера филосовски рассудил - задачки не сильно сложные и предложил модифицировать вторую из них.
Итак:
Есть массив чисел. Размер массива 2N+2. В этом массиве 2N дубликаты, а два значения уникально. Надо написать код, который найдет значение этого уникального числа за одну итерацию, т.е. за один проход. Пример ряда: "3, 1, 5, 6, 1, 3".
В этом ряду {3, 3}, {1,1} дубликаты, а 5б 6 — уникальные.
Ломаю голову уже второй час - пока простого варианта решения не наблюдаю :)
← →
Inovet © (2014-04-19 12:34) [114]> [113] Rouse_ © (19.04.14 12:26)
> который найдет значение этого уникального числа за одну итерацию
Значение этих двух уникальных чисел.
← →
Inovet © (2014-04-19 12:34) [115]> [114] Inovet © (19.04.14 12:34)
> Значение
Эти два уникальных числа.
← →
Rouse_ © (2014-04-19 12:38) [116]
> Inovet © (19.04.14 12:34) [114]
Ну да, не доконца подправил текст, ща еще раз:
Итак:Есть массив чисел. Размер массива 2N+2. В этом массиве 2N дубликаты, а два значения уникальны. Надо написать код, который найдет значение этих двух уникальных чисел за одну итерацию, т.е. за один проход.
Пример ряда: "3, 1, 5, 6, 1, 3".
В этом ряду {3, 3}, {1,1} дубликаты, а 5 и 6 — уникальные.
← →
Sha © (2014-04-19 15:29) [117]> Rouse_ © (19.04.14 12:38) [116]
> MBo вчера филосовски рассудил - задачки не сильно сложные и предложил модифицировать вторую из них.
Похоже, ты решил облечить решение )
То, что задача находится в этой ветке уже является подсказкой решающим )
> Есть массив чисел.
Хотелось бы уточнить тип и область возможных значений.
← →
Rouse_ © (2014-04-19 16:09) [118]
> Sha © (19.04.14 15:29) [117]
> Похоже, ты решил облечить решение )
> То, что задача находится в этой ветке уже является подсказкой
> решающим )
Мне это не помогло, сказывается похоже вчерашняя встреча :))
> Хотелось бы уточнить тип и область возможных значений.
Допустим, это будет массив Byte.
← →
Inovet © (2014-04-19 16:51) [119]> [118] Rouse_ © (19.04.14 16:09)
> массив Byte
Чёт там тогда делать?
← →
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]Мне кстати здается что там есть два варинта, либо Боря это делал через какую-то хитрую константу (врятли, хотя когда я спрашивал, он хитро улыбался) либо, он просто ушел в истоки, от которых работает процессор (всего две инструкции) т.е. выходим либо на штрих Шеффера, либо стрелку Пирса и там как-то хитро обиграл работу с данными, эмулируя работу того-же ксора, где есть возможность вклинится непосредственно в момент выполнения инструкции.
← →
Rouse_ © (2014-04-19 23:15) [149]ЗЫ: а может я уже просто загнался и я не вижу чего-то очевидного :))))
← →
Sha © (2014-04-19 23:16) [150]загнался
← →
Rouse_ © (2014-04-19 23:22) [151]
> Sha © (19.04.14 23:16) [150]
Сань, только одну вещь скажи - у тебя решение за 1 проход цикла?
← →
Sha © (2014-04-19 23:26) [152]да
← →
Inovet © (2014-04-20 00:23) [153]
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]Прошу прощения за орфографию.
← →
Sha © (2014-04-20 02:58) [156]> Дмитрий СС
вынудил :)
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;
← →
Sha © (2014-04-20 03:08) [157]> Дмитрий СС (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;
← →
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]
← →
MBo © (2014-04-20 20:54) [189]7 лет назад ;)
> Sha © (2007-11-16 11:53) [43]
> 5б аналогично.
> На первом проходе XOR-ом отыскиваем бит, в котором наши
> числа не совпадают.
> На втором проходе вычисляем XOR0 для всех чисел, содержащих
> 0 в этом бите, и XOR1 для чисел, содержащих 1.
> Это и будут искомые числа.
Я при решении (двухпроходном) долго упускал смысл результата первого прохода. И дотумкал, только когда подумал о значении единичных битов в нём.
← →
Romkin © (2014-04-21 12:41) [190]
> Попросили уточнить требования про два уникальных числа в
> массиве дубликатов.Числа целые 32 или 64 разряда.Хорошо
> бы решить за линейное время O(n) и с O(1) дополнительной
> памяти.(т.е. один или несколько проходов по массиву допустимы,
> и несколько вспомогательных переменных, но не, например,
> массив из n битов)
И чего тут такого?
Упорядочить по возрастанию за время O(n), пройти и посмотреть. И все: и мудрить не надо, и сколько хочешь недубликатов найдет.
← →
Sha © (2014-04-21 13:02) [191]> Romkin © (21.04.14 12:41) [190]
неизвестно, можно ли изменять массив,
плюс непонятно, как упорядочить за время O(N) и память O(1)
← →
SergP © (2014-04-21 16:22) [192]
> а где решение в 1 проход?)
Ну можно и в 1 проход сделать. Если учесть то что у нас массив значений строго определенного типа.
только решение будет некрасивое и сложное.
← →
Дмитрий СС (2014-04-21 18:42) [193]
> SergP © (21.04.14 16:22) [192]
>
Ну так в студию)
← →
Sha © (2014-04-21 19:36) [194]> Rouse_ © (19.04.14 12:26) [113]
> MBo вчера филосовски рассудил - задачки не сильно сложные и предложил модифицировать вторую из них.
Что-то меня тоже на философию потянуло.
Те же условия, решить задачу для неизвестного числа дубликатов D=0..3.
← →
Sha © (2014-04-21 19:37) [195]* НЕДУБЛИКАТОВ
← →
SergP © (2014-04-21 21:27) [196]
> Ну так в студию)
Времени нет на написание кода, да и жена злая рядом не дает компом пользоваться.
Но суть та же как и в предлагаемом решении с двумя проходами. Только вы в первом проходе ищете нужный бит, по которому выбираете данные во втором проходе. а можно сразу в одном проходе делать и общий xor, а так же и 8 xorов по всем битам, а после прохода анализировать полученные данные уже без проходов по исходному массиву
← →
SergP © (2014-04-22 11:36) [197]что-то типа этого:
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;
← →
SergP © (2014-04-22 11:42) [198][197] это на [193]
← →
SergP © (2014-04-22 11:45) [199]
> Те же условия, решить задачу для неизвестного числа дубликатов
> D=0..3.
Т.е. ты хотел сказать для "неизвестного числа недубликатов"?
думаю будет проблематично, хотя бы из-за того что одним из недубликатов вполне может быть 0
← →
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;
ещё 1while (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]
> Я решал с двумя проходами
Как это работает?
Выглядит очень круто
← →
MBo © (2014-04-25 15:32) [229]Первый цикл - сумма по модулю два (ксор) всех элементов. Парные взаимоуничтожаются, а результат будет 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)... Но они будут медленнее, чем предложенный Вами
← →
MBo © (2014-04-25 15:42) [231]>но зачем было условие про 1 проход и памяти O(1)?
Я на одном проходе не настаивал, требование было только о линейном времени и о памяти O(1)
← →
Гора Фудзияма (2014-04-25 15:45) [232]А как такой подход будет выглядеть для 3-4-5 элементов?
← →
MBo © (2014-04-25 17:22) [233]такой - никак (например, 1 xor 2 xor 3 = 0), в этих случаях уже нужны побитовые действия
← →
Гора Фудзияма (2014-04-26 14:30) [234]Не плохая идея - делать пятничные задачки
← →
junglecat (2014-04-26 14:36) [235]> делать пятничные задачки
когда-то это было здесь традицией
← →
MBo © (2014-04-30 13:28) [236]Освежим немного:
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.
← →
Sha © (2014-04-30 13:43) [237]> MBo © (25.04.14 15:04) [226]
Можно упростить вычисление маски, используя один из известных хаков
для выделения младшего ненулевого бита и вычисления его номера:
Mask:=n1 and not (n1-1);
← →
Sha © (2014-04-30 14:26) [238]> Sha © (30.04.14 13:43) [237]
Можно еще упростить, т.к. -i=1+not i, то:
Mask:=n1 and -n1;
← →
Inovet © (2014-04-30 14:54) [239]> [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;
}
← →
Inovet © (2014-04-30 14:57) [240]Да, вывод:
{V,e,r,y, ,p,r,e,t,t,y, ,l,i,s,t}
{}
{L}
{L and 2}
{S,h,L}
← →
MBo © (2014-04-30 15:06) [241]>Inovet
Идея понятна, но форматирование для случая "больше двух" не то
← →
Inovet © (2014-04-30 15:31) [242]> [241] MBo © (30.04.14 15:06)
> но форматирование для случая "больше двух" не то
А, там же надо тоже "и", ну тогда ещё проще - достаточно 2 последних помнить
Вывод:
{V,e,r,y, ,p,r,e,t,t,y, ,l,i,s and t}
{}
{L}
{L and 2}
{S,h and L}
Так есть ли способ "не тупо"?
← →
Inovet © (2014-04-30 15:37) [243]> [242] Inovet © (30.04.14 15:31)
Ну и второй тупой вариант более "медленный" - подставлять разделитель прямо в цикле, например, по значению счётчика.
← →
SergP © (2014-04-30 22:28) [244]
> Дана квадратная матрица NxN, содержащая единицы и нули.
> Требуется без использования дополнительной памяти (т.е.
> с O(1)) обнулить те столбцы и строки, в которых есть нули.
>
А тип данных в матрице позволяет присваивать элементам матрицы значения отличные от 0 и 1 ?
← →
MBo © (2014-05-01 07:23) [245]>А тип данных в матрице позволяет присваивать элементам матрицы значения отличные от 0 и 1 ?
Нет
← →
Inovet © (2014-05-01 09:39) [246]> [236] MBo © (30.04.14 13:28)
> Zero-Matrix
Идём по диагонали, смотрим стороны текущей матрицы. Если встречается 0, сбрасываем в 0 уже пройденные элементы строки или столбца. Т.о. дополнительная память не требуется, и внесённые изменения не влияют на результат.
Вроде, так должно работать.
← →
SergP © (2014-05-01 11:24) [247]Вот как-то так вроде, если я не ошибся...
Смысл в том, что сначала ищем строку N, где отсутствуют нулевые элементы.
(если такой строки нет, то всю матрицу можно обнулять).
Если есть, то запоминаем ее, проверяем все столбцы на наличие нулевых элементов и обнуляем те элементы строки N, в столбцах которых есть нулевые элементы.
Т.е. мы получили конечный вариант строки N
Далее проходим по всем строкам, кроме строки N
если в строке есть нулевой элемент, обнуляем строку, если нет - то копируем на ее место строку N
// пусть массив у нас будет Arr[0..xmax,0..ymax]
// var
// f1,f2:boolean;
// x,y,i,j,n:integer;
// ищем строку где нет нулевых элеменетов
f2:=false;
for y:=0 to ymax do
begin
f1:=true;
for i:=0 to xmax do if Arr[i,y]=0 then f1:=false;
if f1 then
begin
n:=y; // если такая строка существует то запоминаем ее в N
f2:=true;
break;
end;
end;
if f2 then
begin
// строка где нет нулевых элементов существует, ее номер в N
// проверяем все столбцы на наличие нулевых элементов
//
for x:=0 to xmax do
begin
f1:=false;
for j:=0 to ymax do if Arr[x,j]=0 then f1:=true;
// если в столбще есть нулевые элементы то обнуляем соответствующий элемент в строке N
if f1 then Arr[x,n]:=0;
end;
// проходим все строки кроме строки N
for y:=0 to ymax do
begin
if y=n then continue;
f1:=true;
for i:=0 to xmax do if Arr[i,y]=0 then f1:=false;
// Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем
for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0;
end;
// если в каждой строке имеются нулевые элементы то обнуляем весь массив
end else for x:=0 to xmax do for y:=0 to ymax do Arr[x,y]:=0;
← →
SergP © (2014-05-01 11:39) [248]ну можно еще немного оптимизировать, увеличивши размер кода.
Во первых, заменить подобные вещи (проверка строки или столбца на наличие нулевых элементов:
вместо:
f1:=false;
for j:=0 to ymax do if Arr[x,j]=0 then f1:=true;
написать:
f1:=false;
for j:=0 to ymax do if Arr[x,j]=0 then
begin
f1:=true;
break;
end;
ну и не проверять повторно строки от 0 до N во второй части:for y:=0 to ymax do
begin
if y=n then continue;
f1:=true;
for i:=0 to xmax do if Arr[i,y]=0 then f1:=false;
// Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем
for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0;
end;
а сразу их обнулять:for y:=0 to ymax do
begin
if y=n then continue;
if y<0 then for i:=0 to xmax do a[i,y]:=0 else
begin
f1:=true;
for i:=0 to xmax do if Arr[i,y]=0 then f1:=false;
// Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем
for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0;
end;
end;
← →
SergP © (2014-05-01 11:44) [249]типа так:
// ищем строку где нет нулевых элеменетов
f2:=false;
for y:=0 to ymax do
begin
f1:=true;
for i:=0 to xmax do if Arr[i,y]=0 then
begin
f1:=false;
break;
end;
if f1 then
begin
n:=y; // если такая строка существует то запоминаем ее в N
f2:=true;
break;
end;
end;
if f2 then
begin
// строка где нет нулевых элементов существует, ее номер в N
// проверяем все столбцы на наличие нулевых элементов
//
for x:=0 to xmax do
begin
f1:=false;
for j:=0 to ymax do if Arr[x,j]=0 then
begin
f1:=true;
break;
end;
// если в столбще есть нулевые элементы то обнуляем соответствующий элемент в строке N
if f1 then Arr[x,n]:=0;
end;
// проходим все строки кроме строки N
for y:=0 to ymax do
begin
if y=n then continue;
if y<0 then for i:=0 to xmax do Arr[i,y]:=0 else
begin
f1:=true;
for i:=0 to xmax do if Arr[i,y]=0 then
begin
f1:=false;
break;
end;
// Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем
for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0;
end;
end;
// если в каждой строке имеются нулевые элементы то обнуляем весь массив
end else for x:=0 to xmax do for y:=0 to ymax do Arr[x,y]:=0;
← →
SergP © (2014-05-01 11:46) [250]хм. ошибка небольшая.
вот так нужно:// ищем строку где нет нулевых элеменетов
f2:=false;
for y:=0 to ymax do
begin
f1:=true;
for i:=0 to xmax do if Arr[i,y]=0 then
begin
f1:=false;
break;
end;
if f1 then
begin
n:=y; // если такая строка существует то запоминаем ее в N
f2:=true;
break;
end;
end;
if f2 then
begin
// строка где нет нулевых элементов существует, ее номер в N
// проверяем все столбцы на наличие нулевых элементов
//
for x:=0 to xmax do
begin
f1:=false;
for j:=0 to ymax do if Arr[x,j]=0 then
begin
f1:=true;
break;
end;
// если в столбще есть нулевые элементы то обнуляем соответствующий элемент в строке N
if f1 then Arr[x,n]:=0;
end;
// проходим все строки кроме строки N
for y:=0 to ymax do
begin
if y<n then for i:=0 to xmax do Arr[i,y]:=0;
if y>n then
begin
f1:=true;
for i:=0 to xmax do if Arr[i,y]=0 then
begin
f1:=false;
break;
end;
// Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем
for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0;
end;
end;
// если в каждой строке имеются нулевые элементы то обнуляем весь массив
end else for x:=0 to xmax do for y:=0 to ymax do Arr[x,y]:=0;
← →
Sha © (2014-05-01 12:50) [251]
const
h= 4;
type
TElement= byte;
var
m: array[0..h, 0..h] of TElement= (
(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));
procedure TForm1.Button3Click(Sender: TObject);
var
col0: TElement;
i, j: integer;
begin;
col0:=1;
for i:=0 to h do begin;
if m[i,0]=0 then col0:=0;
for j:=1 to h do if m[i,j]=0 then begin;
m[i,0]:=0;
m[0,j]:=0;
end;
end;
for j:=1 to h do if m[0,j]=0 then for i:=1 to h do m[i,j]:=0;
for i:=0 to h do if m[i,0]=0 then for j:=1 to h do m[i,j]:=0;
if col0=0 then for i:=0 to h do m[i,0]:=0;
//for i:=0 to h do Memo1.Lines.Add(Format("%d %d %d %d %d",
// [m[i,0],m[i,1],m[i,2],m[i,3],m[i,4]]));
end;
← →
Гора Фудзияма (2014-05-05 15:19) [252]Удалено модератором
← →
KSergey © (2014-05-06 12:52) [253]> Rouse_ © (16.04.14 23:26) [26]
> Result := (A * B - 6930 + (A xor B) - 23) <> 0;
Byte * Byte дает Integer ??
сволочи
← →
Sha © (2014-05-07 20:26) [254]> KSergey © (06.05.14 12:52) [253]
Это так для всей арифметики, а если один операнд int64 - то и результат int64.
Для логики иначе.
← →
Sha © (2014-05-07 21:55) [255]
function Not1(a: byte): integer;
begin;
Result := not (a or 0); //= not byte(a)
end;
function Not2(a: byte): integer;
begin;
Result := not (a+0); //неожиданный, но соответствующий описанию результат = not integer(a)
end;
function Shl1(a: byte): integer;
begin;
Result := byte(a shl 8); //=byte(integer(a) shl 8)
end;
function Shl2(a: byte): integer;
begin;
Result := a shl 8; //ожидаемый, но не соответствующий описанию результат = integer(a) shl 8
end;
procedure TForm1.Button8Click(Sender: TObject);
begin;
ShowMessage(IntToStr(Not1(1)));
ShowMessage(IntToStr(Not2(1)));
ShowMessage(IntToStr(Shl1(1)));
ShowMessage(IntToStr(Shl2(1)));
end;
← →
Sha © (2014-05-14 13:49) [256]Не поднять ли нам ветку?
За один проход по элементам целочисленного массива найти 0..5 непарных чисел.
Это типа намек как решать [208].
← →
han_malign (2014-05-15 12:52) [257]
> За один проход по элементам целочисленного массива найти 0..5 непарных чисел.
{1 shl k, 1 shl m, 1 shl k + 1 shl m, n, n}
- ну нету медианы...
← →
Sha © (2014-05-15 14:00) [258]вроде и не требуется она для решения
← →
Дмитрий СС (2014-05-15 18:36) [259]А была тут такая задача:
Известны A и B:
A = x xor y
B = x + y
Найти x и y.
← →
Sha © (2014-05-16 00:48) [260]> Дмитрий СС (15.05.14 18:36) [259]
может получиться довольно много решений
← →
han_malign (2014-05-16 08:50) [261]
> вроде и не требуется
- в задаче о 2-х - медиана - это один из битов разницы, по которому надо делить свертку выборки...
позволяет обойтись честным O(1) по памяти(с двумя проходами)
- свертка по всем срезам [бит,значение] - вроде позволяет найти все значения(и не факт что 5 - предел)...
но если по правильному(N => ∞) - это все-таки O(ln N) - по памяти...
(т.к. с таким же успехом можно заявить, что 512 Mб битовая строка - это O(1) - т.к. не зависит от N)
← →
Sha © (2014-05-16 09:27) [262]> han_malign (16.05.14 08:50) [261]
Тем не менее это ничуть не мешает решает решить задачу поиска трех чисел ценой увеличения количества проходов или памяти в b раз (b - количество используемых битов в числах).
По моим экспериментам, похожим образом задача решается для 4, 5 и 6 чисел. Дальше не смотрел, т.к. там довольно громоздко все получается и в лоб уже не выходит вроде.
Для 4 чисел есть строгое доказательство и решение в 1 проход. Небольшой намек на решение дан в конце статьи в блоге.
Страницы: 1 2 3 4 5 6 7 вся ветка
Форум: "Прочее";
Текущий архив: 2014.12.14;
Скачать: [xml.tar.bz2];
Память: 1.21 MB
Время: 0.132 c