ابزار کاربر

ابزار سایت


الگوریتم:خطاها_و_راه_کارهای_حل_آنها

خطاها

خطاهای یک برنامه به صورت زیر هستند:

  • جواب نادرست
  • زمان غیرمجاز
  • حافظه غیرمجاز
  • بازنمایی نادرست: جواب درست است اما درست نمایش داده نشده است.
  • خطای کامپایل: قبل از فرستادن همیشه برنامه خود را اجرا کنید تا خطاهای دستوری نداشته باشد.

بهبود زمان اجرای الگوریتم

برای بهتر کردن زمان برنامه‌ای که تفاوت زیادی با زمان مجاز ندارد، روش‌های زیر را به کار ببرید:

  • ساختن جوابهای مجاز به جای حذف جوابهای غیرمجاز
  • زودتر هرس کردن جوابهای غیرمجاز در جستجوی کامل
  • عدددهی مقادیر اولیه به جای محاسبه‌ی آنها در مسایلی که حجم مقادیر کم اما زمان محاسبه‌ی آنها زیاد است. این اعداد را می‌توانید با برنامه‌ی دیگری محاسبه کنید و لازم نیست با دست حساب کنید.
  • مسأله را از آخر به اول حل کنید و آن را حل شده فرض کنید. شاید با این کار راه حل ساده‌تری به ذهنتان برسد.
  • برنامه خود را سریعتر بنویسید. مثلاً متغیرهایی که مقدار آنها تغییر نمی‌کند و حجم زیادی دارند به توابع نفرستید. از توابع سریعتری استفاده کنید.
  • داده‌ساختارها و الگوریتم‌های بهتری به کار ببرید.
  • از تقارن استفاده کنید.

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

با محاسبه‌ی زمان الگوریتمی که می‌خواهید آن را پیاده‌سازی کنید، می‌توانید بفهمید که در زمان مجاز اجرا می‌شود یا خیر. معمولاً قضیه اساسی تحلیل الگوریتم‌ها، رابطه‌ی بازگشتی زمان برنامه را حل می‌کند. فرض کنید زمان برنامه با رابطه بازگشتی زیر نشان داده شده باشد: \[ T(n) = a.T(n/b)+O(f(n)) \] ابتدا مقدار $g(n) = n^{\log_b a}$ را محاسبه می‌کنیم. اگر تابع $f(n)$ از نظر مرتبه از $g(n)$ بزرگتر بود، زمان الگوریتم $T(n) = f(n)$ خواهد بود. اگر تابع $g(n)$ از نظر مرتبه از تابع $f(n)$ بزرگتر بود، زمان الگوریتم $T(n) = g(n)$ خواهد بود. در غیر این صورت از نظر مرتبه با هم برابر هستند و الگوریتم از مرتبه $T(n) = f(n) O(\log n) = g(n) O(\log n)$ خواهد بود.

حافظه مجاز

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

نمایش درست

یکی از موارد مهم در این قسمت دقت اعداد و نحوه‌ی نمایش آنها است. در زبان c++ کتابخانه‌ی iomanip برای تغییرات روی ورودی و خروجی به کار می‌رود. از این کتابخانه برای نمایش اعداد با دقت دلخواه، تبدیل بین فرم‌های اعشاری و نمایش علمی، اندازه‌ی ستون‌ها و … استفاده می‌شود.

جزئیات کتابخانه استاندارد و مثال برای استفاده از این توابع

از توابع کاربردی دیگر می‌توان به stringstream اشاره کرد که به جای ورودی از روی رشته‌ای که خودتان تعیین می‌کنید ورودی را می‌خواند و می‌توانید از عملگرهای ورودی و خروجی هم روی آن استفاده کنید.

جزئیات جریان ورودی و خروجی رشته‌ای

مثالی از استفاده از جریان رشته‌ای

الگوریتم/خطاها_و_راه_کارهای_حل_آنها.txt · آخرین ویرایش: 2014/12/21 08:18 (ویرایش خارجی)