Приветствую Вас, Гость! Регистрация RSS

Команда фрилансеров

Воскресенье, 24.11.2024
Главная » 2015 » Сентябрь » 11 » Пропавшие числа
07:13
Пропавшие числа
Продолжая тему о пропавших числах, как и обещал, выкладываю работающий вариант однопроходного решения. Все входящие числа и их квадраты вычитаем из заранее известных сумм всех чисел диапазона и в результате строим следующие суммы: Sum = A+B+C+D Xor = A ^ B ^ C ^ D Sq = A*A + B*B + C*C + D*D но эти суммы строятся таблично для всех N битов по следующей схеме: Если в числе X включен бит i, то Init: %8x \r",a); } while (a); Sum 0 Xor 0 | Sum 1 Xor 1 | Squares Sum \n"); printf("------------------+-------------------+-------------\n"); for (int %8i %8x | %8i %8x | %8x%8x \n",(DWORD)g_Sums[0][b],g_Xors[0][b], (DWORD)g_Sums[1][b],g_Xors[1][b],(DWORD)(g_Sq[1][b]>>32),(DWORD)g_Sq[1][b]); } } void GetNumbers(DWORD *Values) { int Precalc ,GetTickCount()-dwTick); DumpTable(); for (DWORD solution = %8x %8x %8x %8x\n",v[0],v[1],v[2],v[3]); }Кроме всего прочего алгоритм симметричен, для него не важно, каким образом построена таблица Sums/Xors/Sq - ее можно строить как вычитанием из максимума, так и сложением всего четырех известных чисел, результат будет один и тот же. Это удобно использовать при проверке всех возможных комбинаций чисел. void InitKnown() { memset(g_Sums,0,sizeof g_Sums); memset(g_Xors,0,sizeof g_Xors); memset(g_Sq,0,sizeof g_Sq); %x %x %x %x total:%i speed:%i \r",x1,x2,x3,x4,total,speed); } DWORD false: %x %x %x %x \n",y1,y2,y3,y4); return; } } } } } printf("\nComplete \n"); }
Просмотров: 433 | Добавил: admin | Рейтинг: 0.0/0
Всего комментариев: 0
Войдите:
avatar