مهمة بناء شجرة هوفمان الكسورية بشكل متكرر

Python Hard recursion

مهمة «مهمة بناء شجرة هوفمان الكسورية بشكل متكرر»

تم إعطاء سلسلة من أحرف الأبجدية اللاتينية (أحرف صغيرة). يجب بناء شجرة هوفمان الكسورية: لكل حرف، احسب تردده، ثم قم ببناء الشجرة بشكل متكرر، حيث تحتوي كل عقدة على مجموع ترددات الشجرة الفرعية اليسرى واليمنى، وتحتوي الأوراق على الأحرف. في كل خطوة من التكرار، يجب تقسيم قائمة الأحرف إلى جزأين بحيث يكون مجموع الترددات في الجزء الأيسر أقرب ما يمكن إلى مجموع الترددات في الجزء الأيمن (خوارزمية جشعة). قم بإرجاع سلسلة تمثل الشجرة بتدوين البادئة: للعقدة — 'F{sum}'، وللورقة — 'L{char}'. التكرار إلزامي.

تنسيق الإدخال

سطر واحد يتكون من أحرف لاتينية صغيرة (الطول من 1 إلى 100).

تنسيق الإخراج

<div>سلسلة — تمثيل شجري بالبادئة بدون مسافات.</div>

أمثلة

مثال 1

الإدخال

1
42

الإخراج

L1

مثال 2

الإدخال

nil nil nil

الإخراج

F11F6LnLiF5LlL 

مثال 3

الإدخال

abc

الإخراج

F3LaF2LbLc

مثال 4

الإدخال

0 1 2

الإخراج

F5F3L0L F2L1L2

main.py