מחפש אלגוריתם בזמן ריצה הנמוך ביותר

[yarom82]

מחפש אלגוריתם בזמן ריצה הנמוך ביותר

נתון מערך A של n מספרים, כששלושת האינדקסים: n>=k>j>i>=1 מהווים תצורה נכונה אם: a<a[j] וגם a[j]>a[k] והערכיות של שלושת האינדקסים שמהווים את התצורה הנכונה מוגדרת כ: (a[j]-a)+(a[j]-a[k]) צריך למצוא את שלושת האינדקסים שנותנים את הערכיות המקסימלית. דוג': a={10,2,15,-3,-5,7,9,3,45,45} תשובה: אינדקסים 2,3,5, כי: (15-2)+(15-(-5))=33

 

[vinney]

ואם לא הבנת את הרמז

פה לא עושים שיעורי בית של אף אחד.

 

[kobi2579]

האומנם?

כותרת הפורום: שימו לב שפורום זה נועד לשאלות תיאורטיות, בנושאי אלגוריתמים, חישוביות, סיבוכיות, ותחומים אחרים של מדעי המחשב...

 

[vinney]

אבל לא לעשות שיעור בית לאף אחד

זה כתוב בהמשך. בכיף שיעלה שאלות, גם אם זה שיעורי בית. אני פשוט לא חושב שזה ראוי או מכובד לשלוח שאלה ככה, בלי שום הסבר או בקשה, ולצפות למשהו. אם הבחור רוצה שיעזרו לו לפתור - שיכתוב "תעזרו לי בבקשה לפתור", ויגיד במה הוא בדיוק מתקשה. אם הבחור רוצה לשתף איתנו שאלה מעניין - שיכתוב "תסתכלו איזו שאלה מעניינת מצאתי בXYZ", כי הרי אנחנו לא רוצים לגנוב קרדיטים, ואשמח לנעוץ את זה כדי שאף אחד לא יפסיד. אבל לשלוח הודעות כמו שהוא שלח זה לא צורה לדעתי.

 

[kobi2579]

אני אגיד לך משהו... no offence

הפורום הזה יחסית חדש, ולפי דעתי לרוב (וקראתי כאן את רוב הדפים) לא עונה על שאלות שאנשים שואלים פה... אתה לא חייב לענות לאף אחד על שום דבר, אבל אם כך אינני מבין מה מהות הפורום... אז בנאדם לא אמר בבקשה - "ביג דיל"... זה פורום מדעי המחשב ולא גן ילדים. לצורך השוואה תוכל להתבונן בפורום מתמטיקה ולראות איך עונים שם לאנשים עם פירוט, פתרונות מלאים, הוכחות מ-א' ועד ת', ואפילו שרטוטים לבעיות בהנדסה. אבל אתה מנהל הפורום אז שיהיה בהצלחה (ובאמת מכל הלב, על אף הביקורת)... אני באמת מקווה גם בשבילך וגם בשביל מבקרי הפורום בעתיד שאנשים אדיבים וסובלניים יותר יצטרפו למעגל עוני התשובות... כי אם לא, אני בספק אם יהיו בכלל שאלות, או הודעות...

 

[vinney]

טוב

לקחתי לתשומת לבי. אני ראיתי את מה שקורה בפורום מתמטיקה, ואני לא רוצה שזה מה שיהיה פה. חורה לי שמישהו יקבל ציון שלא מגיע לו, רק כי מישהו אחר פתר לו את השאלה בפורום. המישהו הזה יצטרך לעבוד איתי אחר כך, ואצטרך לסמוך על הידע שאין לו.

 

[yonyl]

האמת

אתה חושב שכל אלו שמעתיקים עבודות ולא מבינים את החומר מצליחים במבחנים? אין לי האמת מושג אבל זה מעניין. אני נתקל בהרבה סטודנטים שאין להם מושג ומבקשים שאני יישלח להם את הפתרון שלי וכ'ו. מעניין אם למרות שבעבודות הם בטח מצליחים להסתדר איכשהו הם מצליחים במבחנים.

 

[vinney]

תלוי מי, תלוי איפה ותלוי באיזה מבחן

