Подскаите алгоритм

[ex-ch-cat325.livejournal.com]

Подскажите что почитать чтобы разработать алгоритм для решения следующей задачи:

есть исходное двоичное число определенной размерности
есть массив с числами той же размерности
найти последовательность применения операции исходное_число=исходное_число XOR число из массива
чтобы в результате получилось ноль.

Comments

[alex-djk1.livejournal.com]

Массив большой?

[ex-ch-cat325.livejournal.com]

числа 32-х битные
массив 36 элементов

[alex-djk1.livejournal.com]

Чето пока ниче в голову не лезет :)
Задача чисто абстрактна или имеет конкретное практическое применение?

[ex-ch-cat325.livejournal.com]

А черт его знает, друг попросил, зачем не колется )

[alex-djk1.livejournal.com]

Вообще ниче не лезет в голову кроме прямого перебора. Он не подойдет? Вариантов не очень много.

[ex-ch-cat325.livejournal.com]

не, 36! это очень много ) при этом не обязательно 36, ведь может быть так
что сначала
x= x xor m[1]
x= x xor m[3]
x= x xor m[2]
x= x xor m[1]
и так далее...

[alex-djk1.livejournal.com]

Ну для начала xor коммутативен. То есть a ^ b = b ^ a.
Это во первых.
Во вторых счас попробую че-нить написать. Секунду.

[alex-djk1.livejournal.com]

DWORD nums[32]; // Исходные числа (чисел 32, а не 36, так как я
не скажу, как там задать long long int)

Тут сразу надо сделать
for( index = 0; index < 32; index++ )
nums[index] = nums[index] ^ исходное_число;

Функция вычисляет xor между исходными числами.
Числа выбираются как соответствующие биты
DWORD CalcXored( DWORD bits )
{
DWORD r = 0, index;
for( index = 0; index < 32; index++, bits = bits >> 1 )
if (bits & 1)
{
r = r ^ nums[index];
}

return r;
}

struct tagNum // структура для кеширования
{
DWORD xored_num;
DWORD index
};

Сначала взять первые 16 чисел (к примеру) и рассчитать TNums XoredNums[2 << 16] массив (размера 2^16 соответственно) вида
Сначала:
for( index = 0; index < (2 << 16); index++ )
{
Nums[index].index = index;
Nums[index].xored_num = CalcXor( DWORD bits )
}
Отсорировать массив по xored_num
Теперь берем остальные числа
for( index = 0; index < (2 << 16); index++ )
// тут уже надо не 2 << 16, а 2 << 20 ( тк 36-16=20 )
{
t = CalcXor( index << 16 );
Потом бинарный поиск в массиве XoredNums по полю xored_num.
Если нашли - результат найден. Числа, которые надо взять будут числа
(index << 16) | nums[ найденное ].index;
Если нет - продолдаем цикл.
}

Займет это всего О(16) + О(20) * ln( 2^16 ) циклов.
То есть О(20). Вот так вот примерно.

[alex-djk1.livejournal.com]

С оценкой я че-то капитально не то написал :)
В общем будет 2^16 + 2^20 * O(16) итераций.

[ex-ch-cat325.livejournal.com]

Я тоже сейчас алгоритмик один проверю

[ex-ch-cat325.livejournal.com]

спасибо )

[alex-djk1.livejournal.com]

Да не за что.
Помогло?

[ex-ch-cat325.livejournal.com]

да я что то не подумал что xor коммутативен, то есть это меня запутали )
то есть последовательность не важна, важно лишь какие числа брать...
таким образом количество проверок при переборе = 2^36, что не очень-то и много...

[alex-djk1.livejournal.com]

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

[maleorca.livejournal.com]

Решение навскидку не подскажу, но думаю, что результативнее будет искать решение этой задачи в формулировке (надеюсь, я правильно понял, о чём идёт речь):
A₀*x₀ ⊕ A₁*x₁ ⊕ ... ⊕ A_n*x_n = C
Где A_i — числа из массива, C — исходное число, x_i принимают значения 1 или 0, ⊕ — операция XOR. Предполагаю, что копать нужно в сторону решения линейных уравнений и дискретной математики.

[ex-ch-cat325.livejournal.com]

да, да, мне уже по аське подсказали... щас думаю.