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

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

ارسال:
  

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 میکنی .
حداکثر کلاس هایی که داخل پشته گذاشتی میشه حداقل کلاس ها
تو این مثال پشته حدا کثر به اندازه ۲ پر میشه.
حالا ممکنه بعضی وقتها خالی بشه یا اینکه فقط یکی تو پشته باشه اما مهم اینه که یک بار ما ۲ تا کلاس تو پشته داشتیم.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل و بررسی سوالات مدارمنطقی دکتری ۹۲ گرایش معماری nomad:D ۲۵ ۲۳,۹۳۲ ۲۰ بهمن ۱۴۰۲ ۱۰:۳۸ ق.ظ
آخرین ارسال: masoumeh97
  دانلود سوالات تخصصی گرایش فناوری اطلاعات آزمون دکتری ۹۱(کد ۲۳۵۸) Lonely Palm ۲ ۵,۸۵۶ ۲۶ دى ۱۴۰۲ ۰۲:۳۳ ب.ظ
آخرین ارسال: bijibuji
  گرایش های علوم کامپیوتر alisaaa ۴ ۳,۶۵۱ ۱۳ آذر ۱۴۰۲ ۰۴:۲۷ ب.ظ
آخرین ارسال: hashemhamidi
  [دانلود] ویس و جزوه ی طراحی الگوریتم سیدجوادی هاتف ۳۳ ۴۰,۷۹۴ ۰۴ تیر ۱۴۰۲ ۰۲:۰۳ ب.ظ
آخرین ارسال: solmaz58
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۴۳۶ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  دانشگاه صنعتی اصفهان یا گرایش معماری امیرکبیر sima84 ۰ ۱,۷۶۴ ۱۶ شهریور ۱۴۰۰ ۰۳:۳۷ ب.ظ
آخرین ارسال: sima84
  منابع آزمون دکتری گرایش تجارت الکترونیک wskf ۳ ۵,۹۷۱ ۳۱ اردیبهشت ۱۴۰۰ ۱۰:۱۳ ب.ظ
آخرین ارسال: Ametrine
  طراحی ui/ux kimiya1234 ۲ ۲,۰۰۹ ۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ
آخرین ارسال: farsamw
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۲۸۲ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  کارنامه نهایی ازمون دکتری داخل سال ۱۳۹۲-گرایش معماری کامپیوتر انرژی مثبت ۱ ۴,۱۱۲ ۱۷ بهمن ۱۳۹۹ ۰۲:۲۸ ق.ظ
آخرین ارسال: hmaryam567

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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