|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Kluchnikov Eugene 2:5003/39.64 06 Mar 2003 13:52:14
To : Vjacheslav Maslov
Subject : задачка: A^3+B^3+C^3=D^3
--------------------------------------------------------------------------------
VM> Хочу предложить такую задачку: найти все натуральные числа меньшие
VM> 1000, которые удовлетворяют уравнению:
VM> A^3+B^3+C^3=D^3.
VM> Мой вариант решения такой:
VM> 1. Составляем таблицу кубов чисел от 1 до 1000 - Cubes.
Задачу можно выразить и по другому A^3+B^3=D^3-C^3
Затем по таблице кубов делаем список ПЧ (500*999)
Затем делаем список ЛЧ (меньше 500*999, наверно около 250*999, ведь нам не
нужны такие суммы, которые больше максимальной разности)
Сортируем оба списка (только не пузырьком - надо за время ~N*log(N)).
По отсортированному списку нетрудно найти совпадающие. Если в списке кроме
значения есть и исходные числа, то их можно выписать.
Получили сложность O(N^2*log(N)), в пределе это намного меньше, но константа
может быть нехорошая.
_WBR_, _/*Eustas*/_.
--- I.Diamond
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
