מציאת מרחק בין איברים במערך

[יוספה27]

מציאת מרחק בין איברים במערך

איך אפשר למצוא מרחק מקסימלי בין שני איברים כאשר השמאלי גדול מהימני ?

 

[BravoMan]

השאלה שלך לא מובנת לחלוטין.

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

 

[יוספה27]

לדוגמא

נתונה סדרת האיברים - 1956710 ארצה לחשב את המרחק המקסימלי בין שני איברים שמקיימים שהגדול משמאל . במקרה של סדרה זו התשובה תהיה 3 עקב התת סדרה 9567 שבו 9 משמאל ל 7 במרחק הגדול ביותר מכל שאר המרחקים בין זוגות איברים בסדרה הנתונה שהשמאלי גדול מהימני . שאלתי היא איך עושים זאת ?

 

[BravoMan]

תן לי להבין רגע:

הכוונה אינה שהאיבר בקצה השמאלי גדול מהימני, אלא למעשה לכלל כזה:
1. קח מספר ותתחיל לזוז ימינה.
2. כל כל עוד כל מספר קטן מזה שמשמאלו (לפניו) ספור צעדים.
3. מצא את ספירת הצעדים הגדולה ביותר.
&nbsp
עכשיו שניסחתי את הבעיה מחדש, צריך להיות לך די ברור איך לפתור את התרגיל.
הכל שאלה של ניסוח!
&nbsp

 

[יוספה27]

יש בעיה באלגוריתם שלך

מה יקרה במצב של 1967510 האם גם עתן 3 כגודל המרחק בין 9 ל 5 בתת סדרה 9675 ? הוא יעצר ב 7 ויכול להמשיך ל 5 . עד כמה שאני מבינה זה קצת יותר מורכב ודורש שני תתי סדרות של קצה שמאלי וקצה ימני שהראשון גדול מהשני ????

 

[BravoMan]

אוקיי, הצלחת לבלבל אותי לחלוטין...

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

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

אז למה עצרנו ב-7 בדוגמה הראשונה, וב-5 בדוגמה השניה?

בדוגמה הראשונה, יש 1 בקצה השמאלי של המערכך, ו-0 בקצה הימני, אז בתאוריה, המרחק הגדול ביותר בין איבר שמאלי שגדול מאיבר ימני הוא אורך כל המערך.

לא ברור כלל למה בחרת דווקא תת סדרה של 9567.
חשבתי שזה בגלל ש-5 קטן מ-6 ו-6 קטן מ-7 אבל הדוגמה השניה שברה את זה.

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

 

[יוספה27]

תת סדרה בגודל מקסימלי - קצה שמאלי גדול מקצה ימני

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

 

[BravoMan]

אני באמת לא יודע, כי אני לא מבין איך הדוגמאות שהצגת עונות

על השאלה.
&nbsp
ממליץ לך לפנות למי שנתן את התרגיל הזה ולקבל הבהרות, ובמיוחד לשאלה מדוע התת סדרה הכי ארוכה בדוגמה ראשונה היא 9 עד 7 ולא 1 עד 0.

 

[יוספה27]

הבהרה לגבי הדוגמא

כי המספר האחרון בסדרה של הדוגמא הוא 10 ולכן ומאחר ו 1 לא קטן מ 10 אז נבחרו 9 ו 7 . בכל מקרה ניסחתי השאלה ונתתי רמז ושוב ולפי הבנתי זה יותר מורכב מכפי שנראה .
תודה על כל עזרה שהיא .

 

[BravoMan]

אוקיי.

בכנות, אני חושב שהרמז טיפה מבלבל.
מה רע בפשוט:
1. שים "עוגן" בנקודת התחלה (מתחיל מתא 0).
2. כל עוד מספרים במערך קטנים מהעוגן, תמשיך לרוץ ולספור כמה יש.
3. נתקלת במספר גדול או שווה לעוגן?
4. האם המרחק שמצאת גדול מהמרחק הקודם שמצאת?
4.1. אם כן, שמור אותו.
5. תתחיל מ-1, כאשר העוגן החדש הוא המקום הנוכחי.

 

[יוספה27]

עדיין לא ברור איך יחשב את המקרה בו

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

 

[BravoMan]

ברגע שמצאת גדול מהעוגן, העוגן עובר להיות הגדול החדש.

באי ננסה את הדוגמה שלך:
1,9,5,6,7,10
מתחילים בעוגן 1, זזים ל-9. מרחק = 0.
עוגן עובר ל-9, סופרים 0, 1, 2, 3 - מגיעים ל-10. מרחק = 3.
עוגן עובר ל-10. הגענו לסוף מערך.
מרחק הכי גדול = 3.
&nbsp
תני דוגמה מספרית שאת חושבת שלא תעבוד, ונעבור עליה ביחד.

 

[יוספה27]

הכיוון נראה נכון ומה לגבי הדוגמא

2 , 9 , 1 , 10 , 8 והתשובה היא 4 - המרחק בין 8 ו 2 . תודה מראש לראש .