ex4a2 מחסנית Stack

Stack מחסנית: תרגילים מתקדמים

4a2.111 בדיקת מחסנית עולה יורדת

link

עליכם לממש פונקציה בשם IsMountainStack אשר מקבלת פרמטר אחד:

  1. st - מחסנית של מספרים שלמים (מסוג Unit4.CollectionsLib.Stack).

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

הפונקציה צריכה להחזיר true אם המחסנית עונה על הקריטריון ו-false אחרת.

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

שימו לב:

  1. השתמשו במחלקה Unit4.CollectionsLib.Stack.
  2. ניתן להשתמש במבני נתונים עזר (כמו מחסניות או תורים נוספים) לצורך הבדיקה והשחזור.
  3. המחסנית יכולה להיות ריקה או להכיל איבר בודד. במקרים אלו, המחסנית נחשבת ‘עולה-יורדת’.

דוגמאות:

  1. עבור המחסנית [5, 4, 3, 2, 1] (כאשר 5 בראש המחסנית), הפונקציה תחזיר true (1 עולה ל-5, ואז 5 יורד ל-1).
  2. עבור המחסנית [1, 2, 3, 4, 5] (כאשר 1 בראש המחסנית), הפונקציה תחזיר true (5 עולה ל-1, ואז 1 יורד ל-5).
  3. עבור המחסנית [1, 3, 2, 4] (כאשר 1 בראש המחסנית), הפונקציה תחזיר false (הסדר אינו עולה-יורד).
  4. עבור המחסנית [10, 20, 15] (כאשר 10 בראש המחסנית), הפונקציה תחזיר true (15 עולה ל-20, ואז 20 יורד ל-10).

4a2.111 בדיקת מיון מחסנית איטרטיבית

link

עליכם לממש פונקציה איטרטיבית בשם IsStackSorted אשר מקבלת פרמטר אחד:

  1. stack - מחסנית של מספרים שלמים (מסוג Unit4.CollectionsLib.Stack).

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

דרישות:

  1. הפעולה חייבת להיות איטרטיבית (אין להשתמש ברקורסיה).
  2. יש להשתמש במבנה נתונים עזר אחד בלבד (לדוגמה, מחסנית נוספת או תור) לצורך הבדיקה ושחזור המחסנית.
  3. בסיום הפעולה, המחסנית המקורית חייבת לחזור למצבה המקורי בדיוק (כולל סדר האיברים).
  4. הפונקציה תחזיר true אם המחסנית ממוינת בסדר עולה, ו-false אחרת.

שימו לב:

  1. מחסנית ריקה נחשבת לממוינת.
  2. מחסנית עם איבר בודד נחשבת לממוינת.
  3. יש להשתמש ב-using Unit4.CollectionsLib; בקובץ הפתרון.

דוגמאות:

  1. עבור המחסנית [1, 2, 3, 4, 5] (כאשר 1 הוא בתחתית ו-5 בראש), הפונקציה תחזיר: True
  2. עבור המחסנית [1, 3, 2, 4, 5] (כאשר 1 הוא בתחתית ו-5 בראש), הפונקציה תחזיר: False
  3. עבור המחסנית [5, 4, 3, 2, 1] (כאשר 5 הוא בתחתית ו-1 בראש), הפונקציה תחזיר: False
  4. עבור מחסנית ריקה, הפונקציה תחזיר: True

4a2.111 בדיקת מיון מחסנית רקורסיבית

link

עליכם לממש פונקציה רקורסיבית בשם IsStackSorted אשר מקבלת מחסנית של מספרים שלמים (מסוג Stack).

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

דגשים:

  1. הפונקציה חייבת להיות רקורסיבית.
  2. בסיום הפעולה, המחסנית המקורית חייבת לחזור למצבה המקורי (כלומר, עם אותם איברים ובאותו סדר כמו לפני קריאה לפונקציה).
  3. יש להשתמש במחלקת Stack מתוך Unit4.CollectionsLib.

חתימת הפונקציה הנדרשת:

