#5 12.05.07 22:28
Re: Интересная задача))
Код: = csharp:
static void Main(string[] args) { Int64 count = 0; int temp; int a,b,c,d; for (d = 3; d < 1001; d++) { for (a = 1; a < d * 1.0 / 1.4 + 1; a++) { temp = (int)Math.Floor(Math.Pow((Math.Pow(d, 3) - Math.Pow(a, 3) * 1.0) / 2, 1d / 3)) + 1; for (b = a; b <= temp; b++) { c = (int)Math.Floor(Math.Pow(Math.Pow(d, 3) - Math.Pow(a, 3) - Math.Pow(b, 3)+1, 1.0 / 3)); if (Math.Pow(d, 3) - Math.Pow(a, 3) - Math.Pow(b, 3) - Math.Pow(c, 3) == 0) { Console.WriteLine(a + "^3+" + b + "^3+" + (c) + "^3=" + d + "^3"); count++; } } } } }
a<=b<=c
1.48 минуты, на моей старенькой машинке.
Исправлено rzk (13.05.07 13:30)
Offline
#8 13.05.07 13:12
Re: Интересная задача))
Мой вариант:
void __fastcall TForm1::FormCreate(TObject *Sender)
{
StringGrid1->Cells[0][0] = "a";
StringGrid1->Cells[1][0] = "b";
StringGrid1->Cells[2][0] = "c";
StringGrid1->Cells[3][0] = "d";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
t = Time();
Thread *SecondProcess = new Thread(true); // create but don’t run
SecondProcess->Priority = tpLower; // set the priority lower than normal
SecondProcess->Resume();
// now start the thread running
myThread *SecondProcess2 = new myThread(true); // create but don’t run
SecondProcess2->Priority = tpLower; // set the priority lower than normal
SecondProcess2->Resume();
TDateTime t1 = Time();
//TimeToStr(t1-t);
Label1->Caption = "Time of work "+TimeToStr(t1-t);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Timer1Timer(TObject *Sender)
{
TDateTime t1 = Time();
//TimeToStr(t1-t);
Label1->Caption = "Time of work "+TimeToStr(t1-t);
}
2й модуль - поток
__fastcall Thread::Thread(bool CreateSuspended)
: TThread(CreateSuspended)
{
}
//---------------------------------------------------------------------------
void __fastcall Thread::Execute()
{ float a,b,c,d;
Form1->StringGrid1->RowCount = 1;
for (a = 1;a < 1000 ;a+=2){
for (b = a;b < 1000 ;b+=1){
for (c = b;c < 1000 ;c+=1){
d = ceil(pow((a*a*a+b*b*b+c*c*c),0.3333));
if ((a*a*a + b*b*b + c*c*c == d*d*d) && (d <= 1000))
{
Form1->StringGrid1->Cells[0][Form1->StringGrid1->RowCount] = FloatToStr(a);
Form1->StringGrid1->Cells[1][Form1->StringGrid1->RowCount] = FloatToStr(b);
Form1->StringGrid1->Cells[2][Form1->StringGrid1->RowCount] = FloatToStr(c);
Form1->StringGrid1->Cells[3][Form1->StringGrid1->RowCount] = FloatToStr(d);
Form1->StringGrid1->RowCount+=1;
} }}
} Form1->Timer1->Enabled = false;
Terminate();//---- Place thread code here ----
}
3й модуль тоже поток
__fastcall myThread::myThread(bool CreateSuspended)
: TThread(CreateSuspended)
{
}
//---------------------------------------------------------------------------
void __fastcall myThread::Execute()
{
float a,b,c,d;
Form1->StringGrid1->RowCount = 2;
for (a = 2;a < 1000 ;a+=2){
for (b = a;b < 1000 ;b+=1){
for (c = b;c < 1000 ;c+=1){
d = ceil(pow((a*a*a+b*b*b+c*c*c),0.3333));
if ((a*a*a + b*b*b + c*c*c == d*d*d)&&(d<= 1000))
{
Form1->StringGrid1->Cells[0][Form1->StringGrid1->RowCount] = FloatToStr(a);
Form1->StringGrid1->Cells[1][Form1->StringGrid1->RowCount] = FloatToStr(b);
Form1->StringGrid1->Cells[2][Form1->StringGrid1->RowCount] = FloatToStr(c);
Form1->StringGrid1->Cells[3][Form1->StringGrid1->RowCount] = FloatToStr(d);
Form1->StringGrid1->RowCount +=1;
} }}
} Form1->Timer1->Enabled = false;
Terminate(); //---- Place thread code here ----
}
организаванно 2 потока один пербирает четные значения другой нечетные
Offline
#9 13.05.07 13:26
Re: Интересная задача))
Andron_ написал(а):
лень в 2 часа ночи что-то писать, но решение придумал... без всяких ужасов типа (int)Math.Floor.
Ахахаха, что пиво с человеком творит. С утра посмотрел - забавно. =))
-12 секунд.
}{B1T написал(а):
for (a = 2;a < 1000 ;a+=2){
for (b = a;b < 1000 ;b+=1){
for (c = b;c < 1000 ;c+=1)
С такими ограничениями, мой старенький амд и за час наверное не справиться. =) a,b,c<d ; c - можно посчитать из a,b,d - если целое, то подходит. А если ещё немного под пивко с неравенствами поиграться, то более строгие ограничения вылезут. =))
Исправлено rzk (13.05.07 14:08)
Offline
#10 13.05.07 13:30
#11 13.05.07 13:59
#12 13.05.07 14:41
#13 13.05.07 14:59
#14 13.05.07 15:09
#15 13.05.07 15:42
#16 13.05.07 16:41
#17 13.05.07 17:17
Re: Интересная задача))
не поленился написал прогу-тестера результатов, без условия a<=b<=c, 1 минута, 17347 результатов, все верные, почти уверен в правильности алгоритма, в прошлом косячёк был..
Код::
#include <math.h>
#include <iostream.h>
#include <math.h>
#include <conio.h>
#include <fstream.h>
int main()
{
int i,j,k,h,r=0,ii,k3,c;
double s;
ofstream f("out.txt");
s=1.0/3.0;
for (i=0;i<=1000; i++)
{
for (j=0;j<=i; j++)
{
ii=i*i*i-j*j*j;
k3=0;
h=ii;
for (k=0;h>=0; k++)
{
h=ii-k*k*k;
c=ceil(pow((double)h,s));
if (h==(c*c*c)){ f<<j<<' '<<k<<' '<<c<<' '<<i<<end; r++;}
}
}
}
cout<<"Count="<<r<<endl;
getch();
return 0;
}Исправлено KyCoK (13.05.07 18:10)
Offline
#18 13.05.07 17:24
Re: Интересная задача))
кстати проверил полученные 17347 результатов на условие
a<=b<=c и среди них оказалось 2391 таких результата
код тестера:
Код::
#include <iostream.h>
#include <math.h>
#include <conio.h>
#include <fstream.h>
int main(){
ifstream f("out.txt");
//if (this!=NULL)
int n=0,a,b,c,d,k=1,j=0;
for(;!(f.eof());n++){
f>>a>>b>>c>>d;
if (a*a*a+b*b*b+c*c*c!=d*d*d){ cout<<a<<" "<<b<<" "<<" "<<c<<" "<<d<<" result failed"<<endl;k=0;}
if ((a<=b)&&(b<=c)) j++;
}
n--;
if (k==1) cout<<"result's OK count="<<n<<" results with a<=b<=c count="<<j<<endl;
getch();
return 0;
}Исправлено KyCoK (13.05.07 17:51)
Offline
#19 13.05.07 17:46
#20 13.05.07 18:19
#21 13.05.07 18:38
#22 13.05.07 18:43
Re: Интересная задача))
Код::
int _tmain(int argc, _TCHAR* argv[])
{
unsigned int Results[1001];
int Counter = 0;
for(int i = 1; i <= 1000; i++)
Results[i] = i*i*i;
int j, k, l, R, F;
int a,b,m;
unsigned int Temp_JK, Temp_JKL;
for(R = 1; R <= 1000; R++)
for(j = 1; j < R; j++)
for(k = j; k < R; k++)
{
Temp_JK = Results[j] + Results[k];
if( Temp_JK > Results[R])
break;
l = (int)pow(Results[R] - Temp_JK, 0.333333332) + 1;
if (Temp_JK + Results[l] == Results[R] && l > k)
{
Counter++;
//printf("%d^3 + %d^3 + %d^3 = %d^3\n", j, k, l, R);
//2391 Solutions
}
}
printf("Well Done! %d Solutions", Counter);
getch();
return 0;
}2391 решение за приблизительно 20сек @2ГГц...
Offline
#23 13.05.07 19:14
#24 13.05.07 19:41
#25 13.05.07 20:27
#26 13.05.07 21:14
#27 13.05.07 21:25
#28 14.05.07 01:04
#29 14.05.07 05:37
#30 14.05.07 10:23
#31 14.05.07 11:20
Re: Интересная задача))
}{B1T написал(а):
Написать программу, которая бы все возможные варианты условия:
a*a*a+b*b*b+c*c*c=d*d*d при условии что a,b,c,d = [1..1000].
Среда разработки любая.
а вы ещё на диану666 ругаетесь, что она с русским языком не дружит
Offline
#32 14.05.07 16:31
#33 14.05.07 20:01
Re: Интересная задача))
Draloskop написал(а):
С++, Visual Studio 2005. Athlon 1500+ (1.33 ГГц).
7.6 секунд, 2391 решение.
Алгоритм - хитросплетение моего изначального и алгоритма rzk на шарпе. Никаких извращений, типа параллельных потоков.
Andron_, твой, для сравнения, у меня ~34 секунды работает.
А показать код можешь?
Offline
#34 14.05.07 22:02
#35 15.05.07 08:00
Re: Интересная задача))
}{B1T написал(а):
2391 решение за приблизительно 20сек @2ГГц...
Ну как зарядка для мозгов?))) У моего преподавателя, который дал это задание прога считает все варианты за 1 секунду, и он не раскрывает каким образом он это сделал)))
1 секунда - это круто... у меня получилось минимум 5.5 секунд (Pentium D820 2.8 ГГц). использовал массив кубов чисел и бинарный поиск по нему....
Код::
procedure TForm1.Button1Click(Sender: TObject);
const UpperLimit = 1000;
var MaxDigit,tmp,tmp1,j,k,l,i,a,b,c,MatchValues: integer;
Time1, Time2: dword;
PowersOf3: array of integer;
LastUsedLeft: integer;
function BinarySearch(left,right: integer; Value: integer): integer;
var CurPtr: integer;
begin
Result := -1;
LastUsedLeft := 0;
while left <= right do
begin
CurPtr := (left + right) div 2;
if PowersOf3[CurPtr] < Value then
left := CurPtr + 1
else
if PowersOf3[CurPtr] > Value then
right := CurPtr - 1
else
begin
Result := CurPtr;
LastUsedLeft := CurPtr;
Break;
end;
end;
LastUsedLeft := left;
end;
begin
memo1.Lines.Clear;
Time1 := GetTickCount;
SetLength(PowersOf3, UpperLimit);
for i := 1 to UpperLimit do
begin
PowersOf3[i - 1] := i * i * i;
end;
MaxDigit := UpperLimit * UpperLimit * UpperLimit;
MatchValues := 0;
for i := 1 to UpperLimit do
begin
tmp := PowersOf3[i-1];
for j := i to UpperLimit do
begin
tmp1 := tmp + PowersOf3[j-1];
LastUsedLeft := 0;
for k := j to UpperLimit do
begin
l := tmp1 + PowersOf3[k-1];
if l > MaxDigit then break;
a := k - 1;
b := UpperLimit - 1;
if LastUsedLeft > a then a := LastUsedLeft;
c := BinarySearch(a, b, l);
if c <> -1 then
begin
Inc(MatchValues);
//memo1.Lines.Add(IntToStr(i) + '^3 + ' + IntToStr(j) + '^3 + ' + IntToStr(k)+ '^3 = ' + IntToStr(c+1) + '^3');
end;
end;
end;
end;
Time2 := GetTickCount;
ShowMessage('Решений: ' + IntToStr(MatchValues) + ' Время: ' + FloatToStr((Time2 - Time1)/1000));
end;Offline
#36 15.05.07 21:21
#37 15.05.07 21:24
#38 15.05.07 22:16
#39 15.05.07 22:53
#40 16.05.07 18:17
#41 18.05.07 19:29
#42 18.05.07 20:01
#43 18.05.07 20:18
Re: Интересная задача))
Ну вот код. Примечание: компилить в релиз-сборке, чтоб осуществлялась inline подстановка, иначе результат далек от ожидаемого.
Код: C++:
#include <stdio.h> #include <time.h> #include <algorithm> const int num = 1001; const int msize = 499500; struct Item { unsigned val; unsigned first; unsigned second; } plus[msize], minus[msize]; inline bool operator < (Item it1, Item it2) { return it1.val < it2.val; } void main() { int count = 0; unsigned res[num]; int a, d; int psize = 0; int k = 0, l = 0; clock_t beg, end; beg = clock(); for (d = 1; d < num; ++d) res[d] = d * d * d; for (d = 1; d < num; ++d) for (a = 1; a < d; ++a) { minus[count].first = d; minus[count].second = a; minus[count].val = res[d] - res[a]; ++count; } count = 0; for (d = 1; d < num; ++d) for (a = 1; a < d; ++a) { if (res[d] + res[a] > res[1000]) break; plus[psize].first = d; plus[psize].second = a; plus[psize].val = res[d] + res[a]; ++psize; } std::sort(minus, minus + msize); std::sort(plus, plus + psize); count = 0; while ((k < msize) && (l < psize)) { if (minus[k].val < plus[l].val) { ++k; } else { if (minus[k].val > plus[l].val) { ++l; } else { if ((k + 1 < msize) && (l + 1 < psize)) { if ((minus[k + 1].val - minus[k].val == 0) && (plus[l + 1].val - plus[l].val == 0)) { int ktemp = k; int ltemp = l; while (minus[ktemp].val - minus[k].val == 0) { ltemp = l; while (plus[ltemp].val - plus[l].val == 0) { if ((plus[ltemp].first > plus[ltemp].second) && (plus[ltemp].second > minus[ktemp].second)) { ++count; } ++ltemp; } ++ktemp; } k = ktemp + 1; l = ltemp + 1; } else { if ((plus[l].first > plus[l].second) && (plus[l].second > minus[k].second)) { ++count; } if (minus[k + 1].val - minus[k].val < plus[l + 1].val - plus[l].val) { ++k; } else { ++l; } } } else { if ((plus[l].first > plus[l].second) && (plus[l].second > minus[k].second)) { ++count; } if (k == msize - 1) { ++l; } else { ++k; } } } } } end = clock(); printf("%d\n%d\n", end - beg, count); getchar(); }
Исправлено Draloskop (18.05.07 20:43)
Offline

