سلام صبحتون بخیر.
این هفته میخوایم روی دو تا موضوع جستجوی دودیی و روش حریصانه کار کنیم . مسابقه ی این هفته رو از امشب شروع میکنیم تا امروز وقت برای خوندن منابع داشته باشین.
جستجوی دودویی (BinarySearch) : اکثرا این ذهنیت رو برای این جستجو داریم که ما یدونه آرایه ی مرتب داریم و میخوایم یه عنصری رو ازش پیدا کنیم . چون این جستجو هر دفعه بازه رو نصف میکنه پس این کار با LogN تا مقایسه انجام میشه . ولی فقط این نیست ...جستجوی دودویی کاربردای زیادی داره .
مثلا : فرض کنین یه معادله بهمون دادن ( که میدونیم نمودارش به صورت صعودی یا نزولی هستش ) و میگن به ازای چه مقدار n جواب این معادله برابر X میشه ؟ 2 حالت داریم یا میدونیم n تو چه بازه ای میتونه باشه که در این صورت با یه جستجوی دودیی تو اون بازه میتونیم جواب رو پیدا کنیم ، درصورتی هم که بازه ی مشخصی نداشته باشه بازم میشه با روشی کاملا مشابه جستجوی دودویی به مسئله جواب داد (چجوری ؟). و ...
متاسفانه کتاب فارسی تو اینترنت نتونستم پیدا کنم که همچین کاربردایی رو بگه ولی کتاب طراحی الگوریتم به روش خلاقانه رو اگه داشته باشین چند موردش رو نوشته . به هر حال میتونین از منابع زیر استفاده کنین :
سایت TopCoder (آموزشای این سایت خیلی خوب هستن )
روش حریصانه (Greedy) : بطور خلاصه ، انتخاب یک جواب در هر مرحله بدون توجه به انتخاب های قبل و بعد . معمولا اگه با این روش برای مسئله ای جواب پیدا کنین کد زدنش آسون هستش مثلا سوال Taxi مسابقه ی اول با این روش حل میشد. ... میتونین از منابع زیر استفاده کنین :
الگوریتمستان (فارسی) ، مثالای نمونه این سایت (فارسی)
