נתונה סידרה
של מספרים גדולים או שווים ל1. תת-סידרה
של X נקראת חברותית אם היא מכילה לפחות שני איברים עוקבים של X, ובדלנית אם היא איננה חברותית.
דוגמה:
נניח ש . אז:
היא תת-סידרה חברותית.
היא תת-סידרה בדלנית.
היא תת-סידרה חברותית.
היא תת-סידרה בדלנית.
היא תת-סידרה בדלנית.
|
אנא כתוב אלגוריתם אשר מקבל סידרה
ומדפיס תת-סידרה בדלנית שמכפלת איבריה גדולה ככל האפשר. (הנח שמכפלת איברי תת-סידרה ריקה היא 1.) קבע את Length(X)
כ
, ונתח את סיבוכיות האלגוריתם במונחי
.
דוגמה:
נניח שהאלגוריתם מקבל כקלט את . במקרה זה, עליו להדפיס : זו תת-סידרה בדלנית של , , ואין תת-סידרה בדלנית אחרת שמכפלת איבריה גדולה מ35.
|