ex5a2 תורים Queue

תור: Queue תרגילים מתקדמים

5a2.1 סידור תור: שליליים תחילה, חיוביים אחריהם

link

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

  1. queue - תור של מספרים שלמים (מסוג Queue) שיש לשנות.

הפונקציה צריכה לשנות את התור הקיים (פעולה על הפניה) כך שיתקיימו התנאים הבאים:

  1. כל המספרים השליליים יופיעו בתחילת התור.
  2. כל המספרים החיוביים (כולל 0) יופיעו בסוף התור.
  3. הסדר היחסי של המספרים השליליים בינם לבין עצמם חייב להישמר.
  4. הסדר היחסי של המספרים החיוביים בינם לבין עצמם חייב להישמר.

הפעולה אינה מחזירה ערך (void).

דגשים:

  1. יש להשתמש במחלקה Queue מהספרייה Unit4.CollectionsLib.
  2. נסו לפתור את הבעיה בדרך היעילה ביותר האפשרית מבחינת זמן ריצה ושימוש בזיכרון.

דוגמאות:

  1. עבור התור: [5, -2, 8, -1, 0, 3] הפונקציה תשנה את התור ל: [-2, -1, 5, 8, 0, 3] (שימו לב: 0 נחשב למספר חיובי לצורך תרגיל זה, או שניתן לטפל בו בנפרד ולשים אותו עם החיוביים)
  2. עבור התור: [-10, -5, -20] הפונקציה תשנה את התור ל: [-10, -5, -20]
  3. עבור התור: [1, 2, 3] הפונקציה תשנה את התור ל: [1, 2, 3]

5a2.2 הפיכת סדר איברים בתור

link

עליכם לממש פעולה סטטית בשם ReverseQueue במחלקה Solution. הפעולה תקבל פרמטר אחד:

  1. queue - תור של מספרים שלמים (מסוג Queue) שיש להפוך את סדר איבריו.

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

דרישות:

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

שימו לב:

  1. בניגוד לכלל הרגיל, בתרגיל זה מותר לשנות את התור שהתקבל כפרמטר, מכיוון שזו מטרת הפעולה.

link

דוגמאות:

  1. עבור התור: [1, 2, 3, 4, 5] (כאשר 1 הוא ראש התור), לאחר הפעלת הפעולה, התור יהיה: [5, 4, 3, 2, 1] (כאשר 5 הוא ראש התור).
  2. עבור התור: [‘A’, ‘B’, ‘C’] (כאשר ‘A’ הוא ראש התור), לאחר הפעלת הפעולה, התור יהיה: [‘C’, ‘B’, ‘A’] (כאשר ‘C’ הוא ראש התור).

5a2.3 בדיקת פלינדרום בתור

link

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

  1. q - תור (מסוג Queue) המכיל איברים מטיפוס גנרי T.

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

דרישות:

  1. הפונקציה תחזיר true אם התור הוא פלינדרום, ו-false אחרת.
  2. חשוב: בתום פעולת הפונקציה, התור המקורי (q) צריך להישאר ללא שינוי (כלומר, עם אותם איברים ובאותו סדר כמו לפני הקריאה לפונקציה).
  3. יש להשתמש במחלקה Queue מהספרייה Unit4.CollectionsLib.
  4. מומלץ לפתור את הבעיה בדרך היעילה ביותר האפשרית.

שימוש במחלקה Queue:

כדי להשתמש במחלקה Queue ב-C#, יש להוסיף את השורה הבאה בתחילת הקובץ:

using Unit4.CollectionsLib; מתודות עיקריות של Queue:

  1. void Insert(T x): מכניס איבר לסוף התור.
  2. T Remove(): מוציא ומחזיר את האיבר מראש התור.
  3. T Head(): מחזיר את האיבר מראש התור מבלי להוציאו.
  4. bool IsEmpty(): מחזיר true אם התור ריק, false אחרת.

