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

המבנה הרקורסיבי

עריכה

נגדיר כ  את המכפלה הגדולה ביותר האפשרית של תת-סידרה בדלנית של   (שים לב שתת-הסדרה אינה בהרכח משתמשת ב ).



משפט:

  מקיימת את נוסחת הנסיגה הבאה:

  1. אם  , אז  .
  2. אם  , אז  .
  3. אם  , אז  .



הוכחה: נשים לב לנקודות הבאות:

  1. אם  , אז בוודאי שנבחר באיבר הראשון (כל איבר הוא לפחות 1); נקבל בהכרח  .
  2. אם  , אז בוודאי שנבחר באיבר הראשון או באיבר השני (כל איבר הוא לפחות 1); נקבל בהכרח  .
  3. אם  , אז או שנבחר ב  או שלא (אלו שתי האפשרויות היחידות).
    • אם נבחר ב , אז לא נוכל לבחור ב ; במקרה זה נרצה להכפיל את   בתוצאה הטובה ביותר האפשרית עד  , שהיא  .
    • אם לא נבחר את  , אז נרצה את תת-הסדרה הטובה ביותר עד  , שהיא, עפ"י ההגדרה,  .

בנקודה השלישית, היות שאיננו יודעים אם כדאי לבחור את האיבר ב  או לא - ניקח את המקסימום משתי האפשרויות.

 

מימוש רקורסיבי נאיבי

עריכה

להלן פסוודו-קוד המממש רעיון זה:

Max-Product(i)
1	if i == 1
2		return X[1]

3	if i == 2
4		return max(X[1], X[2])

6	guess-with = Max-Product(i - 2) * X[i]
7	guess-without = Max-Product(i - 1)
		
8	if guess-with > guess-without
9		return guess-with
10	else
11		return guess-without

קל לראות שסיבוכיות האלגוריתם גבוהה מדי. היא נתונה ע"י הפתרון לנוסחה   (כלומר אקספוננציאלית, מפני שזו סדרת Fibonacci), וסיבתה היא הסיבה הקבועה: פתירת אותן תת-בעיות שוב ושוב.

שימוש בmemoization

עריכה

להלן פסוודו-קוד יעיל יותר:

1	L = Make-Array(n)

2	for i in [1, ..., n]
3		L[i] = Nil


Max-Product(i)
1	if L[i] != Nil
2		return L[i]

3	if i == 1
4		L[1] = X[1]
5		return L[1]

6	if i == 2
7		L[2] = max(X[1], X[2])
8		return L[2]

9	guess-with = Max-Product(i - 2) * X[i]
10	guess-without = Max-Product(i - 1)
		
11	if guess-with > guess-without
12		L[i] = guess-with
12		return L[i]
13	else
14		L[i] = guess-without
15		return L[i]

הדפסת האיברים

עריכה

להלן פסוודו-קוד המאפשר גם הדפסת תת-הסדרה:

1	L = Make-Array(n)
2	U = Make-Array(n)

3	for i in [1, ..., n]
4		L[i] = Nil


Max-Product(i)
1	if L[i] != Nil
2		return L[i]

3	if i == 1
4		L[1] = X[1]
5		U[1] = True
6		return L[1]

7	if i == 2
8		L[2] = max(X[1], X[2])
9		U[2] = X[2] == L[2]? True : False
10		return L[2]

11	guess-with = Max-Product(i - 2) * X[i]
12	guess-without = Max-Product(i - 1)
		
13	if guess-with > guess-without
14		L[i] = guess-with
15		U[i] = True
16		return L[i]
17	else
18		L[i] = guess-without
19		U[i] = False
20		return L[i]

המערך U מחזיק בכניסה ה  את ההכרעה האם תת-הסדרה הטובה ביותר עד   אכן משתמשת באיבר ה  או לא. קטע הקוד הבא מראה כיצד להדפיס את האינדקסים של תת-הסידרה הטובה ביותר המסתיימת ב .

Print-Seq(i)
1	if U[i] == True
2		Print-Seq(i - 2)
3		Print(i)
4		return
	
5	Print-Seq(i - 1)

כיצד נשתמש בקוד, אם כן?

  1. נאתחל המשתנים הגלובליים, ונקרא לMax-Product(n).
  2. נקרא לPrint-Seq(n).


ניתוח סיבוכיות

עריכה

הסיבוכיות הכוללת הנה לינארית:

  • מהתבוננות, ברור שהאתחול לינארי.
  • הסיבוכיות של Max-Product(n) נתון על ידי  , כאשר   הוא זמן הריצה של Max-Product(i) בהנחה שכל קריאה רקורסיבית היא   (ראו הניתוח בדג הסלמון).
  • מהתבוננות, קל לראות שהדפסת האיברים היא  .