سلام
ببخشید
می شه در شمارش تعداد گامهای این دستورات در برنامه C++ کمکم کنید؟
float rsum(float list[],int n)
{
if (n!=0)
return rsum(list,n-1)+list[n-1];
else
return list[0];
}
سلام
ببخشید
می شه در شمارش تعداد گامهای این دستورات در برنامه C++ کمکم کنید؟
float rsum(float list[],int n)
{
if (n!=0)
return rsum(list,n-1)+list[n-1];
else
return list[0];
}
فکر کنم آخرش جواب بشه:
return list[0]+list[n-1];
همون n که برای اولین بار به تابع ارسال شده
اولین بار n مخالف صفر هست.
rsum(list,n-1)این دستور اجرا میشه و تابع دوباره فراخوانی میشه. همینطوری ادامه پیدا میکنه تا اینکه n=0 بشه. مساوی صفر که شد list[0] برگردونده میشه و در نهایت با list[n-1] جمع میشه. n هم مقدارش همون مقداریه که اولین بار به تابع ارسال شده.
سلام
از اینکه به سؤال من جواب دادی متشکرم
شما گفته بودید که تعداد گامهای این شرط n است .شما فقط تعداد گامهای داخل شرط را حساب کرده بودید آیا خود شرط هم جزو تعداد گام حساب نمی شود؟
اگه خود شرط را هم حساب کنیم می شه n+1 که با n قبلی می شه 2n+1 بار.
یه سؤال دیگه:آیا این عبارت 2 بار اجرا می شه یا یک بار(تعداد گام)؟
return fact(n-1)*n;
fact؟ انگار اصلا شما درمورد سوال اولتون صحبت نمیکنید؟!!!
خب این کد چرا باید دوبار اجرا بشه؟! اگر تابع بازگشتی هست کاملشو قرار بدید.
سلام dousti_design جان
منو ببخش من خیلی عصبانی بودم
من نباید اون حرفها را می زدم
راستی
سال نو مبارک
اگه بخشیدی جواب منو بده
آخرین ویرایش به وسیله kamran_14 : شنبه 22 اسفند 1388 در 18:53 عصر
اینجا هیچ کس وظیفه ای در قبال پاسخ به سوالات دیگران ندارد؛شخصی که جواب می دهد یا سعی در کمک کردن دارد به نوعی لطف می کند. پس سعی کنید از لحن مناسب تری برای برخورد با دیگران استفاده کنید.
در هر تایپیک فقط می توانید یک سوال مطرح کنید.(قوانین را مطالعه کنید)بعد یه سؤال دیگه اضافه کردم
گام اونقدر مفهوم مهمی نیست، بلکه اونچه که مهمه order زمان اجرا هست که در اینجا (O(n هست. در واقع اگه بخوام دقیقتر توضیح بدم این دستور زبان C ممکنه به شکلهای مختلفی به زبان ماشین ترجمه بشه و اصلآ اینطور نیست که مثلا یک خط دستور، در یک سیکل ماشین اجرا بشه. بنابر این صحبت از تعداد دقیق گامها (اینکه n تاست یا 2*n تا) کاملآ بی مورد هست (فکر میکنم تنها جایی که ممکنه به در بخوره سر جلسه امتحانه)
برای شمارش تعداد خطوط اجرایی برنامه یا همون تعداد گام های اجرایی برنامه باید به این نکته توجه کرد که یه کار سخت و پیچیده و طاقت فرسا هست مخصوصا برای کدهای پیچیده و همچنین توابع بازگشتی و....بنابراین به جای اینکه تعداد خطوط یک برنامه رو بشمارن میان اون تکه کد رو با کدهای مشابه و معروف که قبلا به صورت دقیق بررسی شده قیاس میکنن و رده بندی هایپیچیدگی زمانی رو براش بحث میکنن!!!!
اما برای این تابعه ای که اینجا نوشتین فارغ از اینکه چه کاری رو داره انجام میده از خط اول :
0 ..... چون تعریف هست و توسط cpu اجرا نمیشه
0
n+1 .....برای دستور if و دستور تحت خودش(n بار اجرا میشه و یک بار آخر هم شرط چک میشه که غلط هست و قسمت else اجرا میشه)
1 ........برای دستور else و return تحت خودش
0
مجموع n+2
که از order====> O(n) هست!
در مورد این کد هم بگم که این کد یه تکه کد از تابع بازگشتی معروف فاکتوریل هست!
پس n! بار اجرا میشه!!! و از رده ی O(n!) هست.که پیچیدگی بالایی هم داره!
اما اگر همین تابع بازگشتی رو به صورت غیر بازگشتی و با دستور حلقه بنویسید به پیچیدگی کمتر و یا به عبارتی سرعت خیلی بهتر نسبت به فاکتوریل ; یعنی به سرعت تابع خطی O(n) میرسیم که این مثال نشون میده که توابع بازگشتی درسته که گاهی اوقات ساده میشه نوشت و یا درکش ساده تر هست اما همیشه سرعت اجرایی خوبی ندارن!!!!