Re: задачка: A^3+B^3+C^3=D^3

From

Soldatenkov Mitea (2:5015/126.41)

To

Vjacheslav Maslov ()

Date

2003-03-07T02:08:44Z

Area

RU.ALGORITHMS

Привет, Vjacheslav Maslov!
Ты вроде писал(а) в эху RU.ALGORITHMS следуюшее:
N это максимальное значение числа? Тогда:
 VM> 2. Затем тройной цикл:     for a:=1 to N do         
Неа, for a=1 to f1(n*n*n/3)do
Где f1 будет определять корень 3ей степени из своего параметра, с отсечением
дробной части. С этой функцией imho, проблем быть недолжно.
Так-как A, B и C будут упорядоченны по возрастанию, то B и C заведомо
несмогут быть меньше A. Следовательно, минимальное значение функции
A^3+B^3+C^3=3*A^3. Так-как так-же известно что все это <= N^3,
то как следствие, A как минимум <=((N^3)/3)^(1/3).
 VM> for b:=1 to N do
Опять-же неа, for b:=a to f1((n*n*n-cubes[a])/2) do.
Думаю, понятно из преведущей объяснялки:).
 VM> for c:=1 to N do
Опять-же, for c=b to f1(n*n*n-cubes[a]-cubes[b]) do.
Примерно в 6 раз, если не ошибаюсь ускоришь поиск, потому-что a, b и c будут
сразу упорядочены по возрастанию что избавит тебя от 6ти разового
перебора одной и той-же комбинации. Потом, если тебе нужны все сочетания,
проставь не 1, а 6 writeln примерно таким образом:
writeln'a:=',a,' b:=',b,' c:=',c,' d:=',d);
writeln'a:=',a,' b:=',c,' c:=',' d:=',d);
writeln'a:=',b,' b:=',a,' c:=',c,' d:=',d);
...
вобщем, думаю понятно о чем я.
 VM> begin                 if
 VM> Search(Cubes[a]+Cubes[b]+Cubes[c]) then //найдено решение
 VM> writeln(...)             end; Где Search(x) - бинарный поиск числа x в
 VM> массиве Cubes.


 VM> Работает, но медленно где-то 5-7 минут. Один мой знакомый утверждает, что
 VM> придумал алгоритм решения этой задачи, который отрабатывает за 2 сек на
 VM> машине класса P III.

 VM> Возможно ли?
Да запросто. Надо просто осмотрется вокруг. Вот например, какой-нить студент
нечего незнает, а правильно отвечает. Спрашивается: как? А он в шпаргалку скорее
всего глядит. Вот и создай для проги шпору. Чтоб в ней были указанны все A, B, C и D
удалитворяющее условию задачи. А дальше, шпору выдавай на печать. Это imho,
вообще в виде bat файла оформить можно.

--- 
 * Origin: Введи четыре кубика и ты турист..  (2:5015/126.41)