|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 07 Mar 2003 23:54:52
To : Vjacheslav Maslov
Subject : Re: задачка: A^3+B^3+C^3=D^3
--------------------------------------------------------------------------------
Однажды 06-Mar-03 в 00:15 Vjacheslav Maslov (2:5000/231.60)
написал All по поводу
-=- задачка: A^3+B^3+C^3=D^3 -=-
VM> /*Доброго времени суток*/, All !
VM> Хочу предложить такую задачку: найти все натуральные числа меньшие 1000,
VM> которые удовлетворяют уравнению:
VM> A^3+B^3+C^3=D^3.
VM> Мой вариант решения такой:
VM> 1. Составляем таблицу кубов чисел от 1 до 1000 - Cubes.
VM> 2. Затем тройной цикл:
VM> for a:=1 to N do
VM> for b:=1 to N do
VM> for c:=1 to N do begin
VM> if Search(Cubes[a]+Cubes[b]+Cubes[c]) then //найдено решение
VM> writeln(...)
VM> end;
VM> Где Search(x) - бинарный поиск числа x в массиве Cubes.
VM> Работает, но медленно где-то 5-7 минут. Один мой знакомый утверждает, что
VM> придумал алгоритм решения этой задачи, который отрабатывает за 2 сек на
VM> машине класса P III.
VM> Возможно ли?
Kонечно возможно.
1. Думаю, что вместо двоичного поиска будет быстрее извлечь куб. корень,
округлить, возвести в куб и сравнить с требуемым.
2. Думаю, достаточно найти только решения, удовлетворяющие неравенствам
0<=a<=b<=c<d<=1000.
3. Думаю, нет смысла искать с такие, что c^3 < d^3/3.
4. Думаю, нет смысла искать b такие, что b^3 < (d^3-c^3)/2.
Т.о. замеить поиск вычислением и отсечь заведомо ненужные варианты.
До свидания, в 22:43 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
