כמה שאלות:

[ronihp]

אם כך

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

 

[vinney]

ואיך אתה מוסיף משהו בו זמנית לכולם?

לזה תצטרך את השלישי

 

[ronihp]

הלכתי על הפתרון עם המחסנית

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

 

[vinney]

משתנה עזר

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

 

[אלוהים1980]

היי, השאלה הזאת היתה לי במבחן...

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

 

[vinney]

לא הבנתי למה צריך מחסניות...

למה אתה צריך לזכור מינימום ומקסימום לרגע ההכנסה לכל איבר?

 

[vinney]

וואלה צודק, צריך ../images/Emo13.gif

 

[ronihp]

אין פה בזבוז משאבים?

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

 

[vinney]

ברמת המקדמים, אתה יכול להתעלם

 

[אלוהים1980]

נדמה לי שבמבחן שלי היה מותר להשתמש

רק במחסניות, אם כי אני לא בטוח. בכל מקרה, הרעיון הוא שתוכל תמיד ב O של 1 לקבל את הנתונים.

 

[ronihp]

לגבי ד'

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

 

[ronihp]

אני צריך עזרה עם אלגוריתם רקורסיבי

בהנחה ונתונה לי מפה של רחובות, נניח בעץ. לדעתי, הפונ' צריכה להיות רקורסיבית על מנת למצוא את כל הדרכים להגיע מ-A ל-B למשל. רק שאני לא מבין מה הפונ' צריכה לקבל בכל פעם.

 

[ronihp]

בינתים רק רשימה מקושרת

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

 

[cprog]

מערך בלבד,כנס לפרטים ודוגמא.

רשימה מקושרת לצורך העניין זה רע. אתה צריך להשתמש במחסנית LIFO והשכלול הוא שאחרי כל שלב בחיפוש יש למיין את אברי המחסנית. הדרך היעילה לעשות זאת היא בעזרת מחסנית של POINTERS ואז בכל שלב אתה ממיין את ה POINTERS (לפי תוכן ה struct עליהם הם מצביעים, לא לפי כתובות בזכרון). אתה מוזמן להוריד את הפרוייקט Traveling Agent מאתר הבית שלי, יש source-code מלא (VC++6, נכתב ב 1999) בחן את stack.cpp תמצא שם מימוש אלוגריתם Branch and Bound ובנוסף,דוגמא למיון המחסנית.

 

[cprog]

התשובה הזאת מתייחסת לבעיית המרחק

התשובה הזאת מתייחסת לבעיית המרחק-המינימלי שביקשת עזרה בפתרונה בתחילת השרשור.