زمان اجرای فوق العاده زیاد!

[pershianix]

من یک برنامه نوشتم که سری فیبوناچی رو تا جمله ی 80 محاسبه میکنه و بعد از محاسبه و نمایش مجموع سری، مجموع جملات زوج رو نیز محاسبه و چاپ میکنه.
منتها این برنامه یک اشکال خیلی بزرگ داره و اونم اینه که زمان اجرای خیلی خیلی زیادی داره به طوری که تا جمله ی چهلم، تقریبا سریع محاسبه میشه اما مثلا جهت محاسبه ی مجموع جملات تا جمله ی هشتادم، هیچ گاه این اتفاق صورت نمیگریه. حتی بعد از ده دیقه صبر کردن!!

اشکال از کجاست؟ اینم کد:



#include <iostream>

using namespace std;
long fib(long);
int main()
{
long sum=0, num=80;
cout<<fib(num)<<endl;
for (int i=1;i<=num;i++){
if((fib(i)%2)==0)
sum=sum+fib(i);
}
cout<<"result is "<<sum<<endl;
system("pause");
return 0;
}

long fib(long int n)
{
if ((n==0)||(n==1))
return n;
else
return fib(n-1)+fib(n-2);

}




ممنون

[vistacali]

جمله 80 فیبوناچی :متعجب: بابا میدونی چه عدد بزرگی میشه به اینجا (http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.71).aspx)سر بزن مشکل از نوع متغییرها هست فکر کنم

[pershianix]

جمله 80 فیبوناچی :متعجب: بابا میدونی چه عدد بزرگی میشه به اینجا (http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.71).aspx)سر بزن مشکل از نوع متغییرها هست فکر کنم

میدونم. موضوع اینه که یه تمرین دارم که خواسته مجموع جملات زوج سری فیبوناچی رو تا جمله ی 4 میلیون حساب کنم!!! من حتی به خاطر کم کردن فراخوانی تابع، به جای استفاده از تابع بازگشتی، از آرایه ها استفاده کردم تا زمان اجرا بیاد پایین و همین طور هم شد. منتها مثلا تا جمله ی ده هزارم که حساب کردم، خیلی از جملات پایانی، مقدار بی نهایت رو چاپ میکنه که درست هم باید باشه.
جالبه که توی کتاب دیتل، خوندم که اعداد متوالی سری فیبوناچی به طرف مقدار ثابت 1.618000 میل میکنند که به این عدد، نسبت طلایی گفته میشه.

[vistacali]

من الان این رو یک ساعت هست گذاشتم در حال اجرا هست ولی هنوز به جواب نرسیده هنوز داره محاسبه میکنه حتی 37 درصد از cpu رو هم گرفته ببینم چه وقت اخرش جواب جمله 80 رو میده جالب شد:چشمک:

[quiet_programmer]

باسلام.

کد زیر برای محاسبه سری فیبوناچی پیچیدگی زمانی O(N رو داره از لحاظ پیچیدگی حافظه هم حداقل حافظه رو مصرف میکنه.

#include <iostream.h>
void main(void)
{
int F1=1; //fib(0)
int F2=1; //fib(1)
unsigned long int F;
for(int i=2;i<=46;i++)
{
F=F1+F2;
cout<<i<<":"<<F<<endl;
F1=F2;
F2=F;
}
}
*برای داشتن سرعت بالا برای محاسبه جمله فیبوناچی cout داخل حلقه رو خارج از حلقه قرار بده. من فقط برای داشتن تمامی جمله ها چاپ رو داخل حلقه قرار دادم.

از اونجایی که جمله 46سری فیبوناچی 2971215073 میشه و از اونجایی که unsigned long int در صورت 4 بایتی بودن میتونه مقدار 4294967296 رو در خودش جا بده ما مشکل سرریزی حافظه رو نداریم. ولی جمله 47 فیبوناچی 4807526976 میشه. معلومه که این عدد دیگه تو unsigned long int جا نمیشه! پس برای محاسبه این جمله (جمله 47) باید نوع داده ای توسط برنامه نویس شبیه سازی بشه. مثلا استفاده از آرایه که هر اندیس آرایه یک رقم از نتیجه جمله رو در خوش نگهداری میکنه و همچنین اعمال ریاضی که مهمترینش جمع هست برای این مساله توسط خود برنامه نویس شبیه سازی بشه.


مقدار بی نهایت رو چاپ میکنه که درست هم باید باشه.

منظورت از مقدار بینهایت چیه؟

یاحق.
موفق باشید/

[quiet_programmer]

با سلام.


من الان این رو یک ساعت هست گذاشتم در حال اجرا هست ولی هنوز به جواب نرسیده

کاملا طبیعیه!!
چون فراخوانی های بازگشتی نسبت به روش غیر بازگشتی اورهد(Overhead) زیادی دارن. در ضمن احتمال Stack overflow محتمله.

یاحق.
موفق باشید/

[vistacali]

این رو اجرا کنید همین الان پیداش کردم خیلی راحت تا n سری از این جمله را توی سه سوت حساب میکنه



#include <iostream>
using namespace std;

int main (int argc, char* argv[])
{
int fib1 = 0;
int fib2 = 1;
int fib3;
int numbers;
do
{
cout<<"How many numbers would you like to see?";
cin >> numbers;
}while(numbers <= 2);
cout<<fib1<<endl<<fib2<<endl; //keep in mind you want to see the first 2 as well
for(int loop = 2;loop < numbers;loop++)
{
fib3 = fib1 + fib2;
cout << fib3<<"\n";
fib1 = fib2;
fib2 = fib3;
}
system("pause");
return 0;
}

[pershianix]

از همگی ممنون. اشتباه در برداشت من از صورت سوال بود. منظور صورت سوال، محاسبه تا جایی بود که مقدار یکی از جمله ها (و نه خود جمله) کمتر از چهار میلیون باشه که به این ترتیب، من اونو اینطور نوشتم:


#include <iostream>

using namespace std;
long fib(long);
int main()
{
long sum=0, num=40;
//cout<<fib(num)<<endl;
for (int i=1;i<=num;i++){
if(fib(i)>=4000000) break;
if((fib(i)%2)==0)
sum=sum+fib(i);
}
cout<<"sum of the even-valued terms: "<<sum<<endl<<endl;
system("pause");
return 0;
}

long fib(long int n)
{
if ((n==0)||(n==1))
return n;
else
return fib(n-1)+fib(n-2);

}




منظورم هم از چاپ مقدار بی نهایت این بود که موقع اجرا و در محیط command جمله های پایانی با عبارت infinity یا بی نهایت نشون داده میشد.
به هر حال از همگی بابت راهنمایی ممنونم.

[quiet_programmer]

با سلام.


اشتباه در برداشت من از صورت سوال بود. منظور صورت سوال، محاسبه تا جایی بود که مقدار یکی از جمله ها (و نه خود جمله) کمتر از چهار میلیون باشه که به این ترتیب، من اونو اینطور نوشتم:

خسته نباشی!

یاحق.
موفق باشید/