שאלה לגבי פונקצית פוטנציאל

Summary:

איך התקבלה פונקצית הפוטנציאל של מימוש מחסנית במערך?

שאלה

hadarb 04 Mar 2009 19:05

בהרצאה הראשונה בחלק של function potential: למה הפוטנציאל של המחסנית מוגדר ככה - t+1)*2 - n) ?

Re: שאלה

Yahav 04 Mar 2009 20:29

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

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

1. בפעולות פוש ופופ "זולות" הפוטנציאל לא יעלה בהרבה.
2. בפעולת פוש "יקרה", הפוטנציאל ירד בגודל המערך.
3. הפוטנציאל לעולם לא יהיה שלילי.

מדרישה 2, המקדם של
N
צריך להיות שלילי (למשל 1 -)
מדרישה 1, המקדם של
t
צריך להיות כפול בערכו המוחלט מזה של
N
כי רק חצי מהאברים במערך יכולים "להתקזז" עם ההגדלה הבאה של המערך.
(החצי השני, של האיברים הישנים יותר, כבר "התקזז" עם הגדלה קודמת של המערך.)
שאר הביטוי נועד לשמור על דרישה 3.

זו כמובן לא הפונקציה היחידה שעונה על כל הדרישות, אפשר למשל להכפיל את המקדמים של
N, t
או למשל להגדיל רק את המקדם של
t

הדגמה

Yahav 04 Mar 2009 22:00

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

Stack as Array demonstration

Last edited on 04 Mar 2009 22:07 by Yahav + Show more

Re: הדגמה

Juny327 08 Mar 2009 22:40

תודה על ההדגמה.

לגבי פונקציית הפוטנציאל:

שאלה 1:
מי זה
t?
האם זה מספרים האיבר הנוכחי (סופרים מ-1)? האם זה המקום שלו במערך (סופרים מ-0)?

שאלה 2:
במצגת הפונקציה מוצגת עם תנאי:
if 2(t + 1) - N > 0
אז ערך הפונקציה הוא כמו שראינו.
אחרת ערך הפונקציה הוא 0.
נגיד המערך שלי הוא בגודל 2. בפוש הראשון
t=1
N=2
אז לפי הגדרת הפונקציה צריך לצאת שמצב הבנק הוא 0. אנחנו יודעים שהוא צריך להיות 2. אז איך זה מסתדר?
ולמה בכלל יש את התנאי הזה? זה נועד למקרה שאין מספיק כסף בבנק? הרי בשום שלב זה לא אמור לקרות, אז למה צריך את זה?

Re: הדגמה

Danny Feldman 08 Mar 2009 23:35

Q1) $t$ is defined in the beginning of the presentation, inside "push".
It is the last filled index in the array, or the number of current items minus one.
Should be initialized to "-1" when the stack is empty.

Q2) Note that N is the size of the array minus 1. after the first "push" we have "t=0".
We will discuss this in class.

Re: הדגמה

Yahav 09 Mar 2009 06:36

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

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

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