Обратить функцию.

Сейчас на форуме: asfa, _MBK_ (+6 невидимых)

Посл.ответ	Сообщение
4t Ранг: 38.3 (посетитель) Активность: 0.02↘0 Статус: Участник	Создано: 14 января 2010 22:57 · Поправил: 4t · Личное сообщение · #1 Всем привет, с прошедшими и будущими праздниками! Тут такое дело , в одной проге попалась жизненно важная функция, без которой ну никак. Уж очень она нужна. Но загвоздка стала в том, что чет ее обратить не получается. Вроде простенькая, и кода немного требует, ан не дается. Сначала думал решил задачку, при значении индексов 123456 или 654321, получался исходный массив. Но поигравшись с параметра понял, что косячу. Сейчас так наигрался с реверсом этой функции, что код даже при 123456 хрень полнейшую выдает. В общем запарился. Что я имею: Значит параметры функции следующие: на входе: 1.) - массив из 7 байт // например (a0, a1, a2, a3, a4, a5, a6) 2.) - 6 значное число. // где цифры этого чила - индексы перестановки, допустимые значения цифр которых: 0-6, цифры уникальны в пределах данного числа, например 123456 на выходе: 1.) тот же самый массив, но с другим расположением элементов // (a6, a0, a1, a2, a3, a4, a5) Можно заметить, что количество индексов не соответствует размеру массива ). В этом думаю и загвоздка. В позицию отсутствующего индекса в массиве, в данном примере - 0, вставляется шестой элемент исходного массива. Вот мое творение, всё это дело реализующее, рипнуто под pascal, для вычислений использую Algebrus, весит 2мб, код можно в него вставить и будет работать: Code: program SortArrayAvers; var imput :array [0..6] of byte = ($a0,$a1,$a2,$a3,$a4,$a5,$a6); // <- сортируемый массив, пример SortParametrs :integer = 123456; // <- индексы, пример output,check :array [0..6] of byte; SortIndex :array [0..5] of byte; i :integer; s :string; begin // заполняем значения индексов перестановки for i:= 0 to 5 do begin SortIndex[5-i]:= SortParametrs mod 10; SortParametrs:= SortParametrs div 10; end; // перестановка массива for i:= 0 to 5 do begin output[SortIndex[i]]:= imput[i]; check[SortIndex[i]]:= 1; // метка, что сюда уже записывали end; // в какую ячейку не записывали? < - imput[6] for i:= 0 to 6 do if check[i] = 0 then output[i]:= imput[6]; // печатаем for i:= 0 to 6 do s:= s + Hex(imput[i]) + ' '; write(s, ' < - imput'); // сортируемый массив s:=''; for i:= 0 to 5 do s:= s + Hex(SortIndex[i]) + ' '; write(s, ' < - параметры сортировки'); // параметры сортировки s:=''; write ('результат ='); for i:= 0 to 6 do s:= s + Hex(output[i]) + ' '; write(s,' < - output'); // отсортированный массив s:=''; for i:= 0 to 6 do s:= s + Hex(check[i]) + ' '; write(s); // метки end. Задача. Имея индексы и изменненый массив, надо получить оригинальный массив. Пример: ($a0,$a1,$a2,$a3,$a4,$a5,$a6) < - оригинальный 230456 a2, a6, a0, a1, a3, a4 ,a5 634021 a3, a5, a4, a1, a2, a6, a0

