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

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

سی‌پلاس‌پلاس

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

  

کتاب Competetive Programming

ویراست سوم کتاب برنامه‌نویسی رقابتی با نام کامل Competitive Programming 3: The New Lower Bound of Programming Contests با تلاش Steven Halim و Felix Halim از مربیان تیم‌های برنامه‌نویسی ACM-ICPC سنگاپور تالیف و در سال ۲۰۱۳ منتشر شده است که امروزه به عنوان یکی از منابع مناسب برای آمادگی تیم‌های شرکت‌کننده در مسابقات برنامه‌نویسی الگوریتمی بویژه مسابقات برنامه‌نویسی ACM-ICPC توصیه می‌شود.

نکته‌ای در مورد کلاس‌ها و مجموعه‌ها در ++C

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

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

sync_with_stdio در زبان ++C

زبان برنامه‌نویسی ++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 مدت زمان اجرای قطعه کد را به دست آورد.

هدر فایل bits/stdc++.h

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

نکته‌ای از مسأله‌ Graphical Editor

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

تابع popen در زبان ++C

گاهی لازم است یک برنامه خارجی را از برنامه خودمان اجرا و خروجی آن را استفاده کنیم. این برنامه می‌تواند یک برنامه اجرایی دیگر یا یکی از ابزارهای سیستم عامل مانند ping یا حتی اجرای یک برنامه java باشد. آنچه که مهم است اجرا شدن از خط فرمان و تولید خروجی متنی است.

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

ظرف‌ها در ++C

منظور از ظرف یا نگهدارنده (Container) ساختمان داده‌ای‌ست که دسته‌ای از اطلاعات را در خود نگه می‌دارد. آنچه که این ساختمان‌ها را از هم متمایز می‌کند، نوع تخصیص حافظه، نوع دسترسی و کارایی درج و حذف عنصر در آنها است که به برخی از آنها کاربری‌های ویژه می‌دهد.

در ادامه با انواع این نوع ساختمان داده‌ها در زبان برنامه‌نویسی ++C نسخه C++11 آشنا می‌شویم. با توجه به گسترده بودن این بحث، جزئیات بیشتر هر کلاس را در «پیوندها برای مطالعه بیشتر» بخوانید.

نکته‌ای در استفاده از map

ساختمان داده map (یا dictionary) از ابزارهای مهم و کاربردی هر زبان برنامه‌نویسی است که برای برقراری نگاشت بین هر نوع کلید و مقدار متناظر استفاده می‌شود. آرایه‌های معمولی یک عدد صحیح را به عنوان کلید به یک مقدار از هر نوع کلاس یا نوع داده نگاشت می‌کنند. اما وقتی از map استفاده می‌کنیم، این امکان را داریم که از اشیاء کلاس‌ها و انواع داده‌های پیش‌فرض هر زبان برنامه‌نویسی به عنوان کلید استفاده کنیم. در نتیجه پیاده‌سازی بسیاری از عملیات‌ها ساده‌تر می‌شود که کمک بزرگی به حساب می‌آید.

فایل سرآیند algorithm

فایل سرآیند (هدر فایل) algorithm از جمله فایل‌های سرآیند تعاریف کتابخانه‌ قالب استاندارد (STL) زبان برنامه‌نویسی ++C‌ است که به طور عمده شامل توابعی برای کار با مجموعه‌ای از داده‌ها (آرایه‌ها و لیست‌ها) است. با استفاده از این توابع به راحتی می‌توان با تنها یک خط کد عملیات جستجو، مرتب‌سازی، شمارش و بررسی یک خاصیت در تمامی داده‌های یک بازه مشخص را انجام داد.

نکات مهم در برنامه‌نویسی به زبان ++C

اجتناب از بررسی تساوی در اعداد اعشاری

اعداد اعشاری در محاسبات ریاضی - مانند عمل تقسیم یا محاسبه توابع مثلثاتی و غیره - ممکن است حاوی مقدار بسیار ناچیزی خطا باشند که عموما ناشی از عملیات گرد کردن و قطع کردن نتایج مراحل میانی محاسبات هستند. در چنین حالتی به کار بردن عملگر تساوی لزوما به نتیجه درست ختم نمی‌شود. به عنوان مثال:

الگوریتم مرتب‌سازی حبابی

یکی از روش‌های مرتب‌سازی، روش مرتب‌سازی حبابی (Bubble Sort) است که به آن روش تعویض استاندارد (Standard Exchange) نیز می‌گویند. این روش شامل چند مرحله است که در هر مرحله یک عنصر از لیست به طور قطع در محل مناسب خود قرار می‌گیرد.

