زمان کنونی: ۰۲ مهر ۱۳۹۹, ۰۵:۴۸ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مرتبه اجرایی تابع بازگشتی

ارسال:
  

khavar_1365 پرسیده:

مرتبه اجرایی تابع بازگشتی

سلام دوستان:میخواستم بدونم مرتبه اجرایی این تابع چی میشه؟!من خودم فکر میکنم
از مرتبه nمیشه اما داخل کتاب آقای مقسمی اونو۲به توانnبدست آوورده!!!!!اگر جواب درست اینه.لطف کنید نکته‌ها وراه حل اونهم بفرمایید.
باتشکر از همه شما
[[tex]t(n)=t(n-1)*t(n-1)[/tex]

۰
ارسال:
  

summer_66 پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

(۱۴ مهر ۱۳۹۰ ۱۰:۴۷ ق.ظ)khavar_1365 نوشته شده توسط:  سلام دوستان:میخواستم بدونم مرتبه اجرایی این تابع چی میشه؟!من خودم فکر میکنم
از مرتبه nمیشه اما داخل کتاب آقای مقسمی اونو۲به توانnبدست آوورده!!!!!اگر جواب درست اینه.لطف کنید نکته‌ها وراه حل اونهم بفرمایید.
باتشکر از همه شما
[[tex]t(n)=t(n-1)*t(n-1)[/tex]
ببینید شما یه درخت به ارتفاع n خواهید داشت که هر کدام از نود های اون یک مرحله اجرای تابع هست که باید در محاسبه مرتبه اجرایی به حساب بیاد پس باید تعداد کل نود های این درخت به ارتفاع n رو بدست بیارید که میشه [tex]2^{n} -1[/tex] پس مرتبه اجرایی همون [tex]2^{n}[/tex] هست .شکلش رو بکشید تا متوجه بشید اگه موضوع براتون روشن نشد بگید تا شکلش رو بکشم.

۰
ارسال:
  

mfXpert پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

اگر تابع [tex]t(n)=t(n-1)*t(n-1)[/tex] تو گسسته مطرح میشد و از شما خواسته میشد که جواب غیر بازگشتی تابع رو به دست بیارید اونوقت باید از روش های معمول حل روابط بازگشتی استفاده می کردید و جواب رو به دست می آوردید.اما چون تو بحث ساختمان و مرتبه اجرایی به دنبال تعداد کل فراخوانی های تابع t هستیم پس می تونیم علامت ضرب موجود در صورت سوال رو به جمع تبدیل کنیم.یعنی تابع [tex]t(n)=t(n-1)*t(n-1)[/tex] رو به صورت [tex]t(n)=t(n-1) t(n-1)=2t(n-1)[/tex] در نظر بگیریم .حالا میتونیم با روش جایگذاری‌، تعداد فراخوانی های t رو به دست بیاریم:
[tex]t(n)=2t(n-1)[/tex]
[tex]t(n)=2(2t(n-2))[/tex]
.
.
.
[tex]t(n)=2^{n-1}(t(1))[/tex]

همونطور که مشخصه تابع بازگشتی از مرتبه دو به توان n هستش

ارسال:
  

khavar_1365 پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

(۱۴ مهر ۱۳۹۰ ۰۲:۱۴ ب.ظ)mfXpert نوشته شده توسط:  اگر تابع [tex]t(n)=t(n-1)*t(n-1)[/tex] تو گسسته مطرح میشد و از شما خواسته میشد که جواب غیر بازگشتی تابع رو به دست بیارید اونوقت باید از روش های معمول حل روابط بازگشتی استفاده می کردید و جواب رو به دست می آوردید.اما چون تو بحث ساختمان و مرتبه اجرایی به دنبال تعداد کل فراخوانی های تابع t هستیم پس می تونیم علامت ضرب موجود در صورت سوال رو به جمع تبدیل کنیم.یعنی تابع [tex]t(n)=t(n-1)*t(n-1)[/tex] رو به صورت [tex]t(n)=t(n-1) t(n-1)=2t(n-1)[/tex] در نظر بگیریم .حالا میتونیم با روش جایگذاری‌، تعداد فراخوانی های t رو به دست بیاریم:
[tex]t(n)=2t(n-1)[/tex]
[tex]t(n)=2(2t(n-2))[/tex]
.
.
.
[tex]t(n)=2^{n-1}(t(1))[/tex]

همونطور که مشخصه تابع بازگشتی از مرتبه دو به توان n هستش
سلام دوست عزیز
نکته بسیارخوب و مفیدی برای حل تستی اینگونه روابط بیان کردی بسیارمتشکرم.


(۱۴ مهر ۱۳۹۰ ۰۱:۳۰ ب.ظ)summer_66 نوشته شده توسط:  
(14 مهر ۱۳۹۰ ۱۰:۴۷ ق.ظ)khavar_1365 نوشته شده توسط:  سلام دوستان:میخواستم بدونم مرتبه اجرایی این تابع چی میشه؟!من خودم فکر میکنم
از مرتبه nمیشه اما داخل کتاب آقای مقسمی اونو۲به توانnبدست آوورده!!!!!اگر جواب درست اینه.لطف کنید نکته‌ها وراه حل اونهم بفرمایید.
باتشکر از همه شما
[[tex]t(n)=t(n-1)*t(n-1)[/tex]
ببینید شما یه درخت به ارتفاع n خواهید داشت که هر کدام از نود های اون یک مرحله اجرای تابع هست که باید در محاسبه مرتبه اجرایی به حساب بیاد پس باید تعداد کل نود های این درخت به ارتفاع n رو بدست بیارید که میشه [tex]2^{n} -1[/tex] پس مرتبه اجرایی همون [tex]2^{n}[/tex] هست .شکلش رو بکشید تا متوجه بشید اگه موضوع براتون روشن نشد بگید تا شکلش رو بکشم.

سلام واقعا از جوابتون ممنون.اگه لطف کنید و شکلش رو هم بکشید بسیار ممنون میشم جون برای رسم و حل روابط بازگشتی بادرخت هنوز مشکل دارم اگرنکته مفیدوکلی هست برای رسم با درخت بازگشتی حتما بیان کنید..ممنون
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

khavar_1365 پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

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

ارسال:
  

summer_66 پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

(۱۴ مهر ۱۳۹۰ ۱۰:۵۲ ب.ظ)khavar_1365 نوشته شده توسط:  سلام دوست عزیز.
بسیار سپاسگزارم از لطف و راهنماییتون.ممنون میشم اگه بیشتر از این بتونید تو حل اینجور مسایلی کمکم کنید بخصوص درخت بارگشتی.
با تشکر
اگه کمکی از دستم بربیاد در خدمت هستم.
درمورد روش دوم باید بگم روشم غیر آکادمیک بود و خوب نتونستم جمع و جورش کنم تا توضیح بدم پس فعلا منتظر روش دوم از طرف من نباشید تا ببینم میتونم سر راستش کنم برای بیان کردن یا نه.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۷,۴۸۳ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  تابع مولد ss311 ۰ ۱۳۹ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۴۹ ب.ظ
آخرین ارسال: ss311
  مرتبه زمانی Sanazzz ۱۷ ۵,۲۰۹ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۹۸۶ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۱,۰۰۷ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
  مرتبه زمانی Sanazzz ۰ ۵۴۴ ۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ
آخرین ارسال: Sanazzz
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۲,۶۶۴ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  مشکل در محاسبه مرتبه ایک سوال Mr.R3ZA ۰ ۶۵۶ ۲۴ خرداد ۱۳۹۷ ۰۱:۰۳ ب.ظ
آخرین ارسال: Mr.R3ZA
  پنجمین ازمون استخدام مشترک فراگیر دستگاه های اجرایی کشور naghmeh70 ۷ ۳,۵۶۹ ۳۱ اردیبهشت ۱۳۹۷ ۱۱:۳۵ ب.ظ
آخرین ارسال: αɾια
  تابع ورودی فلیپ فلاپ naghmeh70 ۳ ۸۶۶ ۲۷ فروردین ۱۳۹۷ ۰۶:۵۹ ب.ظ
آخرین ارسال: عزیز دادخواه

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close