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

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

נתונות לנו <math dir = "ltr">\displaystyle	n</math> מילים, {{קוד בשורה|Word[1], Word[2], ..., Word[n]}}. עלינו להחליט היכן לסיים כל שורה בפסקה, לפי הכללים הבאים:
#בכל שורת טקסט יש מקום ל<math dir = "ltr">\displaystyle	M</math> תווים (אין מילה בעלת יותר מ<math dir = "ltr">\displaystyle	M</math> תווים).
#יש להדפיס רווח יחיד בין כל שתי מילים באותה שורה.

{{דוגמה|תוכן=
נניח ש<math dir = "ltr">\displaystyle	M = 20</math>, והמילים הן

<p dir = "ltr">
If they have no rice, let them eat ladoo.
</p>

נוכל לבנות פסקה כך:
<p dir = "ltr">
If they have no
</p>
<p dir = "ltr">
rice, let them 
</p>
<p dir = "ltr">
eat ladoo.
</p>

אך לא כך:
<p dir = "ltr">
If they have no rice, let them eat 
</p>
<p dir = "ltr">
ladoo.
</p>
(בדוגמה השניה יש יותר מ20 תווים בשורה הראשונה).

}}

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

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

}}

אנא מצא אלגוריתם יעיל למציאת הפסקה היפה ביותר. 
הנח ש<math dir = "ltr">\displaystyle	n</math> הוא משתנה גלובלי נתון, ושקיימת פונקציה {{קוד בשורה|Length}} המקבלת מספר <math dir = "ltr">\displaystyle	i</math> ומחזירה את מספר התווים במילה ה<math dir = "ltr">\displaystyle	i</math>.