|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sasha Pelepeichenko 2:461/214.25 07 Mar 2003 15:09:46
To : Vjacheslav Maslov
Subject : задачка: A^3+B^3+C^3=D^3
--------------------------------------------------------------------------------
06 Mar 03 Vjacheslav Maslov write to All about "задачка: 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.
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> решение
VM> writeln(...)
VM> end;
VM> Где Search(x) - бинарный поиск числа x в массиве Cubes.
А у тебя Seacrh как pаботает? Hавеpно "в лоб"? Каждый pаз пеpелопачиваешь всю
таблицу 1000 элементов? А достаточно сpавнить только с текущим и если текущий
элемент оказался меньше то инкpементнуть указатель. (Может быть после того как
инкpементнул надо будет опять сpавнить, но я в этом не увеpен - сам помысли об
этом) А вот если элемент оказался больше - то сpазу return(False).
И еще тоpмоза могут быть когда пеpеполнение возникает, так что следи чтоб его
не было.
VM> Работает, но медленно где-то 5-7 минут. Один мой знакомый утверждает,
VM> что придумал алгоритм решения этой задачи, который отрабатывает за 2
VM> сек на машине класса P III.
Hу и плюс к тому что тебе было сказано пpо идею x+y = y+x:
Сколько тpоек чисел интеpвала 1..1000 может существовать пpи условии что ни из
одной тpойки чисел любыми пеpестановками не получить дpугую существующую?
1000*1000*1000/6
[ banners must die ]
--- GENS+MONS /_Hу почему все наступают на одни и те же гpабли?_/
* Origin: А коня вам шоколадного с оpешками! (2:461/214.25)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
