11-11-2008, 09:13
|
|
|
חבר מתאריך: 11.03.08
הודעות: 2
|
|
שאלה באלגוריתמים
היי,
מישהו יכול בבקשה לעזור לי בשתי השאלות הבאות.
1. תהי רשימה עם M מספרים טבעיים שונים (לא עוקבים).
א. הוכח כי קיימת תת רשימה (בלוק שלם בתוך הרשימה, בלי דילוגים) שסכומה מתחלק ב N לכל N קטן או שווה ל M.
ב. כתוב אלגוריתם שמוצא תת רשימה כזו בסיבוכיות של o(n+m)
2. תהי רשימה של מספרים ממשיים שונים. כתוב אלגוריתם המוצא תת רשימה רציפה שסכומה הוא מקסימלי בסיבוכיות של o(n)/. אין להשתמש בהרבה זכרון (אסור מערכים).
תודה
|