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

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب وبلاگ نوشته‌ها با برچسب وبلاگ - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

وبلاگ

»

فرض کنید صفحه‌ی ۵ در ۵ از کلید شاسی‌های چراغ‌دار داریم و این کلیدها به نحوی به هم متصل هستن که وقتی کلیدی رو فشار می‌دیم، نه تنها وضعیت چراغ همون کلید که وضعیت چراغ چهار کلید بالا، پایین، راست و چپ هم (در صورت وجود) عوض می‌شه؛ یعنی اگر چراغ روشن باشه، خاموش می‌شه و بالعکس. بازی Lights Out (یا Lights Off) روی چنین صفحه‌ای انجام می‌شه و به این ترتیب هست که اگر یک سری از چراغ‌ها در ابتدای کار روشن باشن، چطور می‌تونیم با فشار دادن کلیدها همه‌ی چراغ‌ها رو خاموش کنیم.

پیوند نوشت ۱: شما می‌تونید Lights Out رو اینجا به صورت آنلاین بازی کنید.

ادامه ...

زبان برنامه‌نویسی ++C دو کلاس set و unordered_set رو برای پیاده‌سازی مفهوم مجموعه (ظرفی با عناصر غیرتکراری) داره.

کلاس set علاوه بر بررسی تکراری نبودن عناصر، اونها رو به صورت مرتب ذخیره می‌کنه. پس اگر بخوایم برای نگه داشتن عناصری از کلاس دلخواه خودمون از set استفاده کنیم، باید حداقل عملگر > رو سربارگذاری کرده باشیم تا ظرف set قابلیت تشخیص ترتیب عناصر رو داشته باشه. اما گاهی تعریف کوچکتر بودن برای کلاسمون مقدور نیست یا از لحاظ مفهومی معنی نداره. در چنین شرایطی می‌تونیم از کلاس unordered_set استفاده کنیم.

ادامه ...

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

برای حل سوال می‌شه از هر الگوریتم مسیریابی کمینه استفاده کرد. اما الگوریتم فلوید-وارشال کارایی بهتری داره. چون در عین ساده‌گی پیاده‌سازی، ماتریس نهایی کمترین هزینه برای سفر بین هر دو شهر دلخواه رو شامل می‌شه و کافی‌ه بیشتر مقدار در اون ماتریس رو به عنوان خروجی چاپ کنیم.

ادامه ...

زبان برنامه‌نویسی ++C علاوه بر ابزارهایی مثل cin و cout برای عملیات I/O، توابعی مثل scanf و printf رو هم برای همین کارها از زبان برنامه‌نویسی C به ارث برده. هر کدوم از این دو دسته مزایایی دارن که ممکنه بخوایم از هر دو در برنامه‌نویسی استفاده کنیم. مثلا printf فرمت‌بندی خروجی راحت‌تری نسبت به cout داره. اما برای کاربری‌های عادی استفاده از cout پیچیده‌گی کمتری داره.

ادامه ...

برای محاسبه‌ی زمان اجرای کد در ++C می‌شه از دو تابع clock یا time استفاده کرد. تابع clock، تعداد کلاک‌های در اختیار برنامه از CPU تا اون لحظه رو برمی‌گردونه که با تقسیم بر CLOCKS_PER_SEC به ثانیه تبدیل می‌شه. تابع time، زمان سیستم رو بر حسب ثانیه برمی‌گردونه. پس می‌شه از اختلاف دو clock و تقسیم اون بر CLOCKS_PER_SEC یا اختلاف دو time مدت زمان اجرای قطعه کد رو به دست آورد.

ادامه ...

وب‌سایت Virtual Judge این امکان رو فراهم می‌کنه که با ترکیب دلخواهی از سوالات وب‌سایت‌های مخزن سوالات برنامه‌نویسی مثل UVA، Codeforces و خود سوالات ACM-ICPC، مسابقه‌ی مجازی برگزار کرد. از این حیث برای تمرین تیم‌های مسابقات ACM-ICPC بسیار مناسب و کاراست.

ادامه ...

زمان مسابقه تایپ اسم تک تک هدرفایل‌های مورد نیاز برای اجرای برنامه زمان می‌بره. گاهی تابع یا کلاس جدیدی استفاده می‌کنیم که باید یه بار دیگه برگردیم بالای کد و هدرفایل رو ضمیمه کنیم. از یه سمت هم گاهی مطمئن نیستیم باید کدوم فایل اضافه شه.

هدر فایل bits/stdc++.h این زحمت رو کم می‌کنه. زمانی که این هدر رو include می‌کنیم، تمام فایل‌های سرآیند استاندارد به برنامه اضافه می‌شن و اصولا دیگه نیازی نیست چیزی رو اضافه کنیم. ممکنه به نظر بیاد این اضافه شدن دسته‌جمعی سربار زیادی داشته باشه. اما باید در نظر داشت که حتی اگه اینطور باشه، برای ما زمان اجرا مهم هست و نه زمان کامپایل برنامه.

ادامه ...

برای حل سوال Graphical Editor باید هر خط از ورودی بررسی و اگه دستور معتبر بود اجرا شه. تا اینجا مشکل خاصی نیست. اما اگه دستور نامعتبر بود، باید کل خط نادیده گرفته شه. مشکل اینجاست که مشخص نیست چه داده‌هایی و به چه تعداد در اون خط وجود دارن. پس چاره‌ای نیست جز اینکه برای هر ورودی کل خط یکجا خونده شه و بعد از بررسی معتبر بودن دستور، تصمیم گرفته شه که بقیه‌ی داده‌های روی خط خونده شن یا نه.

اینجاست که stringstream به کار می‌یاد و می‌تونه به ما کمک کنه خط رشته‌ای ورودی رو در صورت نیاز خیلی ساده به عدد تبدیل کنیم یا از پردازش خط صرف‌نظر کنیم.

ادامه ...

وب‌سایت UVA Toolkit این امکان رو فراهم می‌کنه که برای سوالات وب‌سایت UVA Online Judge ورودی مد نظرمون رو بدیم و خروجی متناظرش رو ببینیم. به این ترتیب هم می‌تونیم ابهام در نحوه‌ی تولید خروجی رو رفع کنیم و هم زمان برای تولید دستی خروجی نذاریم.

در ضمن برای هر سوال موضوع یا روش حل سوال راهنمایی شده.

ادامه ...

زمانی که ورودی مسأله از نوع عددی هست (حالا صحیح یا اعشاری) لزومی نداره داخل متغیر عددی ذخیره کنیم. گاهی ممکنه ذخیره‌ی اون به صورت رشته بهتر باشه. مثلا برای مسأله‌ی LC-Display باید عدد رو از چپ به راست و رقم به رقم پردازش کنیم. پس چه بهتر که به صورت رشته یا آرایه‌ای از کاراکترها ذخیره شه.

ادامه ...