דוגמאות:

  1. עבור התור: [1, 2, 3, 2, 1] -> הפונקציה תחזיר: true
  2. עבור התור: [a, b, c, b, a] -> הפונקציה תחזיר: true
  3. עבור התור: [1, 2, 3, 4, 5] -> הפונקציה תחזיר: false
  4. עבור התור: [a, b, b, a] -> הפונקציה תחזיר: true

5a2.4 ספירת איברים באופן רקורסיבי

link

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

  1. queue - תור (מסוג Queue) המכיל מספרים שלמים.

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

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

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

דוגמאות:

  1. עבור תור: [1, 2, 3, 4, 5], הפונקציה תחזיר: 5
  2. עבור תור: [“a”, “b”, “c”], הפונקציה תחזיר: 3
  3. עבור תור ריק: [], הפונקציה תחזיר: 0

5a2.5 בדיקת קיום איבר באופן רקורסיבי

link

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

  1. q - תור (מסוג Queue) של מספרים שלמים.
  2. element - מספר שלם לבדיקה.

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

דגשים חשובים:

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

דוגמאות:

  1. עבור התור [1, 2, 3, 4, 5] והאיבר 3, הפונקציה תחזיר true.
  2. עבור התור [10, 20, 30] והאיבר 5, הפונקציה תחזיר false.
  3. עבור תור ריק [] והאיבר 7, הפונקציה תחזיר false.
  4. עבור התור [7, 8, 9] והאיבר 7, הפונקציה תחזיר true.

5a2.6 מיזוג תורים: Q1 לתוך Q2

link

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

  1. q1 - תור של שמות של אנשים (Queue
  2. q2 - תור של שמות של אנשים (Queue

הפונקציה צריכה למזג את התור q1 לתוך התור q2 על פי הכללים הבאים:

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

הגבלות:

  1. ניתן להשתמש רק בפעולות הבסיסיות על תור: Insert, Remove, Head, IsEmpty.
  2. אין להשתמש בתור נוסף או בכל מבנה נתונים אחר (כגון רשימה, מחסנית, מערך זמני).
  3. יש להשתמש במחלקה Queue הנמצאת ב-Unit4.CollectionsLib.

using Unit4.CollectionsLib;

public class Solution

{

public static Queue

{

// כתבו את הקוד שלכם כאן

}

}

דוגמאות:

  1. עבור Q1 = [1, 2, 3] ו-Q2 = [A, B, C, D], הפלט יהיה: Q2 = [A, 1, B, 2, C, 3, D]
  2. עבור Q1 = [10, 20] ו-Q2 = [X, Y], הפלט יהיה: Q2 = [X, 10, Y, 20]
  3. עבור Q1 = [1, 2, 3, 4, 5] ו-Q2 = [A, B], הפלט יהיה: Q2 = [A, 1, B, 2, 3, 4, 5]
  4. עבור Q1 = [] ו-Q2 = [A, B, C], הפלט יהיה: Q2 = [A, B, C]

5a2.7 פיענות הודעת רדיו סודית

link

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

  1. lettersQueue - תור של תווים (char) המייצג את אותיות ההודעה.
  2. lengthsQueue - תור של מספרים שלמים (int) המייצג את אורכי המילים.

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

דגשים:

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

link

דוגמאות:

  1. קלט:
  2. תור אותיות: [‘W’, ‘E’, ‘A’, ‘R’, ‘E’, ‘A’, ‘R’, ‘R’, ‘I’, ‘V’, ‘I’, ‘N’, ‘G’, ‘I’, ‘N’, ‘T’, ‘O’, ‘K’, ‘Y’, ‘O’]
  3. תור אורכים: [2, 3, 8, 2, 5]פלט:

WE ARE ARRIVING IN TOKYO

  1. קלט:
  2. תור אותיות: [‘H’, ‘E’, ‘L’, ‘L’, ‘O’]
  3. תור אורכים: [5]פלט:

HELLO

  1. קלט:
  2. תור אותיות: [‘T’, ‘E’, ‘S’, ‘T’]
  3. תור אורכים: [2, 3] (אין מספיק אותיות למילה השנייה)פלט:

ERROR