المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۹:عملی:سوال ۸

بازیافت درخت

یک درخت ریشه‌دار را می‌توان بدین روش با یک عدد نمایش داد که در ابتدا رشته‌ی ‘0’ را در نظر گرفته و با الگوریتم DFS درخت را پیمایش می‌کنیم، هنگام ورود به هر راس یک ‘0’ و هنگام خروج از آن یک ‘1’ به انتهای رشته اضافه می‌کنیم تا در انتها، رشته‌ی حاوی نمایش مبنای ۲ی عدد مورد نظر به‌دست آید. برای مثال از درخت شکل مربوط به مثال، رشته‌ی ‘000010110011011’ معادل عدد ۱۴۳۵ به‌دست می‌آید.

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

ورودي

در خط نخست فایل ورودی عدد مربوط به درخت آمده است.

خروجي

در خروجی نیمه‌ی پایین ماتریس مجاورت را بنویسید. لازم است ترتیب رئوس را ترتیب وارد شدن به رئوس در DFS در نظر بگیرید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
1435 1
0 1
0 1 0
1 0 0 0
0 0 0 0 1
1 0 0 0 0 0

ابزار صفحه