שאלה במבני נתונים.
התרגיל בתמונה. בגלל שדורשים שהאלגוריתמים יהיה יעילים ככל שניתן, חשבתי לכתוב אותם כאן כדי שתוכלו להעיר לי אם הם לא הכי יעילים שניתן או שהם לא נכונים. לפונ' הראשונה (isStrictlyMonotonicDownUpArray) 1. מחלקים את המערך לשני חצאים. 2. בודקים אם החלק הימני מונוטוני עולה (הבדיקה על ידי פונקציה אחרת, רקורסיבית, שכל פעם חוצה את המערך לשני חצאים ובודקת אם שניהם מונוטונים עולים). 3. בודקים אם החלק השמאלי מונוטוני יורד. 4. אם החלק הימני לא מונוטוני יורד אזי: 4.1. מפעילים את isStrictlyMonotonicDownUpArray על החלק הימני. 4.2. אם החלק הימני הוא מערך Down-Up (ז"אstricrly monotonic downup array ) וגם החלק השמאלי לא מונוטוני יורד אזי 4.2.1 החזר שקר. 4.3 אם החלק הימני הוא מערך Down-Up וגם שמאל מונוטוני יורד אזי 4.3.1 החזר אמת. 5. אם החלק השמאלי לא מונוטוני יורד אזי 5.1 מפעילים את isStrictlyMonotonicDownUpArray על החלק השמאלי. 5.2 אם החלק השמאלי הוא מערך Down-Up וגם החלק הימני לא מונוטוני עולה אזי 5.2.1 החזר שקר. 5.3 אם החלק השמאלי הוא מערך Down-Up וגם החלק הימני מונוטוני עולה אזי 5.3.1 החזר אמת. 6. אם החלק הימני מונוטוני עולה וגם החלק השמאלי מונוטוני יורד אזי 6.1 החזר אמת. 7. החזר שקר. תנאי העצירה הוא בעצם 6, כי כשבודקים אם מערך הוא Down-Up אז מתישהו כשנחצה נגיע למצב שבו החצי הימני מונוטוני עולה והחצי השמאלי מונוטוני יורד. לפונ' השניה: נראה לי שפשוט בודקים מי יותר גדול, האיבר הראשון או האחרון (הפונ' findMax מקבלת גם את האורך של המערך). תודה מראש.
התרגיל בתמונה. בגלל שדורשים שהאלגוריתמים יהיה יעילים ככל שניתן, חשבתי לכתוב אותם כאן כדי שתוכלו להעיר לי אם הם לא הכי יעילים שניתן או שהם לא נכונים. לפונ' הראשונה (isStrictlyMonotonicDownUpArray) 1. מחלקים את המערך לשני חצאים. 2. בודקים אם החלק הימני מונוטוני עולה (הבדיקה על ידי פונקציה אחרת, רקורסיבית, שכל פעם חוצה את המערך לשני חצאים ובודקת אם שניהם מונוטונים עולים). 3. בודקים אם החלק השמאלי מונוטוני יורד. 4. אם החלק הימני לא מונוטוני יורד אזי: 4.1. מפעילים את isStrictlyMonotonicDownUpArray על החלק הימני. 4.2. אם החלק הימני הוא מערך Down-Up (ז"אstricrly monotonic downup array ) וגם החלק השמאלי לא מונוטוני יורד אזי 4.2.1 החזר שקר. 4.3 אם החלק הימני הוא מערך Down-Up וגם שמאל מונוטוני יורד אזי 4.3.1 החזר אמת. 5. אם החלק השמאלי לא מונוטוני יורד אזי 5.1 מפעילים את isStrictlyMonotonicDownUpArray על החלק השמאלי. 5.2 אם החלק השמאלי הוא מערך Down-Up וגם החלק הימני לא מונוטוני עולה אזי 5.2.1 החזר שקר. 5.3 אם החלק השמאלי הוא מערך Down-Up וגם החלק הימני מונוטוני עולה אזי 5.3.1 החזר אמת. 6. אם החלק הימני מונוטוני עולה וגם החלק השמאלי מונוטוני יורד אזי 6.1 החזר אמת. 7. החזר שקר. תנאי העצירה הוא בעצם 6, כי כשבודקים אם מערך הוא Down-Up אז מתישהו כשנחצה נגיע למצב שבו החצי הימני מונוטוני עולה והחצי השמאלי מונוטוני יורד. לפונ' השניה: נראה לי שפשוט בודקים מי יותר גדול, האיבר הראשון או האחרון (הפונ' findMax מקבלת גם את האורך של המערך). תודה מראש.
= 2*T(n/2) + c*n