מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/הדפסה יפה/שאלה

ברצוננו להדפיס פסקת טקסט בצורה יפה.

נתונות לנו $\displaystyle n$ מילים, Word[1], Word[2], ..., Word[n]. עלינו להחליט היכן לסיים כל שורה בפסקה, לפי הכללים הבאים:

1. בכל שורת טקסט יש מקום ל$\displaystyle M$ תווים (אין מילה בעלת יותר מ$\displaystyle M$ תווים).
2. יש להדפיס רווח יחיד בין כל שתי מילים באותה שורה.

דוגמה: נניח ש$\displaystyle M=20$, והמילים הן If they have no rice, let them eat ladoo. נוכל לבנות פסקה כך: If they have no rice, let them eat ladoo. אך לא כך: If they have no rice, let them eat ladoo. (בדוגמה השניה יש יותר מ20 תווים בשורה הראשונה).

אם בשורה יש $\displaystyle m'$ תווים (כולל הרווחים בין המילים), אז יופי השורה הוא $\displaystyle {\frac {1}{(M-m'+1)^{2}}}$. יופי הפסקה מוגדר כסכום היופי של השורות שלו, למעט השורה האחרונה.

דוגמה: בפסקה If they have no rice, let them eat ladoo. יש 15 תווים בשורה הראשונה, ו14 תווים בשורה השניה. יופי הפסקה, לכן הוא $\displaystyle {\frac {1}{(20-15+1)^{2}}}+{\frac {1}{(20-14+1)^{2}}}={\frac {1}{6^{2}}}+{\frac {1}{7^{2}}}$.

אנא מצא אלגוריתם יעיל למציאת הפסקה היפה ביותר. הנח ש$\displaystyle n$ הוא משתנה גלובלי נתון, ושקיימת פונקציה Length המקבלת מספר $\displaystyle i$ ומחזירה את מספר התווים במילה ה$\displaystyle i$.