۰
subtitle
ارسال: #۱
  
حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر
سلام دوستان
این سوال بازگشتی چطور باید حل کرد ؟؟؟
این سوال بازگشتی چطور باید حل کرد ؟؟؟
۸
ارسال: #۲
  
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: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر
ارسال: #۸
  
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر
(۲۵ دى ۱۳۹۲ ۰۸:۴۸ ب.ظ)هاتف نوشته شده توسط: جواب کوتاه اینه که با درخت بازگشت حل اش کنید.
اما اگر دنبال جواب مفصل هستید، الان فرصت اش رو ندارم اما بی جواب نمیذارم اش
حل از طریق درخت بازگشت که واضحه اما میخوام درختش تجزیه تحلیل شه
فکر کنم حل این باشه
[tex]KN(1 \frac{3}{4} \frac{5}{32} ...)= c(KN)\Rightarrow O(KN)[/tex]
۰
ارسال: #۹
  
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر
ممنون از جواب . البته تو ارتفاع درخت اشتباه کردی. ارتفاعش میشه logn + logk علتشم اینه اول هی n تقسیم به دو میشه و k ثابت میمونه بعد n ثابت میمونه و k تقسیم به ۴ میشه.
ارسال: #۱۰
  
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر
(۲۴ بهمن ۱۳۹۲ ۰۴:۲۶ ب.ظ)hap777 نوشته شده توسط: ممنون از جواب . البته تو ارتفاع درخت اشتباه کردی. ارتفاعش میشه logn + logk علتشم اینه اول هی n تقسیم به دو میشه و k ثابت میمونه بعد n ثابت میمونه و k تقسیم به ۴ میشه.
چون هزینه هر سطح داره کم میشه، پس هزینه ای که توی ریشه هست غالب میشه و نیاز به ارتفاع درخت نداریم.
ارسال: #۱۱
  
RE: حل رابطه بازگشتی سوال ۴۸ کنکور ۹۲ کامپیوتر
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close