حل سوال زیربه چه صورت است ؟
سلام. وقت بخیر. میشه از روش مرتب‌سازی ادغامی برای حل این مساله استفاده کرد. به تعداد [n/2] فراخوانی ادغام آرایه‌های ۱ عضوی داریم که هرکدومش به ۱ مقایسه نیاز داره. به تعداد [n/4] فراخوانی ادغام آرایه‌های ۲ عنصری داریم که هر کدومش به حداکثر ۳ مقایسه نیاز داره. ... به تعداد [n/2^i] فراخوانی ادغام آرایه‌های ۲ به توان i عنصری داریم که هرکدوم به حداکثر ۲ به توان i منهای ۱ مقایسه نیاز داره. جواب میشه:
[tex]\sum_{i=1}^{\lceil lg n\rceil}(2^i -1)\lfloor \frac{n}{2^i}\rfloor[/tex]
به نظرم گزینه ۳ جواب مسالست.
(۰۹ آبان ۱۳۹۵ ۰۱:۲۰ ب.ظ)Jooybari نوشته شده توسط: سلام. وقت بخیر. میشه از روش مرتب‌سازی ادغامی برای حل این مساله استفاده کرد. به تعداد [n/2] فراخوانی ادغام آرایه‌های ۱ عضوی داریم که هرکدومش به ۱ مقایسه نیاز داره. به تعداد [n/4] فراخوانی ادغام آرایه‌های ۲ عنصری داریم که هر کدومش به حداکثر ۳ مقایسه نیاز داره. ... به تعداد [n/2^i] فراخوانی ادغام آرایه‌های ۲ به توان i عنصری داریم که هرکدوم به حداکثر ۲ به توان i منهای ۱ مقایسه نیاز داره. جواب میشه:خیلی ممنون بابت پاسخ
[tex]\sum_{i=1}^{\lceil lg n\rceil}(2^i -1)\lfloor \frac{n}{2^i}\rfloor[/tex]
به نظرم گزینه ۳ جواب مسالست.
ولی سازمان سنجش گزینه ی ۱رو گزینه ی صحیح اعلام کرده است
(۰۹ آبان ۱۳۹۵ ۱۲:۴۳ ب.ظ)mostafaheydar1370 نوشته شده توسط: حل سوال زیربه چه صورت است ؟
در بدترین حالت، یعنی وقتی که همه‌ی n تا وزنه وزن مختلفی داشته باشند، تعداد کل حالات [tex]n![/tex] هست و جوابِ درست، یکی از این [tex]n![/tex] حالت هست.
هر مقایسه‌ای که انجام میدیم، نصف این حالات حذف میشه. مثلاً وقتی میدونیم وزنه‌ی x از y سنگین‌تر هست، تمامی حالاتی که داخلشون x قبل از y اومده حذف میشه، که میشه نصف حالات.
پس جواب دقیقاً عبارت است از [tex]T(n!)=T(\frac{n!}{2})+1= \theta (\lceil \log(n!) \rceil )[/tex]. روشش هم اینطوری هست که هر بار به پترن‌های موجود (جایگشت‌های موجود) نگاه کنیم و دو تا متغیر رو با هم مقایسه کنیم، تا ترتیب اصلی‌شون به دست بیاد و نصف حالات حذف بشه.
البته [tex]\log(n!)[/tex] هم معادل با همون [tex]nlog(n)[/tex] هست ولی اینجا جواب دقیق خواسته.
با حدف گزینه هم میشه جواب داد. برای دو وزنه، فقط یک مقایسه نیاز هست، پس گزینه‌ی ۲ و ۳ نمیشه. برای ۳ وزنه هم ۳ مقایسه نیاز هست، پس گزینه‌ِ ۴ هم نمیشه.
(۰۹ آبان ۱۳۹۵ ۰۴:۲۸ ب.ظ)mostafaheydar1370 نوشته شده توسط: خیلی ممنون بابت پاسخ
ولی سازمان سنجش گزینه ی ۱رو گزینه ی صحیح اعلام کرده است
بله. به نظر میرسه این روش، جواب بهینه رو پیدا نمیکنه. روشی که آقا بهنام برای این مساله ارائه دادن بهینست و با هر مقایسه، فضای حالت رو نصف میکنه.