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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

המבנה הרקורסיבי[עריכה]

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



משפט:

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

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



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

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

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

מש"ל.PNG

מימוש רקורסיבי נאיבי[עריכה]

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

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) בהנחה שכל קריאה רקורסיבית היא (ראו הניתוח בדג הסלמון).
  • מהתבוננות, קל לראות שהדפסת האיברים היא .