المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:برنامه نویسی:سوال ۶

سوال ۶

پس از پیاده‌سازی الگوریتم ‎BFS‎ و پیداکردن مقدار فاصله کوتاه‌ترین مسیر از رأس صفر به تمام رأس‌ها، می‌خواهیم خودِ مسیر را نیز چاپ کنیم. برای این منظور از شما خواسته شده که تابع void PrintPathTo(int v)‎ را یک‌بار به‌صورت بازگشتی و یک‌بار به‌صورت غیربازگشتی بنویسید.

این تابع قرارست با استفاده از محتوای آرایه‌ی int parent[MAX_N[ (که در آن پدر هر رأس نگه‌داری می‌شود) کوتاه‌ترین مسیر از رأس شروع (که همواره رأس صفر است) تا رأس ‎v‎ را چاپ کند. برای مثال اگر محتوای آرایه‌ی ‎parent‎ برای اعضای صفر تا ‎5‎ به‌ترتیب (از چپ به راست) ‎0‎, ‎3‎, ‎0‎, ‎0‎, ‎1‎, ‎9‎ باشد، آن‌گاه با فراخوانی تابع به‌صورت ‎PrintPathTo(4)‎ می‌بایست در خروجی ‎(cout)‎ نوشته شود ‎0 3 1 4.

  1. تابع void PrintPathTo(int v)‎ را به‌صورت بازگشتی بنویسید.‎ شما مجاز نیستید در این تابع متغیر جدید تعریف کنید یا از ‎{‎ اضافه استفاده کنید. در بدنه‌ی تابع شما باید حداکثر دو ;‎ یا ‎,‎ استفاده شده باشد.
  2. تابع ‎void PrintPathTo(int v)‎ را به‌صورت غیربازگشتی بنویسید. فرض کنید برای این‌کار به‌ شما یک vector<int> vec;‎ که به‌صورت ‎global‎ تعریف شده، داده شده است. شما به‌هیچ‌وجه مجاز نیستید در این تابع متغیر دیگری تعریف کنید.
  3. یک مورد از مزایای تابع بازگشتی برای حل این مسئله و یک مورد از مزایای تابع غیربازگشتی برای حل این مسئله را ذکر کنید.

ابزار صفحه