public static bool IsStackSorted(Stack)

link

דוגמאות:

מחסנית ממוינת:קלט (מחסנית, כאשר 5 בראש):

[1, 2, 3, 4, 5] פלט: True

מחסנית לא ממוינת:קלט (מחסנית, כאשר 2 בראש):

[1, 3, 2, 4] פלט: False

מחסנית ריקה:קלט:

[] פלט: True

4a2.111 בדיקת קיום איבר במחסנית רקורסיבי

link

עליכם לממש פונקציה רקורסיבית בשם IsElementInStack אשר מקבלת שני פרמטרים:

  1. st - מחסנית (מסוג Unit4.CollectionsLib.Stack) של מספרים שלמים.
  2. element - המספר השלם שיש לחפש במחסנית.

הפונקציה צריכה להחזיר true אם element נמצא במחסנית, ו-false אחרת.

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

דגשים:

  1. השתמשו ברקורסיה לפתרון הבעיה.
  2. עליכם להשתמש במחלקת Unit4.CollectionsLib.Stack.
  3. טפלו במקרה הבסיס של מחסנית ריקה.
  4. ודאו שהמחסנית משוחזרת למצבה המקורי לאחר הבדיקה.

link

דוגמאות:

  1. עבור מחסנית המכילה [1, 2, 3, 4] (כאשר 4 בראש) ואיבר 3, הפונקציה תחזיר true.
  2. עבור מחסנית המכילה [10, 20, 30] (כאשר 30 בראש) ואיבר 5, הפונקציה תחזיר false.
  3. עבור מחסנית ריקה ואיבר כלשהו, הפונקציה תחזיר false.
  4. עבור מחסנית המכילה [5, 10, 15] (כאשר 15 בראש) ואיבר 15, הפונקציה תחזיר true.

4a2.111 בדיקת רצף ספרות במחסנית

link

