پایین اوردن زمان اجرای کد

[sa1378]

با سلام
سوال اینجوریه که 5^10 کارت داریم که به ترتیب شماره گذاری شدن
روی کارت i ام مقدار ( f( i نوشته شده
از کارت 1 شروع میکنیم و در هر مرحله کارتی که داریم رو پاره میکنیم و کارت ( f( i رو برمیداریم
چند مرحله طول میشه که دیگه نتونیم کارتی برداریم؟
این کد منه:
#include <iostream>


using namespace std;
#define N (1000*100)
inline int f(int i)
{
if(i==1)
return 5;

int v=((f(i/2)+f(i-1)+2)%N)+1;
return v;
}

int main(){
int i=1;
bool a[N]={0};

while(a[i]==0)
{
cout<<i<<" ";
a[i]=1;
i=f(i);
}
cout<<endl;
cout<<"FINISH!!!"<<"LAST CARD : "<<i<<endl;


return 0;
}
ولی زمان اجراش زیاده
توی خروجی هم فقط 4 تا عدد چاپ میکنه و بعد جلو نمیره
احتمالا بخاطر اینه که بازگشتی هست
چجوری کمش کنم؟

[a.r.khoshghalb]

اولا که کد شما داره میگه آخرین کارت چیه! که لزوما آخرین کارت یدونه نیست و صورت سوال هم گفته چند مرحله طول میکشه!، مثلا از این 5^10 کارت شاید (f(1 برابر با 2 بود و (f(2 برابر با 1 بود، اینطوری فقط یک مرحله طول می کشه بعدش 2 - 5^10 کارت داریم!
صورت سوال هیچ شرطی برای (f(i ها نذاشته؟؟؟ ما چی می دونیم راجع به (f(i ها؟

[sa1378]

اولا که کد شما داره میگه آخرین کارت چیه! که لزوما آخرین کارت یدونه نیست و صورت سوال هم گفته چند مرحله طول میکشه!، مثلا از این 5^10 کارت شاید (f(1 برابر با 2 بود و (f(2 برابر با 1 بود، اینطوری فقط یک مرحله طول می کشه بعدش 2 - 5^10 کارت داریم!
صورت سوال هیچ شرطی برای (f(i ها نذاشته؟؟؟ ما چی می دونیم راجع به (f(i ها؟
درست میگید باید یه شمارنده میذاشتم برای تعداد مرحله(البته اون که روی زمان مشکلی ایجاد نمیکنه)
توی کد f(i) رو نوشتم فکر کردم خودتون میبینید
f(i)=((f(i/2)+f(i-1)+2)%N)+1;
که N همون 5^10 هست

[sa1378]

در حالی که دارین به بالایی فکر میکنین یه فکری هم به حال این کنین:
اوردش 2^n هست که میشه 1 میلیون دستور
باید اجرا بشه ولی هنگ میکنه
#include <iostream>


using namespace std;
int main() {
long long int a[1000][1000];

for(int i1=0;i1<=999;i1++)
{
a[0][i1]=a[i1][0]=1;
}
for(int i=1;i<=999;i++)
{
for(int j=1;j<=999;j++)
{
a[i][j]=a[i-1][j]+a[i][i-1];
cout<<"a["<<i<<"]["<<j<<"] = "<<a[i][j]<<endl;
}
}
cout<<a[999][999];
return 0;
}

[a.r.khoshghalb]

دلیل هنگ کردن کد پایین اوردر نیست، آرایه a شما به این صورت است:
long long int a[1000][1000];
این خیلی حافضه زیادیه و یک تابع نمی تونه همچین حافظه ای بگیره، باید گلوبال تعریفش کنید.

[a.r.khoshghalb]

برای کد اولت نمیدونم می خوای زمان اجراش چه قدر بشه، صرفا گفتی کم تر بشه!
یه راه خوب کمتر شدنش اینه که به جای اینکه هر دفعه بری (F(i رو حساب کنی، یک بار برای همیشه f همه i ها رو حساب کنی. و از اونجایی که تعریف (f(i بازگشتی هست ولی فقط به f های کمتر از i نیاز داره، دیگه بازگشتی حساب نمی کنیمش.
کد:

#include <iostream>

using namespace std;
//#define N (1000*100) Be in soorat define kardan kheili eshtebahe!
//Chon ke shayad ye jaii to codet havaset nabud masalan ye araye END tarif kardi! Ya...
//Raveshe sahihesh ine :
const int N = (1000*100);

inline int f(int i)
{
if(i==1)
return 5;

int v=((f(i/2)+f(i-1)+2)%N)+1;
return v;
}

int F[N]; // F haye hesab shode ro into mirizim.


int main()
{

//CODE HAII KE MAN EZAFE KARDAM :
F[1] = 5;
for (int I = 2; I <= N; I++)
F[I] = ((F[I/2] + F[I-1] + 2) % N) + 1;


int i=1;
bool a[N]={0};
while(a[i]==0)
{
cout<<i<<" ";
a[i]=1;
//i=f(i);
i = F[i];
}
cout<<endl;
cout<<"FINISH!!!"<<"LAST CARD : "<<i<<endl;


return 0;
}

[sa1378]

کد جدید:
#include <iostream>


using namespace std;
const int N =(1000*100);
int F[N+1];

int main(){
F[1]=5;
for(int I=2;I<=N;I++)
{
F[I]=((F[I/2]+F[I-1]+2)%N)+1;
}

bool a[N+1]={0};
int p=0;
int i=1;
while(a[i]!=1)
{
cout<<i<<" "<<F[i]<<endl;
a[i]==1;
p++;
i=F[i];
}

cout<<"FINISH!!!"<<"NUMBER OF MISSIONS : "<<p<<endl;


return 0;
}
با سرعت نور داره عدد مینویسه ولی تموم نمیشه
یا تعداد مراحل خیلی زیاده
یا کد رو اشتباه نوشتیم و ران تایمتش بی نهایته

الان یه چیزی فهمیدم
اینکه این کلا شماره 5و6 تا کارت رو داره هی چاپ میکنه و اعدادش تکراری هستن
N رو به 10 تغییر دادم و مینویسه:

5 1
3 5
1 3
5 1
3 5
1 3
5 1
3 5
1 3
و...
سوال اینه که چرا از حلقه بیرون نمیاد؟

[مسعود اقدسی فام]

کد جدید:
#include <iostream>


using namespace std;
const int N =(1000*100);
int F[N+1];

int main(){
F[1]=5;
for(int I=2;I<=N;I++)
{
F[I]=((F[I/2]+F[I-1]+2)%N)+1;
}

bool a[N+1]={0};
int p=0;
int i=1;
while(a[i]!=1)
{
cout<<i<<" "<<F[i]<<endl;
a[i]==1;
p++;
i=F[i];
}

cout<<"FINISH!!!"<<"NUMBER OF MISSIONS : "<<p<<endl;


return 0;
}
با سرعت نور داره عدد مینویسه ولی تموم نمیشه
یا تعداد مراحل خیلی زیاده
یا کد رو اشتباه نوشتیم و ران تایمتش بی نهایته

الان یه چیزی فهمیدم
اینکه این کلا شماره 5و6 تا کارت رو داره هی چاپ میکنه و اعدادش تکراری هستن
N رو به 10 تغییر دادم و مینویسه:

5 1
3 5
1 3
5 1
3 5
1 3
5 1
3 5
1 3
و...
سوال اینه که چرا از حلقه بیرون نمیاد؟

خط 21 یه = اضافی داره.