سلام دوستان .
این سوال ۱۰۰ از طراحی الگوریتم نرم افزار از آزمون ۵۰ درصد اول پارسه بود :
![[تصویر: QUESTION_100.png]](https://img.manesht.ir/QUESTION_100.png)
و این هم پاسخ آن است که در زیر آمده :
![[تصویر: ANSWER_100.png]](https://img.manesht.ir/ANSWER_100.png)
سوال من اینه که در اون قسمتی که [tex]g(k)[/tex] محاسبه می شود، چطور با استفاده از قضیه اصلی، به چنین پاسخی رسیده است ؟
من فکر می کنم پاسخ درست [tex]g(k) = \theta (k)[/tex] است.
ممنونم.
(۰۲ آذر ۱۳۹۲ ۰۵:۴۷ ق.ظ)Morris نوشته شده توسط: سلام دوستان .
این سوال ۱۰۰ از طراحی الگوریتم نرم افزار از آزمون ۵۰ درصد اول پارسه بود :
و این هم پاسخ آن است که در زیر آمده :
سوال من اینه که در اون قسمتی که [tex]g(k)[/tex] محاسبه می شود، چطور با استفاده از قضیه اصلی، به چنین پاسخی رسیده است ؟
من فکر می کنم پاسخ درست [tex]g(k) = \theta (k)[/tex] است.
ممنونم.
به نظر من هم پاسخ شما درسته.
(۰۲ آذر ۱۳۹۲ ۰۸:۰۷ ق.ظ)e.sharmi نوشته شده توسط: به نظر من هم پاسخ شما درسته.
بسیار ممنونم.
(۰۲ آذر ۱۳۹۲ ۱۱:۵۹ ب.ظ)Morris نوشته شده توسط:(02 آذر ۱۳۹۲ ۰۸:۰۷ ق.ظ)e.sharmi نوشته شده توسط: به نظر من هم پاسخ شما درسته.بسیار ممنونم.
البته یه جاهایی استفاده از مستر صحیح نیست و باید از درخت استفاده کرد. جاهایی که وقتی لگاریتم میگیریم از f رابطه به صورت چند جمله ای بزرگتر یا کوچکتر نباشه. البته اینجا چند جمله ای کوچکتره و نباید موردی باشه ولی بازم شک دارم که نکنه از اون حالات خاص هست
(۰۳ آذر ۱۳۹۲ ۱۲:۰۳ ق.ظ)zimenswall نوشته شده توسط:(02 آذر ۱۳۹۲ ۱۱:۵۹ ب.ظ)Morris نوشته شده توسط:(02 آذر ۱۳۹۲ ۰۸:۰۷ ق.ظ)e.sharmi نوشته شده توسط: به نظر من هم پاسخ شما درسته.بسیار ممنونم.
البته یه جاهایی استفاده از مستر صحیح نیست و باید از درخت استفاده کرد. جاهایی که وقتی لگاریتم میگیریم از f رابطه به صورت چند جمله ای بزرگتر یا کوچکتر نباشه. البته اینجا چند جمله ای کوچکتره و نباید موردی باشه ولی بازم شک دارم که نکنه از اون حالات خاص هست
کاملا حق با شماست !
البته دوستمون آقای ریمان در ارسال زیر این قسمت از مساله را با استفاده از درخت بازگشتی حل کردند که به همان جواب پارسه رسیده ! من که کاملا گیج شدم !!!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۳ آذر ۱۳۹۲ ۱۲:۵۷ ق.ظ)Morris نوشته شده توسط: کاملا حق با شماست !
البته دوستمون آقای ریمان در ارسال زیر این قسمت از مساله را با استفاده از درخت بازگشتی حل کردند که به همان جواب پارسه رسیده ! من که کاملا گیج شدم !!!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
البته ایشون درخت را اشتباه کشیده بودن. درختشون دو شاخه ای شده بود و این اشتباهه.
من درختشو کشیدم و جوابی که بدست آوردم ۲k-2 بود. البته اگر درست گفته باشم.
(۰۳ آذر ۱۳۹۲ ۰۱:۰۱ ق.ظ)zimenswall نوشته شده توسط:(03 آذر ۱۳۹۲ ۱۲:۵۷ ق.ظ)Morris نوشته شده توسط: کاملا حق با شماست !
البته دوستمون آقای ریمان در ارسال زیر این قسمت از مساله را با استفاده از درخت بازگشتی حل کردند که به همان جواب پارسه رسیده ! من که کاملا گیج شدم !!!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
البته ایشون درخت را اشتباه کشیده بودن. درختشون دو شاخه ای شده بود و این اشتباهه.
من درختشو کشیدم و جوابی که بدست آوردم ۲k-2 بود. البته اگر درست گفته باشم.
گویا حواس من هم مثل ایشان پرت بوده
!
درختی که من بدست آوردم اینجوری بود
اگر بدخطه یا اشتباهی هست ببخشید.
![[تصویر: 227205_DSCN6370.JPG]](https://img.manesht.ir/227205_DSCN6370.JPG)
(۰۲ آذر ۱۳۹۲ ۰۵:۴۷ ق.ظ)Morris نوشته شده توسط: سلام دوستان .
این سوال ۱۰۰ از طراحی الگوریتم نرم افزار از آزمون ۵۰ درصد اول پارسه بود :
و این هم پاسخ آن است که در زیر آمده :
سوال من اینه که در اون قسمتی که [tex]g(k)[/tex] محاسبه می شود، چطور با استفاده از قضیه اصلی، به چنین پاسخی رسیده است ؟
من فکر می کنم پاسخ درست [tex]g(k) = \theta (k)[/tex] است.
ممنونم.
سلام دوست گرامی
این یک تبصره در قضیه اساسی هست که اگر رابطه بازگشتی به این صورت بود:
T(n)=aT(n/b) + (n ^ log a) * (log n) ^ d
جواب این خواهد بود: n ^ log a * log n ^ (d+1) = javab
در ضمن در روابط بالا منطور لوگ a بر مبنای b هست.
(۱۳ آذر ۱۳۹۲ ۱۲:۰۵ ق.ظ)misagh01 نوشته شده توسط: این یک تبصره در قضیه اساسی هست که اگر رابطه بازگشتی به این صورت بود:
T(n)=aT(n/b) + (n ^ log a) * (log n) ^ d
جواب این خواهد بود: n ^ log a * log n ^ (d+1) = javab
در معادله بالا چیزی که شما گفتید صدق نمیکنه.
بله ! همونطور که دوستمون zimenswall گفتند، این شرط در این مثال صدق نمی کند.
ممنون از شما.