Официальный сайт студ.городка НГТУ
Программирование и БД » Интересная задача)) 

#1  12.05.07 19:46

Интересная задача))

Написать программу, которая бы все возможные варианты условия:
a*a*a+b*b*b+c*c*c=d*d*d при условии что a,b,c,d = [1..1000].
Среда разработки любая.
Я писал в Билдере С++ и моя программа считает за 2 минуты 21 секунду.
Поделитесь своими идеями)))

Offline

#2  12.05.07 19:54

Re: Интересная задача))

a,b,c,d числа целые чтоли?

Offline

#3  12.05.07 20:26

Re: Интересная задача))

Andron_ написал(а):

a,b,c,d числа целые чтоли?

да перебор целых значений.

Offline

#4  12.05.07 20:57

Re: Интересная задача))

}{B1T написал(а):

Поделитесь своими идеями)))

Сначала ты поделись. Имеет ли смысл выкладывать свои, если ты решил более эффективно или так же?

Offline

#5  12.05.07 22:28

rzk
Профиль

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

#6  13.05.07 01:58

Re: Интересная задача))

лень в 2 часа ночи что-то писать, но решение придумал... без всяких ужасов типа (int)Math.Floor.

Offline

#7  13.05.07 08:21

Maq
Профиль

Re: Интересная задача))

}{B1T написал(а):

которая бы все возможные варианты условия:

которая что бы делала?)))

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

rzk
Профиль

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

Re: Интересная задача))

c - можно посчитать из a,b,d - если целое, то подходит

Я d  считаю из a,b,c.

d = ceil(pow((a*a*a+b*b*b+c*c*c),0.3333));

Offline

#11  13.05.07 13:59

Re: Интересная задача))

}{B1T написал(а):

организаванно 2 потока

Бгого. У меня и без всяких параллельных потоков на С++ древний атлончик за ~22-23 секунды посчитал.

Offline

#12  13.05.07 14:41

Re: Интересная задача))

так... стоп... условие невнимательно прочитал...

Исправлено Andron_ (13.05.07 14:44)

Offline

#13  13.05.07 14:59

Re: Интересная задача))

народ давайте хоть как-то ориентироваться в правильности наших алгоритмов- например подсчитывать хотябы количество ответов, у меня 16348 :) не уверен в правильности)

Offline

#14  13.05.07 15:09

Re: Интересная задача))

хах результат одного и тогоже кода на buildere-16348/2:07 MS Visual c++ -16351/1:01
мля ща ещё на чемнибудь скомпилю)))

Исправлено KyCoK (13.05.07 15:10)

Offline

#15  13.05.07 15:42

rzk
Профиль

Re: Интересная задача))

2391 строка при выполнении неравенств a<=b<=c, соответственно при перестановке слагаемых, строк в 6 раз больше. Фигасе у вас компьютеры если без ограничений, за 20 секунд выполняется. Полюбому мне нужен апгрейд.

Исправлено rzk (13.05.07 15:45)

Offline

#16  13.05.07 16:41

Re: Интересная задача))

тэкс.... для контроля результатов...
при условии a<=b<=c должно выводиться 2391 решение.

на данный момент у мя 20 сек. результат.

Offline

#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

Re: Интересная задача))

Мдя... вы бы ещё под MMX это дело написали :) Кстати, ради интереса врубите в опциях компилятора (те, кто под MSVS пишут) поддержку оптимизирующего компилятора, MMX, SSE I-III, 3dnow! - думаю, время уменьшиться раза в 4

Offline

#20  13.05.07 18:19

Re: Интересная задача))

условие понял не так, бред удален. :)

Исправлено srf2000 (13.05.07 18:54)

Offline

#21  13.05.07 18:38

rzk
Профиль

Re: Интересная задача))

как из условия

}{B1T написал(а):

a*a*a+b*b*b+c*c*c=d*d*d

появляется

srf2000 написал(а):

a * b * c = d * d * d

??? И что-то ответов многовато. при условии a <= b <= c.


KyCoK написал(а):

for (i=0;i<=1000; i++)

a,b,c,d>=1;

Исправлено rzk (13.05.07 18:42)

Offline

#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

rzk
Профиль

Re: Интересная задача))

Andron_ написал(а):

for(int i = 1; i <= 1000; i++) Results[i] = i*i*i;

Апгрейд компьютера откладывается. На очереди апгрейд мозгов. =))
18 секунд.

