Ради интереса я реализовал кое-какие математические штуки на C++ и пытался реализовать Fermats. Метод факторизации, однако я не знаю, понимаю ли я, что он должен возвращать. Эта реализация, которая у меня есть, возвращает 105
для номера примера 5959, указанного в статье Википедии.
Псевдокод в Википедии выглядит так:
Пробуют разные значения a, надеясь, что это квадрат.
FermatFactor(N): // N should be odd
a → ceil(sqrt(N))
b2 → a*a - N
while b2 isn't a square:
a → a + 1 // equivalently: b2 → b2 + 2*a + 1
b2 → a*a - N // a → a + 1
endwhile
return a - sqrt(b2) // or a + sqrt(b2)
Моя реализация на С++ выглядит так:
int FermatFactor(int oddNumber)
{
double a = ceil(sqrt(static_cast<double>(oddNumber)));
double b2 = a*a - oddNumber;
std::cout << "B2: " << b2 << "a: " << a << std::endl;
double tmp = sqrt(b2);
tmp = round(tmp,1);
while (compare_doubles(tmp*tmp, b2)) //does this line look correct?
{
a = a + 1;
b2 = a*a - oddNumber;
std::cout << "B2: " << b2 << "a: " << a << std::endl;
tmp = sqrt(b2);
tmp = round(tmp,1);
}
return static_cast<int>(a + sqrt(b2));
}
bool compare_doubles(double a, double b)
{
int diff = std::fabs(a - b);
return diff < std::numeric_limits<double>::epsilon();
}
Что он должен вернуть? Кажется, просто возвращается a + b
, что не является фактором 5959
?
ИЗМЕНИТЬ
double cint(double x){
double tmp = 0.0;
if (modf(x,&tmp)>=.5)
return x>=0?ceil(x):floor(x);
else
return x<0?ceil(x):floor(x);
}
double round(double r,unsigned places){
double off=pow(10,static_cast<double>(places));
return cint(r*off)/off;
}
static_cast<double>(b2)
? Там есть причина? Также как определяетсяcompare_doubles
? - person jli   schedule 07.05.2012b2
былint
в моей предыдущей реализации, позвольте мне изменить его, у него больше нет причин для существования - person Tony The Lion   schedule 07.05.2012tmp
иb2
. Чтобы тесты прошли, вам в любом случае нужен целочисленный квадратный корень изb2
. На самом деле реализация с целыми числами для всех локальных переменных возвращает 101. :) - person vhallac   schedule 07.05.2012