سوالات قشنگ الگوریتم

[Aida.Mousavi]

سلام
اگه موافق باشین یه ماراتن الگوریتم داشته باشیم
اگر سوالی حل نشد ولی براش ایده ای داشین حتما ایدتونو بگین
هر وقت نیاز به راهنمایی داشتین هم بگین
تا سوالی حل نشه سوال جدید نمیذارم
هرچی بیشتر حل کنید یا ایده بدید سوال جدید بیشتر میذارم

سوال یک : یه آرایه به طول n داریم و عدد x رو هم داریم. الگوریتمی بدین که کوتاهترین زیرآرایه ای از عناصر متوالی رو پیدا کنه که جمع عناصرش بزرگتر مساوی x باشه
مرتبه ی الگوریتمتون کمتر n^2 از باشه.

 

[AlimA]

پاسخ : سوالات قشنگ الگوریتم

زیر آرایه یعنی زیر زیر دنباله یا زیر رشته؟

 

[Aida.Mousavi]

پاسخ : سوالات قشنگ الگوریتم

همون زیر رشته

 

[sa1378]

پاسخ : سوالات قشنگ الگوریتم

سلام
اگه موافق باشین یه ماراتن الگوریتم داشته باشیم
اگر سوالی حل نشد ولی براش ایده ای داشین حتما ایدتونو بگین
هر وقت نیاز به راهنمایی داشتین هم بگین
تا سوالی حل نشه سوال جدید نمیذارم
هرچی بیشتر حل کنید یا ایده بدید سوال جدید بیشتر میذارم

سوال یک : یه آرایه به طول n داریم و عدد x رو هم داریم. الگوریتمی بدین که کوتاهترین زیرآرایه ای از عناصر متوالی رو پیدا کنه که جمع عناصرش بزرگتر مساوی x باشه
مرتبه ی الگوریتمتون کمتر n^2 از باشه.

یه سوال اگه در بدتترین حالت n^2 باشه چی؟
با ذخیره کردن مقدار زیررشته ها حل میشه؟

 

[Aida.Mousavi]

پاسخ : سوالات قشنگ الگوریتم

درسته که میشه با ذخیره ی مقدار زیر رشته ها مساله را با مرتبه ی n^2 هم حل کرد اما راه حلی وجود داره که در بدترین حالت هم مرتبه اش بهتر از n^2 باشه
برای شروع اول سعی کن مساله ی کلاسیک زیر که شباهت زیادی هم به مساله ی اصلی داره با ۳ مرتبه ی مختلف n , nlogn, n^2 حل کنی
مساله ی کلاسیک: در یه آرایه ی n تایی از اعداد صحیح زیر رشته ای با بیشترین مجموع مثبت رو پیدا کنید

 

[sa1378]

پاسخ : سوالات قشنگ الگوریتم

سلام
اگه موافق باشین یه ماراتن الگوریتم داشته باشیم
اگر سوالی حل نشد ولی براش ایده ای داشین حتما ایدتونو بگین
هر وقت نیاز به راهنمایی داشتین هم بگین
تا سوالی حل نشه سوال جدید نمیذارم
هرچی بیشتر حل کنید یا ایده بدید سوال جدید بیشتر میذارم

سوال یک : یه آرایه به طول n داریم و عدد x رو هم داریم. الگوریتمی بدین که کوتاهترین زیرآرایه ای از عناصر متوالی رو پیدا کنه که جمع عناصرش بزرگتر مساوی x باشه
مرتبه ی الگوریتمتون کمتر n^2 از باشه.

مثل همون مسئله ای که گفتین
اول میایم آرایه رو از وسط نصف میکنیم
میایم زیر رشته هارو به سه دسته تقسیم میکنیم:
1-زیر رشته هایی که کلشون در تیکه سمت چپ هستن
2-اونایی که در تیکه راست هستن
3-و اینایی که در هر دو تیکه وجود دارن
برای اولی و دومی رو که بازگشتی میزنیم
برای سومی هم میایم دوتایی که وسط هستن رو اول میگیریم و مجموعشون رو حساب میکنیم ( n/2 و n/2+1 )
و بعد بین n/2-1 و n/2+2 مقایسه انجام میدیم و هرکدوم بزرگتر بود رو به آرایه اضافه میکنیم (حالا اگه مثلا n/2-1 بزرگتر بود بعدش n/2-2 و n/2+2 رو مقایسه میکنیم)
به همین ترتیب هروقت مجموع از x بیشتر شده بود متوقف میکنیم و تعداد و رشته رو برمیگردونیم
طبق این الگوریتم داریم:

