מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תת-סידרה בדלנית מקסימאלית כפלית/שאלה
קפיצה לניווט
קפיצה לחיפוש
נתונה סידרה של מספרים גדולים או שווים ל1. תת-סידרה של X נקראת חברותית אם היא מכילה לפחות שני איברים עוקבים של X, ובדלנית אם היא איננה חברותית.
![{\displaystyle \displaystyle X=[x_{1},...,x_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1393f28b6aad4aa2a6b3695ff1b9eb4d33ad9399)
|
דוגמה: נניח ש. אז:
|
![{\displaystyle \displaystyle X=[1,5,2,7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31eacea69cdcd10431db5e78db0b76159209b522)
![{\displaystyle \displaystyle X'=[1,5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eda3134a09214d711b371712195ff1ae6d37f076)
![{\displaystyle \displaystyle X'=[1,7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/febc685fc591bfc0a3612e87814424f72272e094)
![{\displaystyle \displaystyle X'=[1,5,7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5393fd956763e6c64706175a876fa77d8486ff4d)
![{\displaystyle \displaystyle X'=[1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5995edead45004a581cec517d9560a9131cccd73)
![{\displaystyle \displaystyle X'=[]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ea29e8f3e28fddb9e79110bcd0c8de2d8537ad7)
אנא כתוב אלגוריתם אשר מקבל סידרה ומדפיס תת-סידרה בדלנית שמכפלת איבריה גדולה ככל האפשר. (הנח שמכפלת איברי תת-סידרה ריקה היא 1.) קבע את Length(X) כ, ונתח את סיבוכיות האלגוריתם במונחי .
|
דוגמה: נניח שהאלגוריתם מקבל כקלט את . במקרה זה, עליו להדפיס : זו תת-סידרה בדלנית של , , ואין תת-סידרה בדלנית אחרת שמכפלת איבריה גדולה מ35. |
![{\displaystyle \displaystyle [5,7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c4ef2dda936303c72be997f28662ebf1acdec30)
