#include <stdio.h>
#include <math.h>
extern "C" unsigned char _BitScanForward (unsigned *, unsigned __int32);
#pragma intrinsic (_BitScanForward)
static unsigned looking4sum_gray (unsigned length, const double array[], const double target)
{
// минимальная проверка
if (length < 1|target <= 0.0)
return 0;
double flip[32];
unsigned pos, i, j;
char tab[32];
double sum;
// компируем элементы, фильтруя ненужные и проверяя единичные случаи
sum = 0.0; i = length; length = 0; do {
i--;
if (array[i] == target)
return 1u << i;
if (array[i] < target) {
sum += array[i];
tab[length] = i;
flip[length] = array[i];
if (++length > 32)
return 0;
}
} while (i);
if (length < 2)
return 1u << tab[0];
// проверяем парные случаи, это несравнимо быстрее полного перебора
i = 0; do {
j = i + 1; do {
if (flip[i] + flip[j] == target)
return (1u << tab[i]) + (1u << tab[j]);
} while (++j < length);
} while (++i < length - 1);
// счетчик для перебора
pos = (1ul << length) - 1;
if (length == 32)
pos = ~0u;
unsigned best_gray, gray;
if (sum <= target)
// наилучший вариант - сумма всех слагаемых меньших target
best_gray = pos;
else {
// полный перебор кодом Грея
double best_diff = fabs (target);
gray = best_gray = 0; sum = 0.0; do {
j = gray;
gray = pos ^ (pos >> 1);
j ^= gray;
_BitScanForward (&i, j);
sum += flip[i];
flip[i] = -flip[i];
double diff = fabs (sum - target);
if (diff < best_diff) {
best_gray = gray;
best_diff = diff;
if (diff == 0.0)
break;
}
} while (--pos);
}
// конвертируем индексы слагаемых (с учетом пропусков и обратного порядка)
gray = i = 0; do {
if (best_gray & 1)
gray |= 1u << tab[i];
i++;
} while (best_gray >>= 1);
return gray;
}
static unsigned looking4sum_gray_test (const unsigned length, const double array[], const double target)
{
unsigned gray = looking4sum_gray (length, array, target);
double test = 0.0;
for (unsigned i = 0; gray; i++) {
if (gray & 1)
test += array[i];
gray >>= 1;
}
printf ("target %f, result %f, error %f\n", target, test, target - test);
return gray;
}
int main (int argc, char* argv[])
{
static const double test_array[32] = {
6015.8208, 9489.67893, 83.219879, 848.9457, 163.978846,
371946.92, 741.743057, 72464.5683, 45.675712, 56.129234, 89412.3127,
479.74316, 9874.652, 17649.589146, 6565.98146, 79.846252, 854764,
4523.574, 43576.945, 86.9871396, 451513.3424, 52.1619388, 131624,
464.9687, 74592.1453, 697.1834745, 637.195, 44535,
3476.91274, 4123.1237, 3102.982, 769.8498
};
looking4sum_gray_test (32, test_array, 23534.9999);
return 0;
}
---
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