mak Ранг: 673.3 (! !), 400thx Активность: 0.4↘0.31 Статус: Участник CyberMonk	Создано: 15 января 2010 16:23 · Поправил: mak · Личное сообщение · #2 судя по описанию задача сводится к инверсии или инвертированию массива байт , с учетом заполнености , подобного кода в инете и описания очень много по запросу инвертирование массива. 4t пишет: Задача. Имея индексы и изменненый массив, надо получить оригинальный массив. Скорее всего ты имеешь ввиду индексную сортировку или индексную инверсию , по этому запросу можно поискать в нете примеры ----- RE In Progress [!] Coding Hazard [!] Stay Clear of this Cube
4t Ранг: 38.3 (посетитель) Активность: 0.02↘0 Статус: Участник	Создано: 15 января 2010 20:20 · Личное сообщение · #3 mak Ну да, аверс функции - получается индексная сортировка. За исключением отсутствия одного индекса. Отсортировать то не проблема. Проблема получить из тех же самых индексов и отсортированного массива - исходный массив. По крайней мере у меня пока не получается. Пробую на бумажке, для одних параметров нахожу алго, меняю индексы, и всё - алго не катит. Поискал в инете, там куча про сортировку, и индексную тоже, про то как обратить не написано. Собственно искал по теме ещё до того, как задать вопрос здесь. Пока в аверсе имею следующее, далее дело не идёт. условие выполняется всегда: исходный_м[6]:= отсортированный_м[отсутствующий_индекс] Мож кто-нить попробует осилить, кода то немного. Если надо, выложу оригинальный asm листинг этой функции.
mak Ранг: 673.3 (! !), 400thx Активность: 0.4↘0.31 Статус: Участник CyberMonk	Создано: 15 января 2010 21:34 · Личное сообщение · #4 4t пишет: выложу оригинальный asm листинг этой функции =) сразу надобыло , выкладывай конечно , про индексную сортировку я посмотрю у себя , у меня был материал ----- RE In Progress [!] Coding Hazard [!] Stay Clear of this Cube
4t Ранг: 38.3 (посетитель) Активность: 0.02↘0 Статус: Участник	Создано: 15 января 2010 23:49 · Личное сообщение · #5 Усё, осилил, оказалось не так уж и сложно. Получилось примерно так: Code: program SortArrayRevers; var imput :array [0..6] of byte = ($a6,$a5,$a4,$a3,$a2,$a1,$a0);// <- сортируемый массив, пример SortParametrs :integer = 654321; // <- индексы, пример output,check,InvIndex :array [0..6] of byte; SortIndex :array [0..5] of byte; i :integer; s :string; begin // заполняем значения индексов перестановки for i:= 0 to 5 do begin SortIndex[5-i]:= SortParametrs mod 10; SortParametrs:= SortParametrs div 10; end; //инверсия индексов for i:= 0 to 5 do begin InvIndex[SortIndex[i]]:= i; end; // поиск отсутствующего индекса for i:= 0 to 5 do check[SortIndex[i]]:= 1; // метка, что индекс присутствует for i:= 0 to 6 do if check[i] = 0 then InvIndex[i]:= 6; // запись отсутствующего индекса // сортировка массива for i:= 0 to 6 do begin output[InvIndex[i]]:= imput[i]; end; // для отладки // печатаем for i:= 0 to 6 do s:= s + Hex(imput[i]) + ' '; write(s, ' < - imput'); // сортируемый массив s:=' '; for i:= 0 to 5 do s:= s + Hex(SortIndex[i]) + ' '; write(s, ' < - параметры сортировки'); // параметры сортировки s:=''; write ('результат ='); for i:= 0 to 6 do s:= s + Hex(output[i]) + ' '; write(s,' < - output'); // массив s:=''; for i:= 0 to 6 do s:= s + Hex(check[i]) + ' '; write(s); // метки s:=''; for i:= 0 to 6 do s:= s + Hex(InvIndex[i]) + ' '; write(s); end.
4t Ранг: 38.3 (посетитель) Активность: 0.02↘0 Статус: Участник	Создано: 15 января 2010 23:54 · Личное сообщение · #6 mak вот листинг Code: sub_1001A190 proc near Check_Array_4 = dword ptr -14h Check_Array_3 = dword ptr -10h Output_Array_2 = dword ptr -0Ch Output_Array_1 = dword ptr -8 local_0 = dword ptr -4 sub esp, 14h mov eax, dword_1005C5FC xor eax, esp mov [esp+14h+local_0], eax push ebx xor ebx, ebx push esi mov esi, ecx mov byte ptr [esp+1Ch+Check_Array_4], bl mov byte ptr [esp+1Ch+Check_Array_4+1], bl mov byte ptr [esp+1Ch+Check_Array_4+2], bl mov byte ptr [esp+1Ch+Check_Array_4+3], bl mov byte ptr [esp+1Ch+Check_Array_3], bl mov byte ptr [esp+1Ch+Check_Array_3+1], bl mov byte ptr [esp+1Ch+Check_Array_3+2], bl xor ecx, ecx loc_1001A1C2: mov eax, ecx and eax, 80000001h jns short loc_1001A1D0 dec eax or eax, 0FFFFFFFEh inc eax loc_1001A1D0: mov eax, ecx cdq jnz short loc_1001A1E3 sub eax, edx sar eax, 1 movzx eax, byte ptr [eax+esi+7] ; < ESI указывает на сортируемый массив; ESI + 7 на индексы shr eax, 4 jmp short loc_1001A1EF ; ---------------------------------------------------------------------- ----- loc_1001A1E3: sub eax, edx sar eax, 1 movzx eax, byte ptr [eax+esi+7] and eax, 0Fh loc_1001A1EF: cmp eax, 6 jg short loc_1001A24B cmp byte ptr [esp+eax+1Ch+Check_Array_4], bl jnz short loc_1001A24B mov dl, [esi + ecx] inc ecx cmp ecx, 6 mov byte ptr [esp+eax+1Ch+Check_Array_4], 1 mov byte ptr [esp+eax+1Ch+Output_Array_2], dl jl short loc_1001A1C2 xor eax, eax cmp byte ptr [esp+1Ch+Check_Array_4], bl jz short loc_1001A21B loc_1001A214: inc eax cmp byte ptr [esp+eax+1Ch+Check_Array_4], bl jnz short loc_1001A214 loc_1001A21B: movzx ecx, byte ptr [esi+6] mov byte ptr [esp+eax+1Ch+Output_Array_2], cl mov edx, [esp+1Ch+Output_Array_2] movzx ecx, byte ptr [esp+1Ch+Output_Array_1+2] mov ax, word ptr [esp+1Ch+Output_Array_1] mov [esi], edx mov [esi+4], ax mov [esi+6], cl pop esi pop ebx mov ecx, [esp+14h+local_0] xor ecx, esp call sub_1002F990 add esp, 14h retn ; ---------------------------------------------------------------------- ----- loc_1001A24B: mov ecx, [esp+1Ch+local_0] ; // проверку не прошли mov byte ptr [esi+24h], 1 pop esi pop ebx xor ecx, esp call sub_1002F990 add esp, 14h retn sub_1001A190 endp Но теперь появилась другая проблема - генерация этих самих индексов. То бишь нужно сгенерировать шестизначное число из не повторяющихся цифр. Причем рандомно. Есть предложения?
Neo32 Ранг: 19.9 (новичок) Активность: 0.02↘0 Статус: Участник	Создано: 16 января 2010 02:43 · Поправил: Neo32 · Личное сообщение · #7 В цикле от 1 до 6 получи случайный индекс и если в массиве по этому индексу 0 то пиши туда если Нет получай новый случайный индекс или как вариант используй уже забитый массив и получай случайный индекс(количество перестановок равно факториалу 6)
mak Ранг: 673.3 (! !), 400thx Активность: 0.4↘0.31 Статус: Участник CyberMonk	Создано: 16 января 2010 15:07 · Поправил: mak · Личное сообщение · #8 Рандомный генератор , по одному числу , со сканом строки на имеющиеся символы ..можно на асме уложится в строчек 15 пс. выше тоже тему говорят , но смотря что имено ты генишь =) ..какое число ----- RE In Progress [!] Coding Hazard [!] Stay Clear of this Cube
Neo32 Ранг: 19.9 (новичок) Активность: 0.02↘0 Статус: Участник	Создано: 16 января 2010 18:07 · Поправил: Neo32 · Личное сообщение · #9 mak сорри за неточность )), вот код демонстрирующий указанный в посте №7 алгоритм Code: // for unix fpc compiler =))))) program myrandom; var a1:array [1..6] of byte; i,n:byte; begin randomize; for i:=1 to 6 do a1[i]:=0; for i:=1 to 6 do begin repeat n:=random(6)+1; until a1[n]=0; a1[n]:=i; end; for i:=1 to 6 do write(a1[i]); readln; end.
4t Ранг: 38.3 (посетитель) Активность: 0.02↘0 Статус: Участник	Создано: 16 января 2010 20:58 · Личное сообщение · #10 mak пишет: но смотря что имено ты генишь =) ..какое число 6 знаков, от 0 до 6, в первом посте написано ). Neo32 Код работает, ток нолик не генерит )... mak, Neo32 спасиб за ответы. Решения найдены. За сим тему закрываю.

Для печати