יש מלא אנשים שמוכנים לקנות (ויש עוד יותר כאלה שמוכנים למכור להם) עבודות סמינריות/פרוייקטים. מה תגיד על מישהו שהתקבל לעבודה כי עשה פרוייקט בדיוק במה שצריך לתפקיד, ובסוף מסתבר שהוא קנה את כולו? נכון זה דוגמא קיצונית, וגם מעסיקים אמורים לעלות על זה בראיון, אבל למה לתת לזה יד? אני מכיר כמה סטודנטים שלא למדו כל הסמסטר, העתיקו הגשות, בסוף חרשו שבוע, שפכו הכל למבחן, ויום למחרת לא יודעים כלום כבר. למה זה טוב? המטלות/הגשות בתירגולים במהלך הסמסטר נועדו להחזיק אותך בקצב, לאפשר לך לעכל את החומר, להבין אותו, ברוגע של הלימודים הנורמליים, לא בלחץ של לילות לבנים לפני מבחן, ובסופו של דבר - לנוע גם את אותן הלילות הלבנים. לכן חשוב שכל אחד יפתור את התרגילים בעצמו, עם הכוונה, עם עזרה, אבל בסוף - יפתור בעצמו. לטובתם קודם כל, ולטובת כל מי שיצטרך לעבוד איתם אחרי זה, גם. אנשים כאלה רגילים שעושים עבורם את העבודה הקשה, וכמו שעשו אותה בלימודים, ככה מישהו יצטרך לעשות אותה בעבודה. בסוף - הם תמיד מפוטרים. אבל עד אז - הם פוגעים לא רק בעצמם. שוב, אני מדבר מנסיון, אני מכיר כמה.

 

[yarom82]

מסכים לחלוטין

אני מסכים איתך. אם הייתי חושב אחרת, הייתי מעתיק מסטודנט אחר שלומד איתי את הקורס. בגלל שאכפת לי, ואני רוצה להצליח לבד, העלתי את השאלה הזאת אחרי ששברתי את הראש. אני ציפיתי לקבל את ההכוונה שאתה מדבר עליה. ובמקום זה קיבלתי... אני מעדיף לא להמשיך...!!

 

[vinney]

נימוסים לא יזיקו לך.

בכל מקרה, לעניינו, מה עשית עד עכשיו ומה הקושי שלך?

 

[gil levi]

אני מסכים

שחשוב שכל סטודנט/תיכוניסט יפתור את התרגילים בעצמו, אולי עם הכוונה ורמזים, אבל שבאמת ינסה לפתור אותו. מאידך, לא הייתי רוצה לראות מצב שחבר בפורום פותר לחבר אחר בפורום את התרגיל (מבלי שהוא קיבל הכוונה/רמזים) וההודעה נמחקת.

 

[sagima]

כדאי שתבין

שאפשר לתת לאנשים דגים, אבל אם תיתן להם חכה ותלמד אותם לדוג...

 

[yarom82]

איני מבין

את החכה נתנו לי במוסד האקדמי שבו אני לומד, אה, וגם למדו אותי שם איך לדוג, אבל כנראה שלא למדו מספיק טוב... אז בכל מקרה, אם למישהו יש קצה חוט, או רעיון לאלג'.. אני אשמח! תודה מראש!

 

[niro2003]

מה אכפת לך?

אם ימצא פה פרייאר שיפתור לו את התרגיל, שיהנה.

 

[yarom82]

מנהל הפורום - דרושה הבהרה!!!

אם אנחנו לא מחפשים "פריירים" (או אנשים שמוכנים ואוהבים לעזור לאנשים אחרים - לפי איך שאני רואה את זה) להבאת רעיונות והכוונה ל"שיעורי בית" של סטודנטים שלומדים מדעי המחשב, אז במה עוסק הפורום הזה? סקרים? אולי מנהל הפורום יוכל לענות על שאלה מעניינת זו? (בואו נחזיק אצבעות, ונקווה שהוא מספיק פרייר לענות על שאלתי...) למרות שאם הוא לא ידע לתת לי כיוון לפתור את הבעיה שנתתי למעלה, קשה לי להאמין שיוכל לענות לי גם על זו.

 

