מבנה נתונים: תורים ומחסנית

[shochat1]

מבנה נתונים: תורים ומחסנית

אם עליי לממש 2 מחסניות באמצעות מערך אחד כאשר פעולות push pop צריכות להתבצע בO1 זמן. והדרישה היא שתתקיים גלישה באחת מהמחסניות אמ"מ המס' הכולל של האיברים ב2 המחסניות הוא N לדעתי ניתן לפתור כך שאם יש לי 2 מחסניות למשל כך: 1,7,11 והשנייה:2,17,22 וארצה לסדר במערך אתחיל ממחסנית הראשונה למשל כל אם האיבר המתאים במחסנית השנייה קטן יותר הוא יקדים אותו ואז יבדק האיבר הבא ככה שבמערך החדש המס' יהיו מסודרים מקטן לגדול אך אינני מבין את ההערה האחרונה ואם אכן אני מתייחס אליה כמו שצריך ואם אני עונה על השאלה כמו שצריך...

 

[ron369]

איך תוכל לגשת לאיבר, ולדעת באיזה

מהמחסניות הוא, אם סידרת את האיברים לפי סידור ממויין?

 

[gil levi]

אני לא מבין את הפתרון שלך,

אבל יש לי רעיון אחר. אני אתן לך רמז דק: תחלק את המערך לשתי מחסניות- שמאלית וימנית.

 

[gil levi]

טוב, זה רמז יותר מדי דק.

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

 

[ron369]

גם לי יש רמז ../images/Emo13.gif

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

 

[gil levi]

היכון לתביעה על הפרת זכויות יוצרים!

 

[ron369]

אבל זה היה ציטוט! עם " כאלו! ../images/Emo13.gif

 

[gil levi]

נו מילא. לא נתבע.

 

[shochat1]

כלומר אתה אומר

קח את המס' ראשון הכנס משמאל הבא אם הוא גדול ממנו הכנס מימין ואם הוא קטן ממנו הכנס משמאלו

 

[shochat1]

או יותר טוב

תצמיד את קצות הנול של המחסניות והצמד ואז קח את המס' הראשון שים במחסנית הימנית הבא אחריו אם הוא קטן ממנו שים בשמאלית אם הוא גדול ממנו שים בימנית ??

 

[Fingertip]

לא...

נניח שיש לך שתי מחסניות:

1 2 a 3 b​

(בכוונה באחת יש מספרים ובשנייה יש אותיות... אלו מחסניות של תוים

) שתי המחסניות עומדות. נפיל את הימנית ימינה והשמאלית שמאלה, ונקבל:

1 2 3 | a b​

עכשיו יותר ברור? אהד.

 

[shochat1]

כן ולא

הפלת ל2 מחסניות אבל מי אמר שזה נפל בכזה סדר יפה ומי אמר ש2 המחסניות לא יהיו נאמר ככה: 349|127

 

[ron369]

חכה שניה, איך תגיע למצב כזה?

(ומה רע בו?)

 

[gil levi]

הסבר.

כאן.

 

[shochat1]

רק בעיה אחת

הכנסת משמאל הכנסת מימין אין סדר לאיברים בסופו של דבר ולא הבנתי איך זה ממלא את הדרישה שתתקיים גלישה באחת מהמחסניות אמ"מ המס' הכולל של האיברים ב2 המחסניות הוא N

 

[shochat1]

לא משנה לגבי זה

 

[ron369]

רמז חדש! (הוא עוד לא פתר,נכון?)

תחשוב על זה ככה. נניח שאתה משתמש במערך אחד לשני מחסניות. אז אתה יכול, למשל, לשים איברים של מחסנית אחת במקומות הזוגיים במערך, ומחסנית שניה במקומות האי זוגיים במערך. הבעיה היא שאז יש לך מצב שבו אם במחסנית אחת צריכים להכנס יותר מN/2 איברים, גם אם המחסנית השניה ריקה, אתה יכול להתקע (ב"סוף"). מה שניתן לעשות במקרה זה, הוא "לחזור אחורה". איך? כיצד? מושאר כתרגיל לקורא.

 

[shochat1]

שמת לב שרשמתי

לא משנה זה אומר שהבנתי כבר קודם תודה...

 

[shochat1]

עוד שאלה: תורים ומחסניות בלבד

עליי לקבל את N כקלט ולהדפיס מס' שמתחלקים באחד מהמס' הראשוניים 2,3,5 בלבד כלומר נאמר וארשום 20 הוא ידפיס: 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20 .... בלי למשל 14 שמתאים לדרישה הראשונית אך מתחלק ב7 מה שפוסל אותו והצעתי כך על קלט יתחיל מההתחלה ועל כל מס' יבדוק חילוק באחד מהמס' הראשונים כל גורם חלוקה ינסה לחלק שוב באחד מתוך המס' הללו אם התוצאה הסופית של גורם חלוקה שלו תהיה 1 או 2 או 3 או 5 אז זה בסדר אך לא ניתן לחלק כלומר חלוקה בכל אחד המס' תתן מס' לא שלם כמו 7/2 וכ"ו ???

 

[shochat1]

חברים עזרה בבקשהההה