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

[assaf990]

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

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

 

[shirbi]

מה בדיוק הבעיה?

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

 

[assaf990]

ואז? איך זה פותר?

 

[operandx]

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

 

[operandx]

אופס, לא יודע לשרשר, סורי.

 

[assaf990]

?? לא מובן לי עדיין, לצערי

 

[vinney]

שנפתור לך ונגיש ישר למרצה?../images/Emo13.gif

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

 

[gil levi]

יש את זה ב Knuth דרך אגב.

הרעיון הוא כזה: יש לנו מערך A בגודל n (והמספור של האינדקסים יתחיל מ1, לשם הפשטות). נניח המחסניות שלנו הן R וL. ראש המחסנית R יהיה ב A[n] zzz וראש המחסנית L יהיה ב A[1]zzz. מה שבעצם קורה זה שכשאנחנו מכניסים לR אנחנו מכניסים מהכיוון של A[n] zzz לכיוון של A[1]zzz וכשאנחנו מכניסים לL אנחנו מכניסים מהכיוון של A[1] zzz לכיוון של A[n] zzz. ננסה לצייר את זה:

A[1] A[2] A[3]...................................A[n-1] A[n] 45 63 33 הכנסת 22 למחסנית השמאלית: A[1] A[2] A[3]...................................A[n-1] A[n] 22 45 63 33 הכנסת 13 למחסנית הימנית: A[1] A[2] A[3]...................................A[n-1] A[n] 22 45 63 33 13​

עכשיו זה יותר ברור?

 

[assaf990]

ברור בהחלט! אך לפי מה "מלא"?

לפי מה תודיע כל מחסנית שהיא "מלאה"? (להזכיר. כל מחסנית מודיעה שהיא מלאה רק אם סכום איברי 2 המחסניות הוא N)

 

[gil levi]

רעיון.

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

 

[assaf990]

תודה - הבנתי!!!!!! ../images/Emo13.gif