[Desslok of Gamilon]

האם בכנות אתה לא מבין את ההבדל בין לעזור למישהו לבין לעשות את העבודה במקומו? אם היית כותב איך ניסית לפתור, למה הגעת ובמה התקשית, אנשים פה היו שמחים לעזור לך - וגם היית לומד מזה משהו. במקום זה העתקת לפה שאלה, מילה במילה, בלי לנסות לחשוב עליה. נניח שמישהו היה פותר אותה - מה היית עושה אז? מעתיק את התשובה, מילה במילה, בלי לנסות לחשוב עליה, ומגיש למורה/מרצה? בשביל מה זה טוב? כאן לא פורום "עושים את העבודה שלך בשבילך, בזמן שאתה הולך לים".

 

[niro2003]

אתה אמור לכתוב מספר דברים על השאלה

שאתה מביא קרי: להוכיח שהתעמקת בה ונכשלת. את זאת לא עשית.

 

[DadleFish]

תחשוב...

...איך היית פותר את השאלה בעצמך - כלומר, בהינתן מערך כלשהו, איך היית עושה את זה. דרך אחת היא למשל לעבור על כל האפשרויות של J, ואז לנסות את כל האפשרויות ל-I ואת כל האפשרויות ל-K. עכשיו נסה להבין מה סדר הגודל של אלגוריתם נאיבי כזה, ובוא ננסה לשפר אותו. אם תסתכל על הנוסחה שצריך למקסם, תראה ש-[a[j מופיע פעמיים בפלוס והשניים האחרים במינוס. במילים אחרות, אתה צריך [a[j גבוה ככל האפשר, ו-i ו-k נמוכים ככל האפשר. אם תצייר את המערך כגרף, תרצה לתפוס פסגה בגרף כשמשני צידיה יש עמקים נמוכים מאוד. אולי יעזור לך, למשל, למיין את המערך על פי הנתונים שבתוכו, או סתם למצוא 2-3 ערכי מקסימום ומינימום... שאל את עצמך לגבי המערך שלך, למה לא יכולת להשתמש ב-45 למשל בתור j, או ב-5- וב-3- בתור i ו-k. נסה להמשיך עם קצה החוט הזה. אל תשכח שבכל מקרה אתה צריך להוכיח שהפתרון שלך הוא המקסימלי, ולא מספיק למצוא local maxima אלא אתה צריך את ה-global maxima.

 

[yarom82]

תודה רבה! - שאלה אחרונה

ת'אמת אני צריך להגיש את העבודה מחר... ההסבר שנתת לי למעלה, הוא הסבר לשאלה, לפי איך שאני הבנתי את זה, ולא רעיון לפתרון. פתרתי את זה בדרך איטרטיבית ובסיבוכיות O(n^2. אבל מכיוון שלמדנו רק לאחרונה תכנות דינאמי, חשבתי שהכוונה בתרגיל הזה היא לפתור את זה ע"י תכנות דינאמי. כלומר, למצוא את הסכום המקסימאלי ולאחר מכן, במעין תוכנית עזר אחרת, למצוא את האינדקסים... (וכך אולי להגיע לסיבוכיות של O(n. מישהו הבין למה התכוונתי? האם זה הפתרון הנכון?

 

[דני מיכאלי]

בנוגע לשאלה זו, בפתרון שלי

הגעתי לסיבוכיות של

O​

השאלה היא האם האלגוריתם אכן מבצע זאת כמו שצריך, אודה לכם באם תוכלו לבדוק את האלגוריתם ולהציע הצעות לשיפור? להלן קוד האלגוריתם שהגעתי אליו.

max_hill(A,n) max_r = -∞ max_l = -∞ min_r = 1 min_l = n for j = 2 to n-1 r = A[j] - A[min_r] l = A[j] - A[min_l] if r > max_r max_r = r max_i_r = min_r max_j = j end if if l > max_l max_l = l max_i_l = min_l end if if A[j] < A[min_r] min_r = j end if if A[j] ≤ A[min_l] min_l = min_l-1 end if end for return ((max_j-max_i_r)+(max_j-max_i_l))​