انجمنصفحه اولجستجوی انجمن

[khavar_1365]

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

[summer_66]

(۱۴ مهر ۱۳۹۰ ۱۰:۴۷ ق.ظ)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]

اگر تابع [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]

(۱۴ مهر ۱۳۹۰ ۰۲:۱۴ ب.ظ)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] هست .شکلش رو بکشید تا متوجه بشید اگه موضوع براتون روشن نشد بگید تا شکلش رو بکشم.

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

[summer_66]

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

این راه اول. راه دوم هم براتون میفرستم.

[khavar_1365]

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

[summer_66]

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

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