עליכם לממש פונקציה בשם CheckSequenceInStack אשר מקבלת שני פרמטרים:

  1. number (int) - מספר שלם שאת ספרותיו יש לחפש.
  2. stack (Stack

הפונקציה צריכה להחזיר true אם ספרות המספר מופיעות ברצף במחסנית (בכיוון עולה או יורד), ו-false אחרת.

דרישות מיוחדות:

  1. יש להשתמש במחלקת Stack מתוך Unit4.CollectionsLib.
  2. המחסנית המקורית (stack) חייבת לחזור למצבה המקורי בסיום הפעולה (כלומר, אם הפונקציה קיבלה מחסנית עם איברים מסוימים, היא צריכה להחזיר אותה באותו מצב בדיוק).
  3. הרצף יכול להופיע בכל מיקום במחסנית.
  4. הרצף יכול להיות בכיוון עולה (לדוגמה, 1,2,3 עבור המספר 123) או בכיוון יורד (לדוגמה, 3,2,1 עבור המספר 123).

הנחיות למימוש:

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

using Unit4.CollectionsLib;

public class Solution { public static bool CheckSequenceInStack(int number, Stack) { // implement your code here } }

דוגמאות:

  1. עבור מספר 123 ומחסנית המכילה [5, 4, 1, 2, 3, 6], הפונקציה תחזיר true (הרצף 1,2,3 נמצא).
  2. עבור מספר 123 ומחסנית המכילה [5, 4, 3, 2, 1, 6], הפונקציה תחזיר true (הרצף 3,2,1 נמצא).
  3. עבור מספר 789 ומחסנית המכילה [1, 2, 3, 4, 5], הפונקציה תחזיר false.
  4. עבור מספר 12 ומחסנית המכילה [1, 3, 2], הפונקציה תחזיר false (אין רצף 1,2 או 2,1).

4a2.111 בדיקת שוויון בין מחסניות, רקורסיבי

link

עליכם לממש פונקציה רקורסיבית בשם AreStacksEqual אשר מקבלת שני פרמטרים:

  1. s1 - מחסנית ראשונה (מסוג Stack)
  2. s2 - מחסנית שנייה (מסוג Stack)

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

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

הנחיות למימוש:

  1. השתמשו במחלקת Stack מתוך Unit4.CollectionsLib.
  2. הפתרון חייב להיות רקורסיבי.
  3. אין להשתמש בלולאות.
  4. יש לטפל במקרה הבסיס של מחסניות ריקות.
  5. יש לוודא שכל איבר שהוצא ממחסנית נדחף בחזרה אליה בסיום הקריאה הרקורסיבית הרלוונטית, על מנת לשמר את מצבן המקורי של המחסניות.

דוגמאות:

  1. עבור מחסנית 1: [1, 2, 3] (כאשר 1 בראש) ומחסנית 2: [1, 2, 3], הפונקציה תחזיר true.
  2. עבור מחסנית 1: [1, 2, 3] ומחסנית 2: [1, 2, 4], הפונקציה תחזיר false.
  3. עבור מחסנית 1: [1, 2] ומחסנית 2: [1, 2, 3], הפונקציה תחזיר false.
  4. עבור מחסנית 1: [] ומחסנית 2: [], הפונקציה תחזיר true.

4a2.111 הזזה מעגלית במחסנית

link

עליכם לממש פעולה בשם CircularShift אשר מקבלת שני פרמטרים:

  1. stack - מחסנית של מספרים שלמים (מסוג Stack).
  2. n - מספר שלם המייצג את כמות האיברים שיש להזיז מראש המחסנית לתחתיתה.

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

דגשים:

  1. השתמשו במחלקה Unit4.CollectionsLib.Stack ובמחלקה Unit4.CollectionsLib.Queue כעזר.
  2. הפעולה אינה מחזירה ערך (void).
  3. אין צורך לטפל במקרים שבהם n גדול מגודל המחסנית או שלילי. הניחו ש-n תמיד חוקי וקטן או שווה למספר האיברים במחסנית.
  4. מי שהיה בראש המחסנית מבין n האיברים שיועברו, יהיה העליון מבין המספרים שיועברו לתחתית.

לצורך פתרון התרגיל, עליכם להשתמש ב-using Unit4.CollectionsLib;.

דוגמאות:

עבור מחסנית [5, 4, 3, 2, 1] (כאשר 5 בראש) ו-n = 2:

  1. נוציא 5, 4. המחסנית: [3, 2, 1]. התור: [5, 4]
  2. נעביר 3, 2, 1 לתור. המחסנית: []. התור: [5, 4, 3, 2, 1]
  3. נחזיר 3, 2, 1 למחסנית. המחסנית: [1, 2, 3]. התור: [5, 4]
  4. נוסיף 5, 4 לתחתית המחסנית. המחסנית הסופית: [1, 2, 3, 4, 5] (כאשר 1 בראש).

עבור מחסנית [10, 20, 30] (כאשר 10 בראש) ו-n = 1:

  1. נוציא 10. המחסנית: [20, 30]. התור: [10]
  2. נעביר 20, 30 לתור. המחסנית: []. התור: [10, 20, 30]
  3. נחזיר 20, 30 למחסנית. המחסנית: [30, 20]. התור: [10]
  4. נוסיף 10 לתחתית המחסנית. המחסנית הסופית: [30, 20, 10] (כאשר 30 בראש).

4a2.111 פיענוח מחסנית מקודדת

link

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

פורמט המחסנית המקודדת:

  1. המחסנית המקורית מכילה זוגות של ערכים: (value, count).
  2. הערך התחתון בכל זוג הוא value (הערך עצמו).
  3. הערך העליון בכל זוג הוא count (מספר הפעמים שה-value צריך להופיע במחסנית המפוענחת).
  4. לדוגמה, אם המחסנית (מהתחתית לראש) היא A,B,C,D, אז A הוא ערך, B הוא מספר החזרות שלו, C הוא ערך, ו-D הוא מספר החזרות שלו.

הפונקציה צריכה לבצע את הפעולות הבאות:

  1. לקבל מחסנית מקודדת.
  2. ליצור מחסנית חדשה שתכיל את הנתונים המפוענחים.
  3. עבור כל זוג (value, count) במחסנית המקור, יש לדחוף את value למחסנית החדשה count פעמים.
  4. יש לשמור על הסדר היחסי של הערכים במחסנית המפוענחת כפי שהם מופיעים במחסנית המקורית (מהתחתית לראש).
  5. חשוב: יש להחזיר את המחסנית המקורית למצבה הראשוני לאחר סיום הפעולה.

הנחיות נוספות:

  1. השתמשו במחלקת Stack מתוך Unit4.CollectionsLib.
  2. המחסנית המקורית תכיל תמיד מספר זוגי של איברים.

דוגמאות:

מחסנית מקורית (מהתחתית לראש): 2,5,3,3,1,2

  1. זוגות (מהתחתית לראש): (2,5), (3,3), (1,2)
  2. פירוש: המספר 2 יופיע 5 פעמים, המספר 3 יופיע 3 פעמים, המספר 1 יופיע 2 פעמים.
  3. מחסנית חדשה (מהתחתית לראש): 2,2,2,2,2,3,3,3,1,1

מחסנית מקורית (מהתחתית לראש): 7,1,8,2

  1. זוגות (מהתחתית לראש): (7,1), (8,2)
  2. פירוש: המספר 7 יופיע 1 פעם, המספר 8 יופיע 2 פעמים.
  3. מחסנית חדשה (מהתחתית לראש): 7,8,8

4a2.111 קידוד מחסנית בשיטת אורך-רצף (RLE)

link

עליכם לממש פונקציה בשם EncodeStackRLE אשר מקבלת מחסנית של מספרים שלמים (Stack) כפרמטר.

הפונקציה צריכה לבצע את הפעולות הבאות:

  1. ליצור מחסנית חדשה (Stack) שתכיל את הקידוד בשיטת אורך-רצף (Run-Length Encoding - RLE).
  2. עבור כל רצף של ערכים זהים במחסנית המקורית, יש לדחוף למחסנית החדשה זוג של ערכים:
  3. הערך עצמו (בתחתית הזוג).
  4. מספר ההופעות שלו (מעל הערך).
  5. לדוגמה, אם יש רצף של שלושה 5s, יש לדחוף למחסנית החדשה את 5 ואז את 3.
  6. הסדר היחסי של הרצפים במחסנית המקורית חייב להישמר במחסנית החדשה. כלומר, אם רצף A הופיע לפני רצף B במחסנית המקורית (מהתחתית לראש), הזוג המייצג את A יופיע לפני הזוג המייצג את B במחסנית החדשה (מהתחתית לראש).
  7. לאחר סיום הקידוד, יש להחזיר את המחסנית המקורית למצבה הראשוני.
  8. הפונקציה תחזיר את המחסנית החדשה המקודדת.

דגשים:

  1. השתמשו במחלקת Stack מהספרייה Unit4.CollectionsLib.
  2. שימו לב שיש צורך לשמור על סדר הרצפים, מה שידרוש חשיבה על אופן הטיפול במחסניות.
  3. הקפידו להחזיר את המחסנית המקורית למצבה המקורי בסיום הפעולה.

דוגמאות:

מחסנית מקורית (מהתחתית לראש): 2,2,2,2,2,3,3,3,1,1 מחסנית חדשה (מהתחתית לראש): 2,5,3,3,1,2

הסבר:

רצף של חמישה 2s: יוכנסו 2 (ערך), 5 (מונה).

רצף של שלושה 3s: יוכנסו 3 (ערך), 3 (מונה).

רצף של שני 1s: יוכנסו 1 (ערך), 2 (מונה).

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

מחסנית מקורית (מהתחתית לראש): 7,7,7,7 מחסנית חדשה (מהתחתית לראש): 7,4

מחסנית מקורית (מהתחתית לראש): 1,2,3,4 מחסנית חדשה (מהתחתית לראש): 1,1,2,1,3,1,4,1