لیست زیر را در نظر بگیرید که می‌خواهیم به صورت صعودی (از کوچک به بزرگ) مرتب کنیم:

توابع دوست کلاس در ++C

توابع دوست کلاس‌ها از‌ جمله موارد بحث برانگیز برنامه‌نویسی شی‌ءگرا به زبان ++C هستند. چرا که یکی از اصول اساسی شیءگرایی، یعنی پنهان‌سازی اطلاعات، را نقض می‌کنند. با این وجود به خاطر کاربردهای متعددی که دارند از حضورشان نمی‌توان چشم‌پوشی کرد.

به زبان ساده، توابع دوست یک کلاس توابعی هستند که عضو کلاس نیستند، اما به تمامی داده‌ها و توابع خصوصی و محافظت شده آن دسترسی دارند.

سربارگذاری عملگرها در ++C

همانطور که می‌دانید، شیوه معرفی اشیاء کلاس‌های تعریف شده در ++C همانند متغیرهای عادی هستند. به عنوان مثال اگر کلاسی به نام myclass تعریف کرده باشیم، عبارت زیر یک شیء از این کلاس به نام a تعریف می‌کند:

  

متغیرهای مرجع در ++C

زبان برنامه‌نویسی C از دو نوع متغیر پشتیبانی می‌کند: متغیرهای معمولی و اشاره‌گرها (متغیرهای حاوی آدرس حافظه). زبان ++C نوع سومی را به این مجموعه اضافه کرده است: متغیرهای مرجع (Reference).

متغیرهای مرجع از روی دو نوع دیگر ساخته می‌شود و به نوعی می‌توان گفت نام مستعار برای متغیر اصلی به حساب می‌آید. برای تعریف متغیر مرجع از عملگر & استفاده می‌کنیم:

کلاس‌های حافظه در ++C

زبان برنامه‌نویسی ++C از کلاس‌های حافظه‌ (Storage Classes) مختلفی برای تعریف متغیرها پشتیبانی می‌کند.

  

کلاس حافظه اتوماتیک (auto)

این کلاس اصلی‌ترین کلاس حافظه زبان ++C محسوب می‌شود. متغیرهایی که توسط این کلاس تعریف می‌شوند، با خروج از محدوده تعریف به طور خودکار از بین می‌روند. بنابراین تمامی متغیرهای عادی از این نوع کلاس هستند. یعنی شما برای مشخص کردن کلاس حافظه اتوماتیک نیاز به انجام کار خاصی ندارید. اما برای تاکید بر اتوماتیک بودن کلاس حافظه، می‌توانید از کلمه کلیدی auto استفاده کنید. به عنوان نمونه، دو عبارت زیر هم ارز هستند:

آرایه پویای دو بعدی در ++C

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

اشاره‌گرها در زبان ++C

یکی از مهمترین مباحث کاربردی هر زبان برنامه‌نویسی، اشاره‌گر و مفهوم آن است که کاربرد گسترده‌ای در شاخه ساختمان داده‌ها نیز دارد. در این فرصت با مفهوم اشاره‌گر و همینطور روش تعریف آن در زبان ++C آشنا می‌شوید. باید توجه داشته باشید که سوای روش تعریف اشاره‌گر در این زبان، کلیت مفهوم آن در بین تمام زبان‌ها مشترک است.

قالب‌ها در ++C

یکی از امکانات جالب و مفید زبان ++C قالب‌ها (Templates) هستند که انعطاف زیادی به کدنویسی می‌دهند.

فرض کنید در یک برنامه نیاز به تعویض مقادیر دو متغیر هست. یعنی مثلا می‌خواهیم مقادیر a و b را با هم عوض کنیم. اگر a و b از نوع صحیح باشند، تابع جابجایی می‌تواند به این صورت باشد:

آرایه ایستا و پویا در ++C

زبان ++C همانند اکثر زبان‌های برنامه‌نویسی دیگر، ساختاری به نام آرایه دارد که امکان تعریف مجموعه‌ای از متغیرهای هم‌نوع (اصطلاحا مجموعه عناصر همگن) را فراهم می‌کند. چنین ساختاری به صورت زیر تعریف می‌شود:

  

حلقه‌های تکرار در ++C

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

هر زبانی عموما شامل چندین نوع حلقه تکرار است که هر کدام به نحوی به برنامه‌نویس در نوشتن کدهای مختصر و با مفهوم کمک می‌کنند. در این فرصت با انواع حلقه‌های تکرار در زبان برنامه‌نویسی ++C آشنا می‌شویم.