حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - نسخهی قابل چاپ |
حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - reza6966 - 25 دى ۱۳۹۲ ۰۸:۴۲ ب.ظ
سلام دوستان این سوال بازگشتی چطور باید حل کرد ؟؟؟ [attachment=14660] |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - هاتف - ۲۵ دى ۱۳۹۲ ۰۸:۴۸ ب.ظ
جواب کوتاه اینه که با درخت بازگشت حل اش کنید. اما اگر دنبال جواب مفصل هستید، الان فرصت اش رو ندارم اما بی جواب نمیذارم اش |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - نارین - ۲۶ دى ۱۳۹۲ ۱۰:۴۶ ب.ظ
(۲۵ دى ۱۳۹۲ ۰۸:۴۸ ب.ظ)هاتف نوشته شده توسط: جواب کوتاه اینه که با درخت بازگشت حل اش کنید. ممنون میشم اگه توضیحش بدین منم نتونستم حلش کنم |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - reza6966 - 27 دى ۱۳۹۲ ۰۲:۱۶ ب.ظ
(۲۵ دى ۱۳۹۲ ۰۸:۴۸ ب.ظ)هاتف نوشته شده توسط: جواب کوتاه اینه که با درخت بازگشت حل اش کنید. حل از طریق درخت بازگشت که واضحه اما میخوام درختش تجزیه تحلیل شه [attachment=14701] فکر کنم حل این باشه [tex]KN(1 \frac{3}{4} \frac{5}{32} ...)= c(KN)\Rightarrow O(KN)[/tex] |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - هاتف - ۰۶ بهمن ۱۳۹۲ ۰۹:۰۳ ب.ظ
سلام روی کاغذ حل کردم، ببخشید که کیفیت خوبی نداره ولی خب خواناست. |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - نارین - ۰۸ بهمن ۱۳۹۲ ۱۱:۰۲ ب.ظ
(۰۶ بهمن ۱۳۹۲ ۰۹:۰۳ ب.ظ)هاتف نوشته شده توسط: سلام سپاسگذارم از جواب خوبتون ولی من اینجایی را که ارتفاع درخت را بدست میارید متوجه نمیشم یه سوال مشابهی هم دیدم که با مثال ارتفاع درخت را بدست آورده بود ولی با مثال زمان بیشتری از آدم گرفته میشه،اگه ممکنه یه کمی بیشتر توضیح بدین ممنون میشم |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - هاتف - ۰۹ بهمن ۱۳۹۲ ۱۰:۲۳ ق.ظ
(۰۸ بهمن ۱۳۹۲ ۱۱:۰۲ ب.ظ)نارین نوشته شده توسط: سپاسگذارم از جواب خوبتون ولی من اینجایی را که ارتفاع درخت را بدست میارید متوجه نمیشم یه سوال مشابهی هم دیدم که با مثال ارتفاع درخت را بدست آورده بود ولی با مثال زمان بیشتری از آدم گرفته میشه،اگه ممکنه یه کمی بیشتر توضیح بدین ممنون میشمخواهش می کنم. درخت بالا رو ببینید، میدونیم که وقتی یک رابطه بازگشتی تموم میشه که به یک مقدار ثابت و اولیه برسه مثلا وقتی n بشه ۱ بعدش دیگه تابع return میکنه، اون همون برگ های درخت هست. اگر بخواهیم بدونیم درخت چند سطح داره باید ببینم طولانی ترین شاخه اش کجا ختم میشه، توی شاخه سمت چپ n داره هربار بر ۲ تقسیم میشه و توی شاخه ی سمت راست k هربار داره بر ۴ تقسیم میشه، پس میشه نتیجه گرفت شاخه سمت چپ دیـــرتر به برگ هاش میرسه (دقت کنید) پس اگر بخواهیم ارتفاع شاخه سمت چپ رو بدست بیاریم مطمئن هستیم که شاخه سمت راستی ازش کمتره. توی خط سوم نوشتم که [tex](\frac{1}{2})^{i} n \geqslant 1[/tex] که i همون سطح درخت هست، مثلا در سطح دوم که i=2 هست میشه [tex]\frac{1}{4}n[/tex] این عبارت تا وقتی از ۱ بزرگتر هست سطح جدید داریم، بعدش دیگه عملیات ریاضی هست تا i بدست بیاد، میبینید که i میتونه حداکثر logn بشه هزینه ی هر سطح هم که قبلا حساب کردم، خط بعدش داره به ازای هر سطح اون هزینه رو حساب میکنه منتها چون حل اون سیگما سخته از یه قضیه استفاده میکنیم (اسم قضیه یادم نیست) و حد بالای سیگما رو بی نهایت میگیریم، nk که ربطی به سیگما ندارند بیرون میان و خود سیگما هم یه عبارت تصاعد هندسی هست که به راحتی قابل حله، در نهایت هم ۴nk بدست اومده که از مرتبه [tex]O(nk)[/tex] میشه اگر دقت کنید همه جا دست بالا گرفتیم و خیلی دقیق حساب نکردیم، برای همین درخت بازگشت مرتبه رو میتونه حساب کنه و نه زمان دقیق عملیات. |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - نارین - ۰۹ بهمن ۱۳۹۲ ۰۷:۲۴ ب.ظ
اوکی سپاسگذارم ، الان متوجه شدم |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - hap777 - 24 بهمن ۱۳۹۲ ۰۴:۲۶ ب.ظ
ممنون از جواب . البته تو ارتفاع درخت اشتباه کردی. ارتفاعش میشه logn + logk علتشم اینه اول هی n تقسیم به دو میشه و k ثابت میمونه بعد n ثابت میمونه و k تقسیم به ۴ میشه. |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - Riemann - 24 بهمن ۱۳۹۲ ۰۴:۳۶ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۴:۲۶ ب.ظ)hap777 نوشته شده توسط: ممنون از جواب . البته تو ارتفاع درخت اشتباه کردی. ارتفاعش میشه logn + logk علتشم اینه اول هی n تقسیم به دو میشه و k ثابت میمونه بعد n ثابت میمونه و k تقسیم به ۴ میشه. چون هزینه هر سطح داره کم میشه، پس هزینه ای که توی ریشه هست غالب میشه و نیاز به ارتفاع درخت نداریم. |
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر - hap777 - 24 بهمن ۱۳۹۲ ۰۴:۵۵ ب.ظ
(۲۴ بهمن ۱۳۹۲ ۰۴:۳۶ ب.ظ)Riemann نوشته شده توسط: چون هزینه هر سطح داره کم میشه، پس هزینه ای که توی ریشه هست غالب میشه و نیاز به ارتفاع درخت نداریم. درسته. منم فقط ارتفاع درختو گفتم اشتباهه نه جواب مسئله. |