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

تست ۵۰ طراحی الگوریتم گرایش هوش سال ۹۰

ارسال:
  

rad.bahar پرسیده:

تست ۵۰ طراحی الگوریتم گرایش هوش سال ۹۰

n بازه i =[xi,yi که ۱<i و i<n داده شده اند هر بازه نشاندهنده زمان یک کلاس ذرس است کمترین تعداد اتاق لارم که بدون تداخل به همه کلاس‌ها اتاق داده شود
چواب n*logn
مشاهده‌ی وب‌سایت کاربر

۲
ارسال:
  

homa پاسخ داده:

RE: سوال ۵۰ هوش ۹۰

چیزی که تو کتاب طراحی الگوریتم پارسه به عنوان راه حلش توضیح داده اینجوریه که:

ما ابتدا تمام داده‌ها بر حسب صعودی مرتب می کنیم یعنی تو یک مجموعه هم زمان شروع و هم زمان پایان رو داریم که به ترتیب صعودی هستن

دو پشته در نظر میگیریم‌: یکی برای کلاس های پر و دیگری برای کلاس های خالی

مجموعه را پیمایش میکنیم اگر به یک زمان شروع رسیدیم‌، یک کلاس از پشته‌ی کلاس های خالی pop کرده و در پشته‌ی کلاس های خالی push میکنیم
و اگر به زمان پایان رسیدیم، بر عکس عمل میکینم و یک کلاس از پشته‌ی پر بر میداریم و در پشته‌ی خالی میگذاریم
تعداد کلاس هایی که در پشته‌ی کلاس های پر قرار میدهیم برابر کمترین تعداد کلاس هاست

و چون زمان push و pop حداکثر میشه [tex]O(n)[/tex] پس زمان کل برابر با همون زمان مرتب سازی میشه یعنی:
[tex]O(nlogn)[/tex]

۰
ارسال:
  

atharrashno پاسخ داده:

سوال ۵۰ هوش ۹۰

خوب دوست من مثل انتخاب فعالیت‌ها یا همون سخران‌ها قبلا کس دیگه ای پرسیده بود نمیدانم کجا ولی لینکش بود
به هر حال
شما فعالیت هارا با یه جستجوی مقایسه ای بر حسب زمان پایان مرتب میکنید که میشه nlogn
بعد توی حلقه یه دستور ایف میزاری و چک میکنی ایا زمان شروع کلاس یعدی از زمان پایان کلاس قبلی بیشتر هست ایا؟
اگر بیشتر بود اون زمان به کلاس اختصاص داده میشود
nlogn+n
=
nlogn
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

rad.bahar پاسخ داده:

سوال ۵۰ هوش ۹۰

ممنون از جوابتان ولی دارید اشتباه می کنید انتخاب فعالیت هایی که در کتاب گفته شده با این یک فرق کوجکی دارد
مثلا اگر همان سخنرانها را در نظر ب*****ید صورت سوال جنین است
یک سالن سخنرانی داریم و تعدادی سحنران می خواهیم حداکتر سخنرانی های بدون تداخل را در این سالن برگزار کنیم
ولی سوال پرسیده شده با تبذیل به مضمون متال بالا به این صورت است
تعدادی سخنران داریم می خواهیم حتما همه سخنرانها سخنرانی کنند حداقل تعداد سالتهایی که می شود تخصیص داد تا این امر محقق شود
شما را به خدا اگر کسی جواب این سوال را می داند بگوید
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

fatima1537 پاسخ داده:

سوال ۵۰ هوش ۹۰

توی تقسیم و غلبه هم این مسئله رو داشتیم که ممکنه همیشه یک آرایه به ۲ نیم تقسیم نشه و میتونه به چند بخش تقسیم بشه و هر بخش هم به طور بازگشتی به بخشهای دیگه تقسیم بشه.که این روش هم از مرتبه nlogn هست

۰
ارسال:
  

homa پاسخ داده:

RE: سوال ۵۰ هوش ۹۰

اون چیزی که من به ذهنم میرسه اینه که ما میتونیم از روش مسئله‌ی سخنرانی‌ها استفاده کنیم.

اونجا ما حداکثر مجموعه‌ی غیر هم پوشان برای سخنرانی‌ها رو انتخاب میکنیم اینجا هم همین کار رو میکنیم زیرا اعضای این مجموعه میتونن تو یک کلاس بر گزار بشن حالا اینا رو از مجموعه اصلی حذف میکنیم و دوباره بین باقی مونده‌ها باز حداکثر رو پیدا میکنیم به همین ترتیب تا مجموعه خالی بشه.

نظرتون چیه؟؟؟؟

ارسال:
  

rad.bahar پاسخ داده:

RE: سوال ۵۰ هوش ۹۰

(۰۶ بهمن ۱۳۹۰ ۱۲:۱۴ ق.ظ)homa نوشته شده توسط:  اون چیزی که من به ذهنم میرسه اینه که ما میتونیم از روش مسئله‌ی سخنرانی‌ها استفاده کنیم.

اونجا ما حداکثر مجموعه‌ی غیر هم پوشان برای سخنرانی‌ها رو انتخاب میکنیم اینجا هم همین کار رو میکنیم زیرا اعضای این مجموعه میتونن تو یک کلاس بر گزار بشن حالا اینا رو از مجموعه اصلی حذف میکنیم و دوباره بین باقی مونده‌ها باز حداکثر رو پیدا میکنیم به همین ترتیب تا مجموعه خالی بشه.

نظرتون چیه؟؟؟؟
با تشکر از جوابتان
هر بار اجرای الگوریتم برای یافتن حداکثر مجموعه‌ی غیر هم پوشان O(N) اگر فرض کنیم همه N محموعه همپوشانی داشته باشند مجبوربم N بار الگوریتم را تا رسیدن به محموعه خالی تکرار کنیم که میشه N^2
کسی راه حل دیگری ندارد لطفا جواب بدید
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

rad.bahar پاسخ داده:

RE: سوال ۵۰ هوش ۹۰

ممنون از جوابتان
ییخشید که گیجم ممکن این سوال را با این متال حل کنید
(۱و۳)
(۲و۴)
(۵و۶)
(۷و۱۰)
(۸و۹)
اینکه کفتید داده‌ها را مرتب کردید منظورتان این هست اول بر اساس زمان شروع بعد بر اساس زمان پایان مرتب می کنید؟
مشاهده‌ی وب‌سایت کاربر

ارسال:
  

homa پاسخ داده:

RE: سوال ۵۰ هوش ۹۰

(۰۶ بهمن ۱۳۹۰ ۰۷:۴۲ ب.ظ)rad.bahar نوشته شده توسط:  ممنون از جوابتان
ییخشید که گیجم ممکن این سوال را با این متال حل کنید
(۱و۳)
(۲و۴)
(۵و۶)
(۷و۱۰)
(۸و۹)
اینکه کفتید داده‌ها را مرتب کردید منظورتان این هست اول بر اساس زمان شروع بعد بر اساس زمان پایان مرتب می کنید؟

همه داده‌ها رو در نظر میگیری چه زمان شروع و چه زمان پایان ولی میفهمی کدومش شروع هست و کدوم پایان.
اینجا به طور کلی ۱۰ تا عدد داری با [tex]O(nlogn)[/tex] مرتب میکنی ارایه میشه:
[tex]\left \{1_{s},2_{s},3_{f},4_{f},5_{s},6_{f},7_{s},8_{s},9_{f},10_{f} \right.\left. \right \}[/tex]

حالا ارایه رو از اول پیمایش میکنی و هر وقت به داده ایی مربوط به زمان شروع رسیدی یک کلا س میذاری داخل پشته و هر وقت هم یک داده مربوط به زمان پایان دیدی یک کلاس از داخل پشته‌ی کلاس‌ها pop میکنی .
حداکثر کلاس هایی که داخل پشته گذاشتی میشه حداقل کلاس ها
تو این مثال پشته حدا کثر به اندازه ۲ پر میشه.
حالا ممکنه بعضی وقتها خالی بشه یا اینکه فقط یکی تو پشته باشه اما مهم اینه که یک بار ما ۲ تا کلاس تو پشته داشتیم.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  بهترین گرایش ها برای اپلای در مقطع دکتری rezamim2020 ۰ ۱۳۰ ۱۶ شهریور ۱۳۹۹ ۰۴:۴۴ ب.ظ
آخرین ارسال: rezamim2020
  سوال درباره طراحی سایت و جدول ahantell ۰ ۹۹ ۰۲ مرداد ۱۳۹۹ ۱۰:۴۳ ق.ظ
آخرین ارسال: ahantell
  طراحی سایت شرکتی ideasoft98 ۰ ۱۰ ۲۶ اسفند ۱۳۹۸ ۰۲:۵۶ ب.ظ
آخرین ارسال: ideasoft98
  جواب سوالهای تخصصی دکتری هوش مصنوعی سال ۹۸ Lootus ۱ ۵۰۰ ۲۹ بهمن ۱۳۹۸ ۰۱:۴۳ ب.ظ
آخرین ارسال: machine86
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۴۷۶ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t
  منابع آزمون دکتری گرایش تجارت الکترونیک wskf ۲ ۲,۰۰۳ ۲۱ دى ۱۳۹۸ ۰۵:۱۶ ب.ظ
آخرین ارسال: parisa1140
  تاثیر بودجه در انتخاب شرکت طراحی سایت wone ۱ ۲۰ ۲۳ آبان ۱۳۹۸ ۰۱:۱۴ ب.ظ
آخرین ارسال: xiaomi
  امکان تحصیل مجدد در گرایش دیگر در مقطع کارشناسی ارشد؟؟؟؟؟؟ minafunda ۵ ۱,۶۴۲ ۱۳ مهر ۱۳۹۸ ۰۲:۵۴ ب.ظ
آخرین ارسال: saharfarhang
  استالینگز یا سیلبر؟برای گرایش نرم افزار؟ ریحان ۱۲ ۳,۳۱۲ ۰۷ مهر ۱۳۹۸ ۱۲:۱۸ ق.ظ
آخرین ارسال: marvelous
  طراحی یک سیستم نورانی هوشمند marvelous ۸ ۸۸۲ ۲۸ مرداد ۱۳۹۸ ۰۳:۵۰ ق.ظ
آخرین ارسال: marvelous

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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