حسام حداد تکنولوژی، برنامه‌نویسی، هوش مصنوعی

الگوریتم حریصانه چیست؟
الگوریتم حریصانه یا آزمند الگوریتمی است که مبنای آن بر انتخاب عنصر یا مسیری که در هر مرحله بهترین به نظر میرسد بدون توجه به انتخاب های قبل یا بعد میباشد. قبل پیاده سازی این الگوریتم باید ابتدا اثبات کنیم که بهترین انتخاب در هر مرحله به طور کلی بهترین انتخاب میباشد در غیر این صورت به جواب نادرستی میرسیم برای مثال نمیتوانیم در مسئله کوتاه ترین فاصله بین دو گره در گراف از الگوریتم حریصانه استفاده کنیم .

کجا نمیتوان از الگوریتم حریصانه استفاده کرد؟

گراف بدون جهت زیر را در نظر بگیرید.

برای پیدا کردن کوتاه ترین مسیر بین گره A   و D اگر به صورت حریصانه عمل کنیم  یال A-C از یال A-B  دارای وزن کمتری میباشد پس یال A-C  را در نظر میگیریم ولی در ادامه مجبوریم از تنها انتخاب یعنی C-D استفاده کنیم و به گره  D برسیم. طول مسیر 9 + 15 یعنی 24 میباشد اما در صورتی که در ابتدا یال A-B را انتخاب کرده بودیم  با اینکه نسبت به A-C در مرحله اول انتخاب بدتری بود اما در ادامه مسیر بهینه تر و کوتاه تری را داشتیم.
پس نمیتوان از الگوریتم حریصانه در پیدا کردن کوتاه ترین میسر بین دو گره استفاده کرد برای اینکار میتوان از الگوریتم هایی مثل Dijkstra استفاده کرد که به این مقاله مربوط نمیشود.
اما باید بدانیم که اگر در مسئله ای الگوریتم حریصانه درست باشد بی شک بهترین راه حل برای آن مسئله حریصانه است چون نسبت به بقییه الگوریتم ها دارای پیچیده گی زمانی کمتری میباشد.
ما بنا بر روال همیشگی امروز یک مسئله ICPC – ACM را برای مثال انتخاب کرده ایم که در حل آن از الگوریتم حریصانه میتوان استفاده کرد.
ابتدا متن سوال را مرور میکنیم

سلام دوستان

امروز به جای حل و بررسی مسائل برنامه نویسی به معرفی منابع و شفاف سازی در زمینه الگوریتم نویسی میپردازیم

قالبا دوستانی که با تگ کلیدی "آموزش الگوریتم نویسی" وارد این تارنما ( بقول پاسداران زبان پارسی ) میشوند را میتوان به دو گروه تقیسم کرد.

گروه اول که به دنبال آموزش الگوریتم نویسی با پیاده سازی برخی الگوریتم ها هستند و یا دنبال اطلاعات دقیق در مورد یک الگوریتم خواص و مقایسه با الگوریتم های دیگر هستند.

گروه دوم که به دنبال اموزش Fllowchart فلوچارت یا pseudocode شبه کد به صورت پایه هستند.

سلام دوستان
امروز میخواهیم یک مبحث پر کاربرد در جاوا را توضیح دهیم Timer در برنامه نویسی کاربرد های بسیاری دارد از کاربرد در یک سیستم اندازه گیری زمان گرفته تا بروز رسانی زمان و تاریخ در یک برنامه تجاری.
کار با Timer در JSwing جاوا بنظر عجیب می آید چون مثل C# یا Visual Basic یک کنترل خاص به Timer اختصاص داده نشده است ( حداقل در Netbeans چنین کنترلی وجود ندارد)

سلام دوستان

قبلا یک سوال از مسابقه DM Contest ShareCode به اسم  حل مسئله کابل های در هم - Tangled in Cables Solotion را حل کرده بودیم در این مسابقه واقعا سوال های خوبی انتخاب شده بود و همه سوالها در واقع کاربرد یکی از الگوریتم ها بود.

خب سوال امروز مسئله نا مساوی هاست منبع اصلی سوال سایت ZOJ میباشد.

این سوال با دادن یک سری نامساوی از ما میخواهد که نامساوی های دیگری که نتیجه می دهد را پیدا کنیم . اشتباهی که زمان خواندن این سوال کردم باعث شد که برای چندین بار پشت سر هم Wrong Answer از سایت بگیرم . اما در آخر از دو روش مختلف از سایت ZOJ و Sharecode توانستم Accept بگیرم هر دو روش رو در ادامه به همراه کد توضیح میدهم ابتدا سوال را مطالعه کنید.

سلام دوستان سوالی که امروز براتون انتخاب کردم یه سوال از مسابقه DM Contest سایت Sharecode.ir هستش که چند هفته پیش برگذار شد منبع اصلیش   Mid-Atlantic 2004 هستش ... این مسئله خیلی وقت منو گرفت چون هربار سعی کردم جواب بهتری واسش ارائه بدم ... در آخر هم از سایت ShareCode.ir و سایت poj.org واسه این راه حل Accept گرفتم ولی سایت ICPC Live Archive به کد Wrong Answer داد .

خب ابتدا سوال رو مطالعه کنید

سلام دوستان ، همونطوری که تو نظرات خواسته بودن که سوالات ACM ICPC سایت شریف رو حل کنیم امروز به حل یک سوال نسبتا ساده مسابقه Tehran, Asia Region - Regional 2011 میپردازیم

لینک ShareCode.ir

خب قبل از ادامه حل سوال ابتدا سوال رو کامل مطالعه بفرمایید و سعی کنید خودتان حل کنید این سوال فقط نیازمند پیاده سازی است و نیاز به الگوریتم پیچیده خاصی ندارد توصیه من این است که حدافل نیم ساعت وقت برای حل این سوال بگذارید و بعد کد نمونه را چک کنید. 

سلام
امروز یک برخلاف روز های دیگه کد سوال ACM رو حل نمی کنیم من به یک مبحث جالب به اسم عدد های دوست توی نت برخوردم و کد پیدا کردن اش رو نوشتم گفتم شاید قرار دادنش روی وبلاگ خالی از لطف نباشه ...

البته این میتونست یک مسئله ACM هم باشه به این صورت که 2 تا عدد بگیره بگه با هم دوست هستند یا نه !!

عدد های دوست اعدادی هستند که جمع مقسوم علیه هاشون برابر با عدد دیگه بشه مثل 220 و 284

سلام
امروز یک مسئله خوب ACM به نام حل مسئله محیط تصاویر Image Perimeters Solotion را برای حل انتخاب کرده ایم این سوال را با استفاده از توابع بازگشتی حل کرده ایم.
این مسئله از مسابقه Mid-Central USA 2001 انتخاب شده است
لینک سوال در ICPC Live Archive
لینک سوال در ShareCode.ir

خب قبل اینکه ادامه مطلب را بخوانید ابتدا متن سوال را مطالعه فرماید و سعی کنید که خودتان حل کنید .

امروز میخواهیم یک مسئله سطح متوسط ACM را حل کنیم اینگونه سوال ها دارای یک نکته یا یک ابتکار کوچک میباشند که اگر آنرا متوجه شوید به راحتی میتوانید سوال را حل کنید.

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

حل بهتر مسئله کارتهای برابر

این سوال از مسابقه Southeast USA 2000 انتخاب شده است.

در مورد سوال را از سایت ShareCode.ir مسئله 1003 بخوانید.

خب قرار است یک شروع آزمایشی داشته باشیم به هیج وجه با دیدن این سوال راجب ACM قضاوت عجولانه نکنید!

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