تمرین ۲ الگوریتم
هدف از این تمرین، آشنایی با استراتژی تقسیم و حل (divide and conquer) می‌باشد. فرض کنید درخت نسبتا کاملی در اختیار دارید که در آن همه گره‌ها دارای وزن هستند (وزن هر گره یک عدد صحیح مثبت می‌باشد). طول یک مسیر در درخت برابر با مجموع وزن تمام گره‌های موجود بر روی مسیر (شامل گره مبدأ و مقصد) می‌باشد. عمق درخت هم برابر با طولانی‌ترین مسیر از گره ریشه تا هر یک از گره‌های برگ می‌باشد. می‌خواهیم برنامه‌ای بنویسیم که عمق یک درخت داده شده را بدست آورد و همینطور تمام مسیرهایی را که از مبدأ ریشه دارای طولی به اندازه عمق درخت هستند پرینت کند. برنامه باید به گونه‌ای نوشته شود که با کمترین تعداد دسترسی به وزن گره‌های درخت، خروجی حاصل شود (تعداد دسترسی به وزن گره‌ها هم باید پرینت شود).
برای مثال، درخت نمونه زیر را در نظر بگیرید:
برنامه باید برای درخت فوق، عمق ۱۲ را بدست آورد و مسیرهای <a,b,e> و همینطور <a,c,f> را به عنوان طولانی‌ترین مسیر از ریشه تا برگ معرفی نماید. تعداد حداقل دفعات دسترسی به وزن گره‌ها هم در این درخت نمونه برابر با ۸ خواهد بود.
ورودی برنامه یک درخت نسبتا کامل است (یعنی درختی که فقط آخرین سطح آن ممکن است کامل نباشد)، و به صورت آرایه‌ای از اعداد پشت سرهم در یک فایل متنی آورده شده است که این اعداد با فاصله از هم جدا شده‌اند (هر عدد در این فایل بیانگر وزن یک گره می‌باشد. در ضمن، فرزندان گره i در موقعیت 2*i و 2*i+1 قرار دارند). برای مثال، سطر زیر بیانگر درخت نمونه فوق می‌باشد:
6 2 1 2 4 5 3 1