|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Kadatch 2:5020/400 12 May 2001 12:01:57
To : All
Subject : Re: найти переменную...
--------------------------------------------------------------------------------
> можно ли(и как) найти b зная bb1 и bb0 имея:
>
> bb1=(bb0+b) xor (bb0-b)
Можно. Перебором с возвращениями от младших битов к старшим.
Предупреждение: для большинства пар (bb0, bb1) существует много b,
удовлетворяющих вышеприведенному равенству.
См. текст примитивного поиска ниже. Поскольку тратить на это
больше 10 минут не хочется, избавиться от хвостовой рекурсии и
получить все решения (а не только первое попавшееся) предлагается
читателю.
#include <stdio.h>
#include <stdlib.h>
// find b such that b1 = (b0 + b) ^ (b0 - b)
// return 1 if such b exist, 0 otherwise
int FindB (int *pb, int b0, int b1, int b, int m)
{
if (m == -1)
{
*pb = b;
return (1);
}
m = m*2 + 1;
if ((b1 & m) == (((b0 + b) ^ (b0 - b)) & m))
{
if (FindB (pb, b0, b1, b, m))
return (1);
}
b += m ^ (m >> 1); // try to set next bit to 1
if ((b1 & m) == (((b0 + b) ^ (b0 - b)) & m))
return (FindB (pb, b0, b1, b, m));
return (0);
}
int main (void)
{
int i, b, b0, b1, br;
for (i = 0; i < 10; ++i)
{
b = rand ();
b0 = rand ();
b1 = (b0 + b) ^ (b0 - b);
printf ("b0=0x%x b=0x%x b1=0x%x\n", b0, b, b1);
if (!FindB (&br, b0, b1, 0, 0))
printf ("oops, expecting %x\n", b);
else if (br == b)
printf ("exact match\n");
else
{
printf ("got br=0x%x, expecting b=0x%x\n", br, b);
b = (b0 + br) ^ (b0 - br);
if (b != b1)
printf ("oops: got f(br)=0x%x, expecting f(b)=0x%x\n", b, b1);
else
printf ("result is the same\n");
}
}
return (0);
}
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: найти переменную... 
