دشواری: 5%

بیشترین جمع در مسیر ۲

با شروع از بالای مثلث زیر و حرکت به یکی از عددهای مجاور در ردیف پایین‌تر، بیشترین جمع عددها در این مسیر برابر ۲۳ می‌شود.

3
7 4
2 4 6
8 5 9 3

که برابر است با 3 + 7 + 4 + 9 = 23.

بیشترین جمع در مسیر را برای مثلث فایل triangle.txt پیدا کنید. (روی لینک راست‌کلیک کرده و گزینهٔ 'Save Link/Target As...' را انتخاب کنید.), یک فایل متنی ۱۵ کیلوبایتی حاوی مثلثی با ۱۰۰ ردیف

نکته: این یک نسخهٔ بسیار سخت‌تر مسئلهٔ ۱۸ است. بررسی همهٔ مسیرهای ممکن روی مثلث شدنی نیست چرا که 299 مسیر وجود دارد! اگر در هر ثانیه یک تریلیون (1012) مسیر را بررسی کنید، بررسی همهٔ آن‌ها ۲۰ میلیارد سال زمان خواهد برد! برای حل این مسئله الگوریتم بهینه‌ای وجود دارد. ;o)

ارسال پاسخ