زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۱۱:۵۸ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

ساختمان داده سراسری ۹۵ سوال ۵۱

ارسال:
  

mostafaheydar1370 پرسیده:

ساختمان داده سراسری ۹۵ سوال ۵۱

حل سوال زیربه چه صورت است ؟


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

Behnam‌ پاسخ داده:

RE: ساختمان داده سراسری ۹۵ سوال ۵۱

(۰۹ آبان ۱۳۹۵ ۱۲:۴۳ ب.ظ)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] هست ولی اینجا جواب دقیق خواسته.

با حدف گزینه هم میشه جواب داد. برای دو وزنه، فقط یک مقایسه نیاز هست، پس گزینه‌ی ۲ و ۳ نمیشه. برای ۳ وزنه هم ۳ مقایسه نیاز هست، پس گزینه‌ِ ۴ هم نمیشه.
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Jooybari پاسخ داده:

RE: ساختمان داده سراسری ۹۵ سوال ۵۱

سلام. وقت بخیر. میشه از روش مرتب‌سازی ادغامی برای حل این مساله استفاده کرد. به تعداد [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 پاسخ داده:

RE: ساختمان داده سراسری ۹۵ سوال ۵۱

(۰۹ آبان ۱۳۹۵ ۰۱:۲۰ ب.ظ)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]

به نظرم گزینه ۳ جواب مسالست.
خیلی ممنون بابت پاسخ
ولی سازمان سنجش گزینه ی ۱رو گزینه ی صحیح اعلام کرده است
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Jooybari پاسخ داده:

RE: ساختمان داده سراسری ۹۵ سوال ۵۱

(۰۹ آبان ۱۳۹۵ ۰۴:۲۸ ب.ظ)mostafaheydar1370 نوشته شده توسط:  خیلی ممنون بابت پاسخ
ولی سازمان سنجش گزینه ی ۱رو گزینه ی صحیح اعلام کرده است

بله. به نظر میرسه این روش، جواب بهینه رو پیدا نمیکنه. روشی که آقا بهنام برای این مساله ارائه دادن بهینست و با هر مقایسه، فضای حالت رو نصف میکنه.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۱۰ ۱۱,۳۰۰ ۱۵ آذر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: msnmkh
  فیلم آموزش ساختمان داده negin_bt ۰ ۹۶۶ ۲۰ مهر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: negin_bt
  معرفی کتاب برای ساختمان داده siamakaf ۲ ۴,۱۸۴ ۱۲ آبان ۱۳۹۹ ۰۹:۲۱ ق.ظ
آخرین ارسال: siamakaf
  ساختمان داده و پایگاه داده پارسه امیدوار ۴ ۳,۹۶۳ ۱۲ خرداد ۱۳۹۹ ۰۸:۰۳ ب.ظ
آخرین ارسال: marvelous
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۳۶,۱۲۹ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070
  منبع ساختمان داده RASPINA ۷ ۷,۲۳۲ ۱۶ آذر ۱۳۹۸ ۰۱:۳۰ ق.ظ
آخرین ارسال: Behnam‌
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۲,۶۱۹ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous
Question فرادرس برای ساختمان داده marvelous ۷ ۵,۷۰۹ ۱۰ مرداد ۱۳۹۸ ۰۹:۳۷ ب.ظ
آخرین ارسال: marvelous
  معرفی منبع خوب برای ساختمان داده alireza9819 ۴ ۵,۱۶۷ ۱۰ مرداد ۱۳۹۸ ۰۲:۵۸ ب.ظ
آخرین ارسال: marvelous
  سراسری ۹۱ Sanazzz ۲ ۲,۹۷۴ ۰۱ خرداد ۱۳۹۸ ۰۱:۵۳ ق.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close