که زمان اجرای کل میشه

 

[Aida.Mousavi]

پاسخ : سوالات قشنگ الگوریتم

آفرین ایدت درسته
اما برای حالت سوم لزوما چک کردن یه عدد از سمت راست و یه عدد از سمت چپ کافی نیست و این روش ممکنه کوتاهترین زیر رشته رو نده
مثلا فرض کن آرایه اینه ۱۰۰۰ ۱ ۲ ۳
و x=1003
حالا تو ۱ و ۲ رو مقایسه میکنی و ۲ رو انخاب میکنی بعد ۳ و ۱ رو مقایسه میکنی و ۳ رو انتخاب میکنی در نهایت هم ۱ و ۱۰۰۰ رو انتخاب میکنی اما
اما واقعا نیاز نیست عدد ۳ انتخاب بشه و جواب مساله ۱۰۰۰ ۱ ۲ است
برای حل قسمت سوم راه حلت سعی کن به ایده ای که اول باهاش شروع کردی (یعنی ذخیره ی یه سری چیزا ) فک کنی

 

[Aida.Mousavi]

پاسخ : سوالات قشنگ الگوریتم

خب چون خیلی طول کشید راه حل رو میگم
فرض کنیم آرایمون به صورت

باشه. همونطوری که اشاره شد برای جواب هایی که دو سر آنها در نیمه ی چپ یا دو سر آنها در نیمه ی راست قرار داره مساله را به طور بازگشتی حال میکنیم
حال باید جواب هایی را بررسی کنیم که یک سر آنها در نیمه راست و یک سر آنها در نیمه ی چپ باشه. فرض کنیم s برای i های بین n/2 تا n به صورت زیر تعریف شده باشد

حال فرض کنیم t برای i های بین 1 تا n/2 به صورت زیر تعریف شده باشد

میشه s وt رو از مرتبه ی n/2 محاسبه کرد .
حالا آرایه ی lp را از روی

به صورت صعودی میسازیم یعنی

به این ترتیب با یک بار حرکت روی آرایه ی

از آخر به اول هر بار به اندیسی رسیدیم که از آخرین اندیس یافته شده

بزرگتری داشت آن را به انتهای lp اضافه میکنیم
به این ترتیب آرایه ی lp شامل زیر رشته هایی با مجموع مثبت و صعودی خواهد بود که یک سر آنها در وسط آرایه و سر دیگر آنها در نیمه ی سمت چپ قرار دارد
حال برای تکمیل راه حل روی آرایه ی r از اول به آخر شروع به حرکت میکنیم و به ازای هر اندیس مثل

دنبال اولین اندیسی مانند

میگردیم به طوری که

از آنجایی که lp یک آرایه ی صعودی است هزینه یافتن

به ازای هر

از مرتبه ی

است.
به طریق مشابه آرایه ی rp را نیز تعیرف میکنیم و جواب های متناظرش را محاسبه میکنیم.
از میان تمام جواب های یافته شده کوتاهترین زیر رشته را انتخاب میکنیم
پس هزینه ی کلی یافتن جواب هایی که یک سر آنها در نیمه ی راست و یک سر آنها در نیمه ی چپ قرار دارد از مرتبه ی

است
پس هزینه یکلی الگوریتم به صورت زیر محاسبه میشود

این سوال یه راه حل پیچیده تر هم با استفاده از segment tree داره

---- دو نوشته به هم متصل شده است ----

سوال دو:
فرض کنیم تعداد ی از ارقام 1 تا 9 را دراختیار داریم. d1 تا رقم 1 و d2 تا رقم2 و ... و d9 تا رقم 9 موجود است.
میخواهیم با استفاده از همه یاین ارقام و افزودن تعدادی رقم 0 کوچکترین عدد مضرب 11 را بسازیم.
الگوریتمی از مرتبه ی n[SUP]2 [/SUP]پیدا کنید که بگه کوچک ترین عدد ممکن چند رقمیه؟