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

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

ارسال:
  

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پاسخنامه تشریحی طراحی الگوریتم موسسه ماهان برای درس طراحی الگوریتم کنکور ۹۱ مهندسی MSsoftware ۸ ۶,۸۸۳ ۰۴ بهمن ۱۳۹۱ ۰۱:۰۲ ق.ظ
آخرین ارسال: fa_karoon
  تست ۳۸ طراحی الگوریتم سال ۸۵ پشتکار ۱۰ ۳,۲۵۴ ۲۹ دى ۱۳۹۱ ۱۰:۲۴ ب.ظ
آخرین ارسال: csharpisatechnology
  تست ۴۰ طراحی الگوریتم نرم افزار ۸۶ reyhaneh64 ۲ ۱,۸۶۰ ۲۹ دى ۱۳۹۱ ۰۳:۱۲ ب.ظ
آخرین ارسال: csharpisatechnology
  تست ۵۳، هوش ۸۷ reyhaneh64 ۰ ۹۰۹ ۰۳ تیر ۱۳۹۱ ۰۶:۱۵ ب.ظ
آخرین ارسال: reyhaneh64
  بررسی سوالات طراحی الگوریتم ۹۱ مهندسی کامپیوتر -گرایش هوش fatima1537 ۸۶ ۳۴,۹۳۸ ۲۰ اسفند ۱۳۹۰ ۱۰:۴۰ ب.ظ
آخرین ارسال: anyone
  تست (مرتبه اجرایی ) طراحی الگوریتم کنکور ۹۱ vijay ۷ ۳,۵۷۴ ۱۵ اسفند ۱۳۹۰ ۰۶:۳۴ ب.ظ
آخرین ارسال: لهمشد
  بررسی سوالات طراحی الگوریتم ۹۱ فناوری اطلاعات uniquegirl ۲۸ ۸,۷۶۷ ۰۷ اسفند ۱۳۹۰ ۱۲:۲۶ ق.ظ
آخرین ارسال: rotbe
  تست (گراف) طراحی الگوریتم آی تی کنکور ۹۱ vijay ۴ ۲,۹۳۵ ۰۱ اسفند ۱۳۹۰ ۰۷:۴۰ ق.ظ
آخرین ارسال: MSZ
  تست مرتبه اجرایی طراحی الگوریتم کنکور ۹۱ vijay ۲ ۲,۶۶۶ ۳۰ بهمن ۱۳۹۰ ۰۲:۵۴ ب.ظ
آخرین ارسال: arixooo
  تست ۳۲ طراحی الگوریتم سال ۹۰ Anahita.R ۳ ۲,۳۳۸ ۲۶ بهمن ۱۳۹۰ ۱۲:۳۶ ب.ظ
آخرین ارسال: atharrashno

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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