|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Soldatenkov Mitea 2:5015/126.41 07 Mar 2003 03:08:44
To : Vjacheslav Maslov
Subject : Re: задачка: A^3+B^3+C^3=D^3
--------------------------------------------------------------------------------
Ты вроде писал(а) в эху RU.ALGORITHMS следуюшее:
N это максимальное значение числа? Тогда:
VM> 2. Затем тройной цикл: for a:=1 to N do
Hеа, 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> Возможно ли?
Да запросто. Hадо просто осмотрется вокруг. Вот например, какой-нить студент
нечего незнает, а правильно отвечает. Спрашивается: как? А он в шпаргалку скорее
всего глядит. Вот и создай для проги шпору. Чтоб в ней были указанны все A, B, C
и D
удалитворяющее условию задачи. А дальше, шпору выдавай на печать. Это imho,
вообще в виде bat файла оформить можно.
---
* Origin: Введи четыре кубика и ты турист.. (2:5015/126.41)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