Исправлено rzk (13.05.07 19:14)

Offline

#24  13.05.07 19:41

Re: Интересная задача))

Andron_,
+1

Offline

#25  13.05.07 20:27

Re: Интересная задача))

хотя, с условием a<=b<=с моя прога даёт решений-2391,30 сек(кстати простое домножение на 6 не даёт полного количества решений) , а с массивом кубов 24 сек, думал прирост будет больше..

Offline

#26  13.05.07 21:14

Re: Интересная задача))

2391 решение за приблизительно 20сек @2ГГц...

Ну как зарядка для мозгов?))) У моего преподавателя, который дал это задание прога считает все варианты за 1 секунду, и он не раскрывает каким образом он это сделал)))

Offline

#27  13.05.07 21:25

Re: Интересная задача))

}{B1T написал(а):

прога считает все варианты за 1 секунду, и он не раскрывает каким образом он это сделал)))

надо курить свойства уравнения... скорее всего есть какое-то аналитическое решение.

Offline

#28  14.05.07 01:04

rzk
Профиль

Re: Интересная задача))

}{B1T написал(а):

У моего преподавателя, который дал это задание прога считает все варианты за 1 секунду

Штоб ему пусто было этому преподавателю, третий час не могу ничего путного придумать, чтобы за 1 секунду считалось.

Offline

#29  14.05.07 05:37

Maq
Профиль

Re: Интересная задача))

решить уравнение сначало надо попробовать))

Offline

#30  14.05.07 10:23

Re: Интересная задача))

Maq написал(а):

решить уравнение сначало надо попробовать))

Скажем, проанализировать.

Offline

#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

Re: Интересная задача))

С++, Visual Studio 2005. Athlon 1500+ (1.33 ГГц).
7.6 секунд, 2391 решение.
Алгоритм - хитросплетение моего изначального и алгоритма rzk на шарпе. Никаких извращений, типа параллельных потоков.
Andron_, твой, для сравнения, у меня ~34 секунды работает.

Offline

#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

Re: Интересная задача))

А у меня быстрее, чем за 40 сек нифига не получается сделать =((

Offline

#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

Re: Интересная задача))

подкинул задачку одному старому маньяку :)

на данный момент рекорд 0.5 секунды (обычный комп)
есть мнение, что можно сделать в 2-3 раза быстрее

Offline

#37  15.05.07 21:24

Re: Интересная задача))

Matrim написал(а):

подкинул задачку одному старому маньяку :)

на данный момент рекорд 0.5 секунды (обычный комп)
есть мнение, что можно сделать в 2-3 раза быстрее

маньяк приведет код на 0.5 секунды? :)

Offline

#38  15.05.07 22:16

Re: Интересная задача))

не спрашивал
может и приведет, когда наиграется

Offline

#39  15.05.07 22:53

Re: Интересная задача))

Matrim написал(а):

не спрашивал
может и приведет, когда наиграется

Очень хотелось бы посмортерь)))

Offline

#40  16.05.07 18:17

rzk
Профиль

Re: Интересная задача))

Довёл до 5.3 секунды(C#. athlon 2500 xp 1.8Ггц), жажду увидеть решение за 0.5 секунды.

Исправлено rzk (16.05.07 18:18)

Offline

#41  18.05.07 19:29

Re: Интересная задача))

Алгоритм rzk из предыдущего поста был переведен на рельсы С++ и слегка мною выпотрошен. И вуаля - 0.36 секунды на Athlon 1500+.
Все регарды - к нему :)

Offline

#42  18.05.07 20:01

Re: Интересная задача))

Draloskop написал(а):

Алгоритм rzk из предыдущего поста был переведен на рельсы С++ и слегка мною выпотрошен. И вуаля - 0.36 секунды на Athlon 1500+.
Все регарды - к нему :)

ну и где код?

Offline

#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

#44  18.05.07 22:58

Re: Интересная задача))

зачотный алгоритм!
снимаю шляпу :)

Offline

#45  18.05.07 23:23

Re: Интересная задача))

Ага, и я снимаю.
}{B1T, шагай, преподу своему покажи.

Offline

Программирование и БД » Интересная задача)) 

ФутЕр:)

© Hostel Web Group, 2002-2025.   Сообщить об ошибке

Сгенерировано за 0.142 сек.
Выполнено 11 запросов.