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

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

ارسال:
  

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 نوشته شده توسط:  سلام دوست عزیز.
بسیار سپاسگزارم از لطف و راهنماییتون.ممنون میشم اگه بیشتر از این بتونید تو حل اینجور مسایلی کمکم کنید بخصوص درخت بارگشتی.
با تشکر
اگه کمکی از دستم بربیاد در خدمت هستم.
درمورد روش دوم باید بگم روشم غیر آکادمیک بود و خوب نتونستم جمع و جورش کنم تا توضیح بدم پس فعلا منتظر روش دوم از طرف من نباشید تا ببینم میتونم سر راستش کنم برای بیان کردن یا نه.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مرتبه ی زمانی حلقه for و while farzaneh6 ۷ ۴,۵۰۳ ۲۳ مهر ۱۳۹۱ ۰۳:۴۵ ب.ظ
آخرین ارسال: zeinab
  مرتبه زمانی *Najmeh* ۳ ۳,۰۰۷ ۲۳ مهر ۱۳۹۱ ۱۰:۵۰ ق.ظ
آخرین ارسال: zeinab
  سوال از بازگشتی Aurora ۷ ۳,۲۰۳ ۱۷ شهریور ۱۳۹۱ ۱۱:۴۰ ب.ظ
آخرین ارسال: azad_ahmadi
  چند سوال از مرتبه زمانی و ... (تمرینات clrs) fatemeh-r ۱۷ ۷,۳۱۳ ۲۴ تیر ۱۳۹۱ ۰۴:۴۰ ب.ظ
آخرین ارسال: Shokoufe.S
  (کمک در حل تست) تابع بازگشتی مربوط به برج هانوی samaneh_aftab ۴ ۵,۴۱۴ ۰۵ تیر ۱۳۹۱ ۰۱:۰۴ ب.ظ
آخرین ارسال: Parva
Lightbulb درخواست راهنمایی در حل رابطه بازگشتی - rasool - ۵۱ ۵,۴۸۸ ۲۴ بهمن ۱۳۹۰ ۰۷:۱۷ ق.ظ
آخرین ارسال: sasanlive
Lightbulb روابط بازگشتی دو متغیره - rasool - ۳ ۱,۹۷۸ ۰۶ دى ۱۳۹۰ ۰۵:۲۷ ب.ظ
آخرین ارسال: homa
  مرتبه الگوریتم hamed_k2 ۹ ۳,۴۰۸ ۱۰ آذر ۱۳۹۰ ۰۲:۳۳ ق.ظ
آخرین ارسال: hamed_k2
  یه سوال بازگشتی از قضیه اصلی پشتکار ۱۱ ۳,۳۴۳ ۰۹ آبان ۱۳۹۰ ۱۲:۱۲ ق.ظ
آخرین ارسال: sasanlive
Smile حل رابطه بازگشتی Mojtaba ۹ ۲,۲۱۴ ۰۶ آبان ۱۳۹۰ ۱۱:۰۵ ب.ظ
آخرین ارسال: - rasool -

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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