|
Существует ли алгоритм нахождения натуральных x,y таких, чтобы выражение $$\sqrt{x}+\sqrt{y}\approx \sqrt{m}$$ являлось лучшим нижним приближением, где m - простое >3. Для составного m существует аналитическое решение, которое не выкладываю, поскольку интерес к теме пропадает сразу (проверено на практике). Замечу только, что для составного m, свободного от квадратов, выполняется $$(x-y)^2\equiv 1\ (mod\ m)$$ и решение задачи вряд ли может быть простым, хотя к NP-полным ее вроде бы не относят. Последнее утверждение обсуждать не берусь. задан 4 Июл '12 12:44 
Андрей А |
|
Если этот алгоритм для компьютера, то он существует и несложный: двойной цикл по х и у и сравнение выражений слева и справа. отвечен 4 Июл '12 19:05 
Anatoliy Перебор с проверкой на лучшее приближение.
(4 Июл '12 20:37)
Anatoliy
Перебор не такой уж большой, поскольку x и y ограничены числом m. А зачем цикл делать двойной? По x находим y, округляем, потом смотрим погрешность.
(5 Июл '12 0:16)
DocentI
Ну что ж, простенько и со вкусом.
(5 Июл '12 12:13)
Андрей А
|