שאלה לגבי מחסנית

[jan777]

שאלה לגבי מחסנית

היי חברים, יש לי שאלה שאומרת כזה דבר פונקציה שתבצע את הדבר הבא: אם מחסנית מסויימת נראית כך: !@#$% אז אני צריך להוציא את האיבר בעומק K במחסנית זו. כלומר,אם K=2 אז האיבר שיוחזר יהיה $. הסתבכתי עם הבעיה כי חשבתי לעשות POP כל הזמן ואז לשאול אם הtop של המחסנית שווה ל k אבל אז נזכרתי שכל פעם שאני אעשה pop אז הtop ייקטן באחד. אפשר רמז בבקשה? תודה.

 

[jan777]

אני כמעט בטוח שהגעתי לתשובה!!!

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

function pelet(st:stack_type;k:integer):stack_info_type; var x:stack_info_type; begin if top<k then pelet:=' '; else (if top>k) for i:=1 to k do stack_pop(st,x); pelet:=x; end;​

 

[vinney]

ופה נשאלת השאלה

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

 

[jan777]

הסתכלתי בספר ואתה אכן צודק...

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

function pelet(st,ez:stack_type;k:integer):stack_info_type; var x:stack_info_type; begin stack_init(ez); if top<k then pelet:=' '; else [if top>k] for i:=1 to (k-1) do begin stack_pop(st,x); stack_push(ez,x); end; stack_pop(st,x); stack_push(ez,x); pelet:=x; for i:=(k+1) to top do begin stack_pop(st,x); stack_push(ez,x); end; while not stack_empty(ez) do begin stack_pop(ez,x); stack_push(st,x); end; end;​

 

[jan777]

וסיבוכיות זמן הריצה היא

O(1);​

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

 

[vinney]

לא

 

[HaifaMan]

אם אתה סורק את כל המחסנית זה כבר לא O(1)

 

[vinney]

זה לא נראה לי נכון

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

 

[jan777]

הוא לא לוקח את ה top מההגדרה מעל לתכנית אבל

שהוא 5 במקרה הזה?

 

[vinney]

אני לא יודע על מה אתה מדבר

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