|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : OAM 2:5020/400 21 Aug 2001 18:29:36
To : All
Subject : Re: Разложение числа на квадраты
--------------------------------------------------------------------------------
Может быть, как нибудь идти другим путем?
То есть составлять все суммы трех квадратов; таким путем получим все числа.
Кстати, массив квадратов для 10е12 получается один миллион штук - совсем
немало при длине, скорее всего, 8 байт на элемент.
Андрей
Я , прошу прощения, не гений...
Andrew Doroshew пишет
> Hадо последовательно, начиная с некоторого числа (порядка 10e9 -10e12),
> получать разложение этого числа на сумму трёх квадратов, и выдавать для
> дальнейшего применения приблизительно следующее:
> 8;0
> 9;3
> 1,2,2; 2,1,2; 2,2,1;
> 10;0
> 11;3
> 1,1,3; 1,3,1; 3,1,1;
> Перебор с некоторой оптимизацией - хранение таблицы квадратов - сильно
> тормозит. Можно и ещё чуток улучшить - запоминать раздоления на пару
> квадратов, но это потребует много памяти, и серьёзного улучшения не
> даст.
> Уверен, что есть более подходящий алгоритм. Часто нужно только
> количество разложений данного числа, а сами разложения вычислять не
> нужно.
> С благодарностью принимаются мысли, ссылки, ключевые слова для поиска.
--- ifmail v.2.15dev5
* Origin: Comint Ltd (post does not reflect views of Comint Ltd) (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Разложение числа на квадраты 
