שאלה על מחסניות

[assaf990]

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

איך כותבים אלגוריתים לזה?

מעדיף ב-C++ או אפילו ברעיון, את השלבים והסבר.

תודה

[Holy]

כל אחת מתחילה מקצה שני של המערך

זה די פשוט...

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

למחסנית הראשונה אתה דחוף ל-sizeof_stack1 ולשניה אתה דוחף ל-total_size-sizeof_stack2

[assaf990]

תוכל להסביר את המשפט האחרון במילים פשוטות יותר?

[Holy]

כשאתה רוצה להכניס למחסנית הראשונה איבר אז אתה צריך לשים אותו בראש המחסנית

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

במחסנית השניה אם יש n2 איברים אז אתה צריך לדחוף את האיבר החדשה במקום ה-n2 מהסוף. אם גודל המערך הוא N אז את האיבר תשים במקום ה-N-n2-1

[assaf990]

האמת, עדיין לא הבנתי ב-100%, אתפוס ראש ואנסה להבין

שאלה נוספת: האם הצעתך היא בסיבוכיות של

0(n)?

[Holy]

מה נראה לך?

[assaf990]

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

[Holy]

אז מה הטעם לשאול שאלה שאתה לא מבין?

קודם תבין מה זה סיבוכיות ואז תבין באיזה סיבוכיות זה.

[Ghosthunter]

נראה לי שיש פתרון פשוט יותר(ללא שמירה של גודל המחסנית).

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

(שני הפתרונות זהים לחלוטין חוץ מהעיקרון הבסיסי)

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

[assaf990]

OK

הבנתי!

תודה

[Ghosthunter]

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

[big foot]

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

מנסיון

[assaf990]