Amir (guest) 26 Jun 2018 14:29
שאלה 5:
ב"בעיית הקטעים התואמים" הקלט הוא וקטור מעל {0,1} באורך n. הפלט הוא קבוצה חוקית של קטעים תואמים:
1. קטע (i,j) הוא תואם אם i<j והספרה הראשונה והספרה האחרונה שלו שוות
2. קבוצת קטעים היא חוקית אם כל קצות הקטעים שלה שונים זה מזה וכל זוג קטעים הוא או מוכל ממש או זר ממש.
תארו אלגוריתם יעיל ככל האפשר המחשב קבוצה חוקית של קטעים תואמים שגודלה מקסימלי.
אשמח לדעת האם הפתרון הבא עובד (אני מניח שלא, כי הוא בסיבוכיות n^2 ופתרון אחר שראיתי שקיבל את מלוא הנקודות היה בסיבוכיות n^3):
C(i,j) - הגודל המקסימלי של קבוצה חוקית בתת הוקטור ai…aj
החישוב של בעיה על ידי תתי בעיות:
אם ai = aj אז C(i,j) = 1 + C(i+1,j-1).
אחרת C(i,j) = max{C(i,j-1), C(i+1,j)}
המבוקש הוא C(1,n)
האתחול הוא C(i,i) = 0 לכל i, וגם C(i,j) = 0 לכל i>j.
את החישוב מבצעים בסדר גדל של אינטרוולים (כלומר קודם C(1,2), C(2,3)… ואז C(1,3), C(2,4) וכן הלאה)
יש לי n^2 תתי בעיות וכל אחת מחושבת בזמן קבוע.
אשמח להבין מה שגוי בפתרון,
תודה!