خب اون پستی که گفتید هم مشکل به جای خودش مونده بود!!یه لگاریتم اضافه میاد

درخت رو ببینید !!با قضیه تورنمنت هم که اشنایی داریم ولی بازم یه مرور مختصر انجام میدیم.
ببنید فرض کنیم میخوایم K امین مینیمم رو پیدا کنیم یه روش اینه که بیایم از بین n عنصر با انجام n-1 مقایسه مینیمم رو پیدا کنیم و از بین n-1عنصر باقیمونده با n-2 مقایسه دومین عنصر میمینمم رو پیدا کنیم و....
ولی میخوایم این تعداد مقایسه رو کاهش بدیم و میایم از روش تورنمنت استفاده میکنیم که مثل مسابقات حذفی میمونه و توی هر مرحله عنصر کوچکتر باقی میمونه و به مرحله بعدی راه پیدا میکنه و تا زمانی که کوچکترین عنصر باقی میمونه.
حالا شکل درخت رو ببینید ما اینجا مثلا ۱۶ تا عنصر داریم(کل عناصر در برگ قرار دارن و به سمت ریشه که کوچکترین عنصر هستش در حال حرکتیم) برای پیدا کردن کوچکترین عنصر ما ۱۵ تا مقایسه انجام میدیم!!بع عبارتی اگه ما n عنصر داشته باشم n-1 مقایسه برای پیدا کردن مینیمم انجام میدیم!!تا اینجا با حالت قبل تفاوتی نداره!!حالا برای پیدا کردن دومین عنصر مینیمم قبول داری این عنصر حتما تو یه جایی به عنصر مینیمم باخته؟؟؟؟درسته؟پس یعنی تو یکی از مقایسه ها از عنصر مینیمم بزرگتر بوده(یعنی حتما با عنصر مینیمم مقایسه شده) حالا تو عکس
دقت کنیدتوی برگها یه نود مشکی و یکی حاشیه تیره داره اونی که مشکی هستش فرض کردیم که نصر مینیمم اونجا بوده اون جاهایی که حاشیه تیره دارن میدونیم که حتما یکی از اونا دومین عنصر مینیمم بوده و حالا تعداشون [tex]\lceil Log(n) \rceil[/tex] تاست.میتونی مثلا برای ۱۶ ببینی میشه ۴ که اینجا هم ۴ تاست!!پس تعداد عناصری که الان برای پیدا کردن دومین عنصر باید مورد بررسی قرار بگیرن [tex]\lceil Log(n) \rceil[/tex] تان که با [tex]\lceil Log(n) \rceil-1[/tex] مقایسه میتونیم دومین عنصر مینیمم رو پیدا کنیم.و حالا برای پیدا کردن سومین عنصر مینیمم این عنصر یا با مینیمم مقایسه شده و حذف شده و یا با دومین مینیمم مقایسه شده و حذف شده و گفتیم که مینیمم با
[tex]\lceil Log(n) \rceil[/tex] عنصر مقایسه شده و دومین عنصر مینیمم هم با [tex]\lceil Log(n) \rceil-1[/tex] عنصر مقایسه شده که مجموع اینا میشه [tex]2\lceil Log(n) \rceil-1[/tex] و یه نکته ای که هست اینه که این [tex]2\lceil Log(n) \rceil-1[/tex] یکیشون دومین مینیمم هستش(ببینید ما با [tex]Lg(n)-1[/tex] مقایسه دومین مینیمم رو به دست اوردیم ولی الان توی مجموع عناصری که مقایسه میشن خود دومین مینیمم رو هم حساب کردیم و الان باید یکی از مجموع کم کنیم که این در واقع همون دومین مینیمم میشه که در نظرش نمیگیریم) و این دومین مینیمم رو در نظر نمیگیریم و الان تعداد عناصر میشن:[tex]2\lceil Lg(n) \rceil-2[/tex] که با [tex]2\lceil Lg(n) \rceil-3[/tex] سومین مینیمم رو به دست میاریم
پس تعداد کل مقایسه ها شد:

[tex]n-1 \lceil Log(n) \rceil-1 2\lceil Log(n) \rceil-3=n 3\lceil Log(n) \rceil-5[/tex]

ببخشید خیلی بد گفتم!!!یکم توضیح این سخته

(۲۰ دى ۱۳۹۳ ۰۱:۰۳ ب.ظ)zahra.s نوشته شده توسط:  سلام دوستان
واسه بدست آوردن kامین کوچکترین عنصر تو کتابا یه فرمولایی نوشتن و میشه بدست آورد ولی من واسم جا نمیفته,نمیخوام فرمول حفظ کنم که یادم بره میخوام بفهمم که چطوری حساب میکنیم مثلاً توضیحات ۳ومین کوچکترین عنصر که اگه اشتباه نکنم طبق حرف دوستان باید سوال ص۲۶ از کتاب ۶۰۰ مسئله باشه ,این موضوع هست, میشه سلیس تر توضیح بدید؟
قبلاً بچه ها تاپیکی مشابه زدن ولی من سوالم فرق میکنه مدیران عزیز

این فرمول خیلی ساده ست اما اصولا توی کنکور ارشد دیگه سوال حفظی از ساختمان الگوریتم نمیدن نخونش مسئولیتش بامن نهایتش حفظش کن

(۲۰ دى ۱۳۹۳ ۰۱:۱۹ ب.ظ)tanhatarin نوشته شده توسط:  

(20 دى ۱۳۹۳ ۰۱:۰۳ ب.ظ)zahra.s نوشته شده توسط:  سلام دوستان
واسه بدست آوردن kامین کوچکترین عنصر تو کتابا یه فرمولایی نوشتن و میشه بدست آورد ولی من واسم جا نمیفته,نمیخوام فرمول حفظ کنم که یادم بره میخوام بفهمم که چطوری حساب میکنیم مثلاً توضیحات ۳ومین کوچکترین عنصر که اگه اشتباه نکنم طبق حرف دوستان باید سوال ص۲۶ از کتاب ۶۰۰ مسئله باشه ,این موضوع هست, میشه سلیس تر توضیح بدید؟
قبلاً بچه ها تاپیکی مشابه زدن ولی من سوالم فرق میکنه مدیران عزیز

این فرمول خیلی ساده ست اما اصولا توی کنکور ارشد دیگه سوال حفظی از ساختمان الگوریتم نمیدن نخونش مسئولیتش بامن نهایتش حفظش کن

از توصیت ممنون و باهات موافقم در ضمن از لطف بالای شما در مسئولیت پذیری هم ممنونم
ولی چون حفظی نمیدن دنبال تحلیلشم ,تحلیل منحصربفرد واسه یه سوال نیست در سوالای دیگه کمک میکنه

ببینید من تحلیلشو میدونم ولی با فرمول اخر فصل دوم پوران تناقض داره!!!!حالا نمیدونم کتاب پوران اشتباهه یا تحلیل دکتر قدسی

(۲۰ دى ۱۳۹۳ ۰۱:۵۰ ب.ظ)miladcr7 نوشته شده توسط:  ببینید من تحلیلشو میدونم ولی با فرمول اخر فصل دوم پوران تناقض داره!!!!حالا نمیدونم کتاب پوران اشتباهه یا تحلیل دکتر قدسی

تحلیلتون رو بگید ما تناقض رو برطرف میکنیم
البته منم فک میکردم تناقض داره بعداً فهمیدم نه , تفاهم داره در این پست هم بهش اشاره شده

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

بسیار ممنون