ماهواره

دستورالعمل‌ها

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

نرم‌افزاری برای ماهواره بنویسید تا درخت را از روی این پیمایش‌ها بازسازی کند.

در پیمایش پیش‌ترتیب، مقدار گره‌ی جاری پیش از خواندن زیردرخت چپ به‌صورت پیش‌ترتیب خوانده می‌شود (به همین دلیل «پیش»). پس از آن، زیردرخت راست به‌صورت پیش‌ترتیب خوانده می‌شود.

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

برای نمونه، پیمایش پیش‌ترتیب این درخت [a, i, x, f, r] است. پیمایش میان‌ترتیب این درخت [i, a, f, x, r] است.

  a
 / \
i   x
   / \
  f   r

نکته: اولین عنصر در پیمایش پیش‌ترتیب همیشه ریشه است.

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

کتابخانه

فایل‌های پیاده‌سازی اولیه شامل خط زیر است:

:- use_module(library(dcg/basics)).

این خط تضمین می‌کند که می‌توان از کتابخانه‌ی dcg/basics استفاده کرد، و همین باید برای حل این تمرین کافی باشد.

منابع

منابع زیر برای شروع کار با DCG در Prolog مفیدند:

• metalevel.at
• wikipedia
• swipl