|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 07 Mar 2003 21:29:53
To : Vjacheslav Maslov
Subject : Re: задачка: A^3+B^3+C^3=D^3
--------------------------------------------------------------------------------
Vjacheslav Maslov wrote:
>
> Работает, но медленно где-то 5-7 минут. Один мой знакомый утверждает, что
> придумал алгоритм решения этой задачи, который отрабатывает за 2 сек на машине
> класса P III.
Hу вот ниже решение. Отрабатывает, правда, не ровно за 2 секунды, но
сопоставимо:
real 0m2.402s
user 0m2.190s
sys 0m0.210s
Если раскомментировать вывод - еще секунда добавится...
#include <map>
#include <set>
#include <iostream>
using namespace std;
int calc(int max) {
map< int, set< int > > cd;
int rescount = 0;
for(short d = 2; d <= max; d++)
for(short c = 1; c < d; c++)
cd[d*d*d-c*c*c].insert((c << 16) | d);
for(short a = 1; a <= max; a++)
for(short b = a; b <= max; b++) {
int ab = a*a*a + b*b*b;
if(cd.count(ab)) {
const set< int > &cds = cd[ab];
for(set< int >::const_iterator it(cds.begin());
it != cds.end(); ++it) {
rescount++;
// cout << "Result: " << a << " " << b << " "
// << (*it >> 16) << " = " << ((short)*it) << endl;
}
}
}
return rescount;
}
main() {
int cnt = calc(1000);
cout << "Found results:" << cnt << endl;
}
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
