מדעי המחשב - מבני נתונים - java

מחלקת נקודה

בנה מחלקה בשם Point שמייצגת נקודה במישור. המחלקה תכלול: • שתי תכונות פרטיות: x ו-y (מספרים שלמים). • בנאי שמקבל x ו-y. • פעולות מאחזרות ל-x ול-y. • פעולה distanceTo שמקבלת נקודה אחרת ומחזירה את המרחק ביניהן (מספר ממשי). • פעולת toString שמחזירה את הנקודה בפורמט (x,y). דוגמה: נקודה (0,0) ונקודה (3,4) — המרחק ביניהן 5.0

מחלקת שעה

בנה מחלקה בשם Hour שמייצגת שעה ביממה. המחלקה תכלול: • שתי תכונות פרטיות: hour (0-23) ו-minutes (0-59). • בנאי שמקבל שעה ודקות. • פעולות מאחזרות לשתיהן. • פעולה addMinutes שמקבלת מספר דקות ומקדמת את השעה בהתאם. • פעולת toString שמחזירה את השעה בפורמט hh:mm, תמיד בשתי ספרות. דוגמאות: 09:45 ועוד 30 דקות → 10:15 23:50 ועוד 20 דקות → 00:10 08:00 ועוד 125 דקות → 10:05 הנחיות: • הדרך הנוחה: להמיר הכול לדקות מתחילת היממה, לחבר, ואז לפרק בחזרה בעזרת / ו-%. • מעבר חצות — התוצאה חוזרת לתחילת היממה. השתמש ב-%24 על השעות. • שעה חד-ספרתית חייבת לצאת עם אפס מוביל: 9 נכתב 09. ```ds:table {"title":"דוגמאות","rows":[["שעה","תוספת","תוצאה"],["09:45","30","10:15"],["23:50","20","00:10"],["08:00","125","10:05"],["00:00","0","00:00"]]} ```

מחלקת חשבון בנק

בנה מחלקה בשם BankAccount שמייצגת חשבון בנק. המחלקה תכלול: • תכונות פרטיות: שם בעל החשבון ויתרה. • בנאי שמקבל שם ויתרה התחלתית. • פעולה deposit(amount) שמוסיפה ליתרה. סכום שאינו חיובי — מתעלמים ממנו. • פעולה withdraw(amount) שמחזירה true אם המשיכה בוצעה. משיכה גדולה מהיתרה או סכום שאינו חיובי — מוחזר false והיתרה לא משתנה. • פעולה מאחזרת ליתרה. זו הנקודה של התרגיל: המחלקה אחראית לכך שהיתרה לעולם לא תהיה שלילית. ```ds:table {"title":"מסלול הבדיקה, שורה אחר שורה","rows":[["פעולה","מה מוחזר","היתרה אחרי"],["יתרה התחלתית 100","—","100"],["deposit(50)","—","150"],["withdraw(200)","false","150"],["withdraw(150)","true","0"],["deposit(-10)","—","0"]]} ```

בנאי העתקה והשוואת עצמים

נתונה המחלקה Book עם שתי תכונות פרטיות: כותרת ושנה. השלם אותה כך שתכלול: • בנאי רגיל שמקבל כותרת ושנה. • **בנאי העתקה** — בנאי שמקבל ספר קיים ובונה ממנו ספר חדש עם אותם ערכים. • פעולת setYear שמשנה את השנה. • פעולה sameAs שמקבלת ספר אחר ומחזירה true אם שני הספרים בעלי אותה כותרת ואותה שנה. הנחיות: • השוואת מחרוזות נעשית ב-equals ולא ב-== . השוואה ב-== משווה הפניות, ולכן היא עלולה להחזיר false על שתי מחרוזות זהות. • זו בדיוק הנקודה של התרגיל: `Book b = a;` אינו העתקה — שני השמות מצביעים על אותו עצם, ושינוי דרך אחד נראה גם דרך השני. בנאי העתקה יוצר עצם **חדש**, ולכן שינוי בו אינו משפיע על המקור. • sameAs משווה ערכים, לא הפניות. שני עצמים נפרדים עם אותם ערכים — התשובה true. ```ds:table {"title":"הבדיקה שבקוד","rows":[["שלב","a","עותק","sameAs"],["אחרי ההעתקה","Dune 1965","Dune 1965","true"],["אחרי setYear(2000) על העותק","Dune 1965","Dune 2000","false"]]} ```

מונה עצמים

בנה מחלקה בשם Ticket שמייצגת כרטיס בתור. המחלקה תכלול: • תכונה **סטטית** פרטית counter, שמתחילה מ-0 ומשותפת לכל הכרטיסים. • תכונה פרטית רגילה id, ייחודית לכל כרטיס. • בנאי בלי פרמטרים שמקדם את המונה ב-1 ומציב את ערכו כ-id של הכרטיס החדש. הכרטיס הראשון מקבל 1, השני 2, וכן הלאה. • פעולה מאחזרת ל-id. • פעולה **סטטית** getCount שמחזירה כמה כרטיסים נוצרו עד כה. הנחיות: • תכונה סטטית שייכת למחלקה, לא לעצם. יש ממנה עותק אחד בלבד, וכל העצמים רואים אותו. • פעולה סטטית נקראת על שם המחלקה ולא על עצם: Ticket.getCount(). • פעולה סטטית אינה יכולה לגשת לתכונה שאינה סטטית — נסה ותראה מה הקומפיילר אומר. זו הנקודה של התרגיל. ```ds:table {"title":"מה קורה בכל יצירה","rows":[["יצירה","counter אחרי","id שהוקצה"],["ראשונה","1","1"],["שנייה","2","2"],["שלישית","3","3"]]} ```

מערך של עצמים

נתונה המחלקה Product עם שתי תכונות פרטיות: שם ומחיר. השלם את המחלקה, ואז כתוב **שתי פעולות חיצוניות** (סטטיות) שמקבלות מערך של מוצרים: 1. פעולה שמחזירה את המוצר היקר ביותר. 2. פעולה שמקבלת גם מחיר סף, ומחזירה כמה מוצרים יקרים ממנו. הנחיות: • פעולה חיצונית אינה יכולה לגשת לתכונות הפרטיות ישירות — היא חייבת לעבור דרך הפעולות המאחזרות. זו הנקודה של התרגיל. • אתחל את "היקר ביותר" לאיבר הראשון במערך, לא ל-null ולא למחיר 0. • אפשר להניח שהמערך אינו ריק בפעולה הראשונה. • השוואת מחירים היא השוואת מספרים; אל תשווה שמות. ```ds:table {"title":"המוצרים שבדוגמה","rows":[["שם","מחיר"],["Pen","12.5"],["Book","89.0"],["Bag","150.0"],["Cup","30.0"]]} ```

עצם מורכב — חניון

המחלקה Hour נתונה לך **מוכנה** — אל תשנה אותה. יש לה שעה, דקות, ופעולה toMinutes שמחזירה כמה דקות עברו מתחילת היממה. בנה מחלקה בשם Parking שמייצגת חנייה אחת: • תכונה פרטית id (מחרוזת — מספר הרכב). • שתי תכונות פרטיות מטיפוס **Hour**: שעת כניסה ושעת יציאה. • בנאי שמקבל id ושתי שעות. • פעולות מאחזרות ל-id ולשעת הכניסה. • פעולה totalMinutes שמחזירה כמה דקות ארכה החנייה. ובנוסף, **פעולה חיצונית** (סטטית) שמקבלת מערך חניות ומחזירה את החנייה הארוכה ביותר. דוגמה: כניסה 08:30, יציאה 10:00 → 90 דקות. הנחיות: • תכונה יכולה להיות עצם, לא רק מספר או מחרוזת. זו הנקודה של התרגיל. • אל תשכפל את החישוב של Hour בתוך Parking — קרא ל-toMinutes. אורך החנייה הוא הפרש שתי התוצאות. • הנח שהיציאה מאוחרת מהכניסה, באותה יממה. • הפעולה החיצונית מחזירה את **העצם** Parking, לא את מספר הדקות. ```ds:table {"title":"החניות שבדוגמה","rows":[["רכב","כניסה","יציאה","דקות"],["11-111-11","08:30","10:00","90"],["22-222-22","09:00","09:45","45"],["33-333-33","06:00","12:00","360"]]} ```

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

נתונה המחלקה Competitor עם שם וזמן ריצה בשניות. בנה מחלקה בשם Race שמנהלת את המתחרים במרוץ: • תכונה פרטית: מערך של מתחרים בגודל קבוע (הגודל מתקבל בבנאי). • תכונה פרטית: count — כמה מתחרים נרשמו בפועל. • בנאי שמקבל את הגודל המרבי. • פעולה add שמקבלת מתחרה ומוסיפה אותו. אם המערך מלא — אין להוסיף, והפעולה מחזירה false. אחרת מוסיפה ומחזירה true. • פעולה fastest שמחזירה את המתחרה המהיר ביותר, או null אם אין מתחרים כלל. • פעולה average שמחזירה את זמן הריצה הממוצע, או 0 אם אין מתחרים. הנחיות: • count אינו אורך המערך. הלולאות חייבות לרוץ עד count ולא עד arr.length — אחרת יגיעו לתאים ריקים. זו הנקודה המרכזית כאן. • מהיר ביותר = הזמן הנמוך ביותר. • אל תשכח לקדם את count אחרי כל הוספה מוצלחת. • בדוק מקרה של מרוץ ריק לפני שאתה ניגש לאיבר הראשון. ```ds:table {"title":"המתחרים שבדוגמה","rows":[["שם","זמן"],["Dan","52.4"],["Rita","48.9"],["Omer","61.0"]]} ```

הורשה ראשונה

נתונה המחלקה Person עם תכונה פרטית אחת: שם. בנה מחלקה בשם Student **שיורשת** מ-Person ומוסיפה תכונה אחת: ציון. המחלקה Student תכלול: • בנאי שמקבל שם וציון, ומעביר את השם לבנאי של האב. • פעולה מאחזרת לציון. • דריסה של הפעולה describe: היא תחזיר את השם, רווח, ואז את הציון בסוגריים. דוגמאות: Person בשם Dana → describe מחזיר Dana Student בשם Yossi, 95 → describe מחזיר Yossi (95) הנחיות: • השם שמור בתכונה **פרטית** של האב, ולכן Student אינו יכול לגשת אליו ישירות. הוא ניגש אליו דרך הפעולה המאחזרת שהאב מספק. זו הנקודה המרכזית בתרגיל. • הקריאה לבנאי האב חייבת להיות השורה הראשונה בבנאי של הבן. • אל תשכפל את התכונה name לתוך Student. אם עשית זאת — ההורשה לא נוצלה, ויש שני שמות שונים באותו עצם. ```ds:table {"title":"הפלט הצפוי","rows":[["עצם","describe"],["Person(\"Dana\")","Dana"],["Student(\"Yossi\", 95)","Yossi (95)"],["Student(\"Noa\", 100)","Noa (100)"]]} ```

קריאה לפעולת האב

בנה שלוש מחלקות בשרשרת הורשה: • A — תכונה פרטית a, ופעולה getSum שמחזירה את a. • B — יורשת מ-A, מוסיפה תכונה b, ו-getSum שלה מחזירה a+b. • C — יורשת מ-B, מוסיפה תכונה c, ו-getSum שלה מחזירה a+b+c. המפתח: **אף מחלקה אינה מחשבת מחדש את הסכום של הרמות שמעליה.** כל אחת קוראת לגרסה של האב ומוסיפה עליה את התכונה שלה בלבד. דוגמה עבור C שנבנה עם a=1, b=2, c=3: getSum מחזיר 6 הנחיות: • קריאה לגרסה של האב מתוך הדריסה נעשית ב-super בג׳אווה וב-base ב-C#. בלעדיה, קריאה סתם ל-getSum בתוך getSum היא קריאה עצמית אינסופית. • כל בנאי מעביר לאב את מה ששייך לאב. • התכונות פרטיות בכל רמה, ואף אחת מהן אינה מוגדרת פעמיים. ```ds:table {"title":"התוצאות הצפויות","rows":[["עצם","getSum"],["A(5)","5"],["B(1,2)","3"],["C(1,2,3)","6"],["A x = C(4,5,6)","15"]]} ```

מערך צורות

נתונה המחלקה **המופשטת** Shape עם פעולה מופשטת area ופעולה מופשטת name. מחלקה מופשטת אינה ניתנת ליצירה — היא רק מגדירה מה כל צורה חייבת לדעת לעשות. בנה שתי מחלקות שיורשות ממנה: • Circle — תכונה radius. השטח: π·r². השם: circle. • Rect — תכונות width ו-height. השטח: מכפלה. השם: rect. ובנוסף, **פעולה חיצונית** שמקבלת מערך של Shape ומחזירה את הצורה בעלת השטח הגדול ביותר. הנחיות: • השתמש ב-Math.PI ולא ב-3.14. • הפעולה החיצונית אינה יודעת ואינה צריכה לדעת באיזו צורה מדובר — היא קוראת ל-area, והשפה בוחרת בזמן ריצה את המימוש הנכון. זו כל מהות הפולימורפיזם, ולכן אין בפעולה הזו שום בדיקת טיפוס. • אתחל את המקסימום לאיבר הראשון. ```ds:table {"title":"הצורות שבדוגמה","rows":[["צורה","נתונים","שטח"],["circle","r=2","12.566..."],["rect","4×5","20.0"],["circle","r=1","3.141..."],["rect","2×3","6.0"]]} ```

ספירת טיפוסים במערך פולימורפי

נתונה שרשרת ההורשה A → B → C (B יורשת מ-A, ו-C יורשת מ-B). נתון מערך מטיפוס A שמכיל עצמים משלושת הטיפוסים. כתוב פעולה חיצונית שמדפיסה שלוש שורות — כמה איברים במערך הם **בדיוק** מטיפוס A, כמה בדיוק B, וכמה בדיוק C, בסדר הזה. **עצם מטיפוס C לא ייספר כ-B, ולא כ-A.** הנחיות: • זו המלכודת: הבדיקה `x instanceof B` מחזירה true גם עבור עצם מטיפוס C, כי C הוא סוג של B. אותו דבר עם `is` ב-C#. • לכן הבדיקות חייבות להיות בשרשרת if-else שמתחילה מהטיפוס **הספציפי ביותר** ויורדת כלפי מעלה: קודם C, אחר כך B, ולבסוף A. ברגע שאחת התאימה, השאר לא נבדקות. • שרשרת של if-ים נפרדים במקום if-else תספור כל עצם C שלוש פעמים. • נסה בכוונה את הסדר ההפוך ותראה מה מתקבל — זו הדרך הטובה ביותר להבין את התרגיל. ```ds:table {"title":"המערך שבדוגמה — שבעה איברים","rows":[["אינדקס","0","1","2","3","4","5","6"],["טיפוס","A","C","B","C","A","B","C"]]} ``` ```ds:table {"title":"הפלט הצפוי","rows":[["טיפוס","כמות"],["A בדיוק","2"],["B בדיוק","2"],["C בדיוק","3"]]} ```

תשבץ · מבני נתונים — מושגי יסוד

עצרת ברקורסיה

כתוב פעולה **רקורסיבית** שמקבלת מספר שלם n ומחזירה את n! (עצרת). n! = n × (n-1) × (n-2) × ... × 1 0! = 1 דוגמאות: 5 → 120 1 → 1 0 → 1 הנחיות: • בלי לולאות בכלל. הפעולה חייבת לקרוא לעצמה. • התחל מהשאלה: מהו מקרה הבסיס שבו הרקורסיה נעצרת? ```ds:table {"title":"מה הפעולה מחזירה","rows":[["n","התוצאה"],["0","1 — מקרה הבסיס"],["1","1"],["3","6"],["5","120"]]} ```

חזקה ברקורסיה

כתוב פעולה **רקורסיבית** שמקבלת בסיס base ומעריך exp (שלם ואי-שלילי) ומחזירה את base בחזקת exp. דוגמאות: 2, 5 → 32 7, 1 → 7 5, 0 → 1 0, 3 → 0 הנחיות: • מקרה הבסיס: כל מספר בחזקת 0 שווה 1. • צעד הרקורסיה: base בחזקת exp = base כפול (base בחזקת exp-1). • שים לב שרק exp קטן בכל קריאה — base נשאר כפי שהוא. זה ההבדל מהעצרת, שבה הפרמטר היחיד הוא זה שקטן. • אסור להשתמש בלולאה וב-Math.pow. ```ds:table {"title":"פריסת הקריאות עבור 2 בחזקת 3","rows":[["קריאה","מחזירה"],["power(2,3)","2 * power(2,2) = 8"],["power(2,2)","2 * power(2,1) = 4"],["power(2,1)","2 * power(2,0) = 2"],["power(2,0)","1"]]} ```

סכום ספרות ברקורסיה

כתוב פעולה **רקורסיבית** שמקבלת מספר שלם חיובי ומחזירה את סכום ספרותיו. דוגמאות: 472 → 13 9 → 9 1000 → 1 הנחיות: • בלי לולאות ובלי המרה למחרוזת. • רמז: הספרה האחרונה היא n%10, ושאר המספר הוא n/10.

האם הספרה נמצאת במספר

כתוב פעולה **רקורסיבית** שמקבלת מספר שלם אי-שלילי n וספרה d, ומחזירה true אם הספרה מופיעה במספר. דוגמאות: 4721, 7 → true 4721, 3 → false 5, 5 → true 0, 0 → true הנחיות: • הספרה האחרונה של n היא n%10, והמספר בלי הספרה האחרונה הוא n/10. • מקרה הבסיס: כשנשאר מספר בן ספרה אחת — בודקים אותו ומסיימים. • צעד הרקורסיה: הספרה נמצאת אם היא הספרה האחרונה **או** אם היא נמצאת בשאר המספר. שים לב שזה "או" — ולכן התשובה עולה מהקריאה הרקורסיבית ולא נזרקת. • אסור להשתמש בלולאה ובהמרה למחרוזת. ```ds:table {"title":"פריסת הקריאות עבור 4721 וספרה 7","rows":[["קריאה","ספרה אחרונה","תוצאה"],["f(4721,7)","1","1==7? לא → f(472,7)"],["f(472,7)","2","לא → f(47,7)"],["f(47,7)","7","כן → true"]]} ```

הדפסת מערך מהסוף להתחלה

כתוב **שתי** פעולות רקורסיביות שמקבלות מערך ואינדקס התחלה: 1. פעולה שמדפיסה את המערך מההתחלה לסוף. 2. פעולה שמדפיסה אותו מהסוף להתחלה. כל איבר בשורה נפרדת. אסור להשתמש בלולאה בכלל. הנחיות: • שתי הפעולות כמעט זהות. ההבדל היחיד: האם ההדפסה מתבצעת **לפני** הקריאה הרקורסיבית או **אחריה**. • זו הנקודה של התרגיל, ולכן כדאי לכתוב את הראשונה, להריץ, ואז לשנות רק את סדר שתי השורות ולראות מה קורה. • מקרה הבסיס: האינדקס הגיע לאורך המערך — אין מה להדפיס. ```ds:array {"title":"הקלט — הפלט ההפוך יהיה 9, 7, 5, 3","items":["3","5","7","9"]} ```

פלינדרום ברקורסיה

כתוב פעולה **רקורסיבית** שמקבלת מחרוזת ומחזירה true אם היא פלינדרום (נקראת אותו דבר משני הכיוונים). דוגמאות: "abba" → true "abcba" → true "abc" → false "" → true הנחיות: • בלי לולאות ובלי היפוך המחרוזת. • רמז: אם התו הראשון והאחרון שווים — הבעיה מצטמצמת למחרוזת שביניהם. ```ds:table {"title":"דוגמאות","rows":[["מחרוזת","פלינדרום?","למה"],["abba","כן","אורך זוגי"],["abcba","כן","אורך אי-זוגי — האמצע לא נבדק"],["abc","לא","a מול c"],["ריקה","כן","מקרה בסיס"]]} ```

האיבר ה-n בפיבונאצ׳י

סדרת פיבונאצ׳י מתחילה ב-0 ו-1, וכל איבר הוא סכום שני קודמיו: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... כתוב פעולה שמקבלת n ומחזירה את האיבר ה-n בסדרה (הספירה מתחילה מ-0). דוגמאות: n=0 → 0 n=1 → 1 n=7 → 13 הנחיות: • פתור בלולאה עם שני משתנים בלבד, בלי רקורסיה ובלי מערך. ```ds:array {"title":"הסדרה — האינדקס מתחת לכל איבר","items":["0","1","1","2","3","5","8","13","21","34","55"]} ```

כמה דרכים לעלות במדרגות

סולם בן n מדרגות. בכל צעד אפשר לעלות מדרגה אחת או שתי מדרגות. כתוב פעולה **רקורסיבית** שמחזירה בכמה דרכים שונות אפשר להגיע לראש הסולם. דוגמה עבור n=4 — חמש דרכים: 1+1+1+1 · 1+1+2 · 1+2+1 · 2+1+1 · 2+2 הנחיות: • חשוב על הצעד **האחרון**: או שהוא היה מדרגה אחת (ואז לפניו היו n-1 מדרגות), או שתיים (ואז n-2). לכן הדרכים ל-n הן סכום שתי האפשרויות. • מקרי בסיס: לסולם בן 0 מדרגות יש דרך אחת (לא לזוז), ולסולם בן מדרגה אחת יש דרך אחת. • אחרי שתפתור — הסתכל על סדרת התוצאות. היא מוכרת לך מתרגיל אחר בספרייה. נסה להסביר לעצמך למה. ```ds:table {"title":"התוצאות הראשונות","rows":[["n","0","1","2","3","4","5","6"],["דרכים","1","1","2","3","5","8","13"]]} ```

מדריך רקורסיה ב-Java

רקורסיה — סוגים, מעקב ומלכודות

רקורסיה — חידון סיכום

חיפוש סדרתי

כתוב פעולה שמקבלת מערך של מספרים שלמים וערך לחיפוש, ומחזירה את האינדקס של המופע הראשון של הערך. אם הערך אינו במערך — החזר 1-. דוגמאות עבור [8, 3, 9, 3]: חיפוש 9 → 2 חיפוש 3 → 1 (המופע הראשון) חיפוש 5 → -1 הנחיות: • המערך אינו ממוין, ולכן אין ברירה אלא לעבור עליו. • צא מהפעולה ברגע שנמצא — אין טעם להמשיך. • 1- הוא ערך מוסכם ל"לא נמצא", כי הוא לעולם אינו אינדקס חוקי. אחרי שתפתור, שים לב: כמה השוואות בממוצע דורש החיפוש הזה על מערך בגודל n? השווה למספר ההשוואות בחיפוש הבינארי. ```ds:array {"title":"המופע הראשון של 3 הוא באינדקס 1","items":["8","3","9","3"]} ```

חיפוש בינארי

כתוב פעולה שמקבלת מערך **ממוין** וערך לחיפוש, ומחזירה את האינדקס שבו הערך נמצא, או -1 אם אינו במערך. הרעיון: השווה לאיבר האמצעי. אם הוא גדול מדי — המשך לחפש בחצי השמאלי, אם קטן מדי — בחצי הימני. כך בכל צעד נחתך חצי מהמערך. דוגמאות עבור [1, 3, 5, 7, 9]: 5 → 2 1 → 0 4 → -1 הנחיות: • אסור לעבור על המערך בלולאה רגילה מההתחלה לסוף. ```ds:array {"title":"המערך הממוין — האינדקס שמתחת לכל תא הוא מה שמוחזר","items":["1","3","5","7","9"]} ```

מיון בועות

כתוב פעולה שממיינת מערך בסדר עולה בשיטת מיון בועות (Bubble Sort), בתוך אותו מערך. הרעיון: עוברים על המערך שוב ושוב, ובכל מעבר מחליפים כל זוג שכנים שאינם בסדר הנכון. אחרי כל מעבר, האיבר הגדול ביותר שנותר "צף" לסוף. דוגמה: [5, 1, 4, 2] → [1, 2, 4, 5] הנחיות: • בלי פונקציות מיון מוכנות. • הפעולה אינה מחזירה ערך — היא משנה את המערך. ```ds:array {"title":"לפני","items":["5","1","4","2"]} ``` ```ds:array {"title":"אחרי","items":["1","2","4","5"]} ```

מיון בחירה

כתוב פעולה שממיינת מערך בסדר עולה בשיטת מיון בחירה (Selection Sort). הרעיון: במקום i, חפש את האיבר הקטן ביותר מבין כל האיברים מ-i והלאה, והחלף אותו עם האיבר שבמקום i. דוגמה: [5, 1, 4, 2] → [1, 2, 4, 5] הנחיות: • בלי פונקציות מיון מוכנות. • שמור את *האינדקס* של המינימום, לא רק את הערך שלו. ```ds:array {"title":"לפני","items":["5","1","4","2"]} ``` ```ds:array {"title":"אחרי","items":["1","2","4","5"]} ```

מיון הכנסה

כתוב פעולה שממיינת מערך של מספרים שלמים בסדר עולה בשיטת **מיון הכנסה**, בתוך אותו מערך, ואז מדפיסה אותו — כל איבר בשורה נפרדת. איך זה עובד: החלק השמאלי של המערך תמיד ממוין. בכל צעד לוקחים את האיבר הבא, ומזיזים ימינה את כל האיברים הגדולים ממנו עד שנמצא מקומו. מעקב עבור [5, 2, 4]: התחלה: 5 | 2 4 מכניסים את 2: 2 5 | 4 מכניסים את 4: 2 4 5 הנחיות: • שמור את האיבר שאתה מכניס במשתנה לפני שאתה מתחיל להזיז — אחרת ההזזה תדרוס אותו. • ההבדל ממיון בועות: כאן מזיזים איברים, לא מחליפים זוגות. • אסור להשתמש בפעולת מיון מוכנה. ```ds:table {"title":"מעקב עבור [5, 2, 4]","rows":[["שלב","המערך"],["התחלה","5 2 4"],["מכניסים 2","2 5 4"],["מכניסים 4","2 4 5"]]} ```

מיזוג שני מערכים ממוינים

נתונים שני מערכים ממוינים בסדר עולה. כתוב פעולה שמחזירה מערך חדש שמכיל את כל האיברים של שניהם, ממוין בסדר עולה. דוגמה: [1, 4, 9] ו-[2, 3, 10] → [1, 2, 3, 4, 9, 10] הנחיות: • אסור לשרשר את שני המערכים ולמיין. הפתרון חייב לנצל את העובדה ששניהם כבר ממוינים, ולעבור על כל אחד מהם פעם אחת בלבד. • החזק שני מדדים, אחד לכל מערך. בכל צעד קח את הקטן מבין שני האיברים הנוכחיים וקדם רק את המדד שממנו לקחת. • כשאחד המערכים נגמר — העתק את שארית השני. אל תשכח את השלב הזה. • מערך יכול להיות ריק. ```ds:array {"title":"מערך א","items":["1","4","9"]} ``` ```ds:array {"title":"מערך ב","items":["2","3","10"]} ``` ```ds:array {"title":"התוצאה","items":["1","2","3","4","9","10"]} ```

האם המערך ממוין

כתוב פעולה שמקבלת מערך ומחזירה true אם הוא ממוין בסדר עולה (כל איבר גדול או שווה לקודמו). דוגמאות: [1, 3, 3, 7] → true [1, 5, 2] → false [4] → true הנחיות: • מספיק מעבר אחד על המערך. • ברגע שנמצאה הפרה אפשר להפסיק. ```ds:array {"title":"ממוין → true (שים לב ש-3 חוזר, וזה עדיין ממוין)","items":["1","3","3","7"]} ``` ```ds:array {"title":"לא ממוין → false (ההפרה בין 5 ל-2)","items":["1","5","2"]} ```

יעילות — סדר גודל ומה באמת נספר

יעילות — חידון סיכום

סכום מחסנית בלי לאבד אותה

כתוב פעולה שמקבלת מחסנית של מספרים שלמים ומחזירה את סכום איבריה — כשבסוף הפעולה המחסנית חוזרת למצבה המקורי, באותו סדר. דוגמה: מחסנית [3,7,2] (3 בראש) → 12, והמחסנית נשארת [3,7,2] הנחיות: • הדרך היחידה לקרוא איבר במחסנית היא להוציא אותו. השתמש במחסנית עזר כדי לשמור את מה שהוצאת, ואז החזר הכול. • pop על מחסנית ריקה זורק שגיאת ריצה — בדוק isEmpty לפני. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:stack {"title":"המחסנית שבדוגמה — הסכום 12, והיא חייבת להישאר בדיוק כך","items":["2","7","3"]} ```

הערך הגדול במחסנית

כתוב פעולה שמקבלת מחסנית של מספרים שלמים ומחזירה את הערך הגדול ביותר שבה — כשבסוף הפעולה המחסנית חוזרת למצבה המקורי, באותו סדר. אם המחסנית ריקה — החזר 1-. דוגמה: מחסנית [3,9,2] (3 בראש) → 9, והמחסנית נשארת [3,9,2] הנחיות: • אי אפשר לקרוא איבר במחסנית בלי להוציא אותו. הוצא הכול למחסנית עזר, ובדרך עקוב אחרי המקסימום. • שתי העברות מחזירות את הסדר המקורי; העברה אחת בלבד הופכת אותו. • pop על מחסנית ריקה זורק שגיאת ריצה — בדוק isEmpty לפני. • אתחל את המקסימום לאיבר הראשון שהוצאת, לא לאפס. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:stack {"title":"המחסנית שבדוגמה — המקסימום 9, והיא חייבת להישאר בדיוק כך","items":["2","9","3"]} ```

שכפול מחסנית

כתוב פעולה שמקבלת מחסנית של מספרים שלמים ומחזירה **מחסנית חדשה** זהה לה — אותם ערכים, באותו סדר. בסוף הפעולה המחסנית המקורית חייבת להיות במצבה ההתחלתי. דוגמה: מקורית [5,1,8] (5 בראש) → מוחזרת [5,1,8], והמקורית נשארת [5,1,8] הנחיות: • כל העברה בין שתי מחסניות הופכת את הסדר. שתי העברות מחזירות אותו. ספור כמה העברות אתה צריך כדי ששתי המחסניות יצאו בסדר הנכון. • השתמש במחסנית עזר אחת. אין צורך במערך ואין צורך ברשימה. • מחסנית ריקה מחזירה מחסנית ריקה. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:stack {"title":"המקורית — והעותק חייב לצאת זהה לה","items":["8","1","5"]} ```

הסרת ערך ממחסנית

כתוב פעולה שמקבלת מחסנית של מספרים שלמים וערך x, ומסירה מהמחסנית את **כל** המופעים של x — כשכל שאר האיברים נשארים בסדר המקורי שלהם. הפעולה משנה את המחסנית שהתקבלה ואינה מחזירה ערך. דוגמה: [4,7,4,1] (4 בראש), x=4 → [7,1] (7 בראש) הנחיות: • רוקן למחסנית עזר ודלג על האיברים שערכם x. • אחרי ההעברה הראשונה הסדר בעזר הפוך. העברה שנייה בחזרה מתקנת אותו. • pop על מחסנית ריקה זורק שגיאת ריצה — בדוק isEmpty לפני. • אם כל האיברים הוסרו, המחסנית תישאר ריקה. זה תקין. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:stack {"title":"לפני — x = 4","items":["1","4","7","4"]} ``` ```ds:stack {"title":"אחרי","items":["1","7"]} ```

סוגריים מאוזנים

כתוב פעולה שמקבלת מחרוזת המכילה סוגריים מסוגים ( ) [ ] { } ומחזירה true אם הם מאוזנים. מאוזן = כל סוגר נסגר בסוגר מהסוג המתאים ובסדר הנכון. דוגמאות: "([]{})" → true "([)]" → false "(()" → false "" → true הנחיות: • סוגר פותח — דוחפים למחסנית. סוגר סוגר — מוציאים ובודקים התאמה. • בסוף חייבת המחסנית להיות ריקה. • pop על מחסנית ריקה זורק שגיאת ריצה — בדוק isEmpty לפני. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:table {"title":"למה כל מחרוזת נופלת איפה שהיא נופלת","rows":[["מחרוזת","מאוזן?","הסיבה"],["([]{})","כן","כל סוגר נסגר בסוג הנכון"],["([)]","לא","סדר הסגירה שגוי — ספירה בלבד לא תתפוס את זה"],["(()","לא","נשאר סוגר פתוח בסוף"],[")(","לא","סגירה לפני שנפתח משהו"]]} ``` ```ds:stack {"title":"מצב המחסנית אחרי קריאת שני התווים ( ואז [","items":["(","["]} ```

חישוב ביטוי בכתיב פולני הפוך

בכתיב פולני הפוך (Postfix) האופרטור נכתב **אחרי** שני האופרנדים שלו, ולכן אין צורך בסוגריים כלל. דוגמאות: "23+" = 2+3 = 5 "23+5*" = (2+3)*5 = 25 "52-3*" = (5-2)*3 = 9 "7" = 7 כתוב פעולה שמקבלת מחרוזת כזו ומחזירה את ערכה. המחרוזת מכילה ספרות בודדות 0-9 והאופרטורים + - *, בלי רווחים. הנחיות: • עבור על התווים משמאל לימין. ספרה — דוחפים למחסנית. אופרטור — מוציאים **שניים**, מחשבים, ודוחפים את התוצאה בחזרה. • סדר האופרנדים חשוב: האיבר שיצא ראשון הוא הימני. עבור "52-" יוצא קודם 2 ואז 5, והחישוב הוא 5-2 ולא 2-5. • המרת תו לספרה: c - '0'. • בסוף הביטוי נשאר במחסנית איבר אחד — הוא התשובה. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:table {"title":"מעקב עבור \"23+5*\"","rows":[["תו","פעולה","המחסנית אחרי"],["2","push 2","2"],["3","push 3","2, 3"],["+","pop 3, pop 2, push 5","5"],["5","push 5","5, 5"],["*","pop 5, pop 5, push 25","25"]]} ```

מחסנית — טיפוס נתונים מופשט ראשון

מחסנית — חידון סיכום

מתי מבנה הנתונים מתפוצץ

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

סכום המחסנית — מה מיותר כאן

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

ספירת איברים בתור

כתוב פעולה שמקבלת תור של מספרים שלמים ומחזירה כמה איברים יש בו, כשבסוף הפעולה התור חוזר למצבו המקורי ובאותו סדר. דוגמה: תור [1,2,3] (1 בראש) → 3, והתור נשאר [1,2,3] הנחיות: • רמז נחמד: בתור, אם מוציאים איבר מהראש ומכניסים אותו מיד לסוף, אחרי סיבוב שלם התור חוזר בדיוק לסדרו המקורי. אין צורך בתור עזר. • remove על תור ריק זורק שגיאת ריצה — בדוק isEmpty לפני. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:queue {"title":"התור שבדוגמה — front משמאל, rear מימין","items":["1","2","3"]} ```

סכום תור של מספרים עשרוניים

ממשו את הפעולה sum שמקבלת תור של מספרים עשרוניים ומחזירה את סכום איבריו. בסיום הפעולה **התור חוזר למצבו המקורי**, באותו סדר. דוגמה: [1.5, 2.0, 0.5] → 4.0, והתור נשאר [1.5, 2.0, 0.5] הנחיות: • רשמו בהערה מעל הפעולה מהי יעילות הפעולה כפונקציה של מספר האיברים. • remove על תור ריק זורק שגיאת ריצה — בדקו isEmpty לפני. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:queue {"title":"התור — הסכום 4.0, והוא חייב להישאר כך","items":["1.5","2.0","0.5"]} ```

ספירת זוגיים בתור

ממשו את הפעולה countEven שמקבלת תור של מספרים שלמים ומחזירה כמה מאיבריו זוגיים. בסיום הפעולה התור חוזר למצבו המקורי. דוגמאות: [4, 7, 2, 9] → 2 [1, 3, 5] → 0 [] → 0 הנחיות: • אין להניח שהאיברים בתור שונים זה מזה. • רשמו בהערה מהי יעילות הפעולה. • שימו לב לאפס ולמספרים שליליים — 0 זוגי, ו--4 זוגי. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:queue {"title":"התור — שני זוגיים: 4 ו-2","items":["4","7","2","9"]} ```

העתקת תור והדפסתו

בתור אין דרך להציץ פנימה — הדרך היחידה לראות איבר היא להוציא אותו, וזה הורס את התור. לכן בונים העתק. כתבו **שתי** פעולות: 1. copyQueue(q) — מקבלת תור ומחזירה העתק שלו, כשהתור המקורי נשאר בדיוק כמו שהיה. 2. printQueue(q) — מדפיסה את איברי התור מהראש לסוף, מופרדים ברווח, בלי לפגוע בתור. **חייבת להשתמש ב-copyQueue.** דוגמה עבור התור [1,2,3] כאשר 1 בראש: 1 2 3 הנחיות: • remove על תור ריק זורק שגיאת ריצה — בדקו isEmpty לפני. • רמז ל-copyQueue: פינוי לתור עזר לא מספיק, כי אז המקורי ריק. חשבו כמה תורים אתם צריכים. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:queue {"title":"התור — front משמאל, rear מימין","items":["1","2","3"]} ```

שכפול מסונן של תור

ממשו את הפעולה cloneDiv3 שמקבלת תור של מספרים שלמים ומחזירה תור **חדש** שמכיל רק את האיברים המתחלקים ב-3 ללא שארית, לפי סדרם המקורי. התור שהתקבל נשאר בדיוק כמו שהיה. דוגמה: [9, 4, 3, 7, 12] → תור חדש [9, 3, 12] והתור המקורי נשאר [9, 4, 3, 7, 12] הנחיות: • שני תורים חוזרים מהפעולה בפועל: החדש שמוחזר, והמקורי ששוחזר. • 0 מתחלק ב-3. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:queue {"title":"המקורי — נשאר כמו שהוא","items":["9","4","3","7","12"]} ``` ```ds:queue {"title":"התור החדש שמוחזר","items":["9","3","12"]} ```

היפוך תור בעזרת מחסנית

כתוב פעולה שמקבלת תור והופכת את סדר איבריו. דוגמה: [1,2,3] → [3,2,1] הנחיות: • תור לבדו לא יכול להפוך את עצמו — הוא FIFO. מחסנית היא LIFO, וזה בדיוק ההבדל שפותר את התרגיל. • רוקן את התור לתוך מחסנית, ואז החזר מהמחסנית לתור. • הפעולה אינה מחזירה ערך — היא משנה את התור שהתקבל. ממשק מבני הנתונים כבר מצורף למשימה — גם Queue וגם Stack. ```ds:queue {"title":"לפני","items":["1","2","3"]} ``` ```ds:stack {"title":"באמצע — אחרי שרוקנת את התור לתוך מחסנית. שים לב מי בראש","items":["1","2","3"]} ``` ```ds:queue {"title":"אחרי","items":["3","2","1"]} ```

סכום ראשי התורים

ממשו את הפעולה getTopsSum. הפעולה מקבלת **שרשרת חוליות שבכל חוליה שלה יושב תור** של מספרים עשרוניים, ומחזירה את סכום האיברים שבראשי התורים. כלומר: מכל תור לוקחים רק את האיבר הראשון, ומסכמים. דוגמה: חוליה 1: תור [1.5, 9.0] → לוקחים 1.5 חוליה 2: תור [] → ריק, מדלגים חוליה 3: תור [2.5, 0.5] → לוקחים 2.5 התוצאה: 4.0 הנחיות: • **חובה שאחת החוליות תכיל תור ריק** — זה המקרה שמפיל פתרונות. head על תור ריק זורק שגיאת ריצה. • התורים חייבים להישאר במצבם המקורי. יש פעולה שמאפשרת לראות את הראש בלי להוציא אותו — מצאו אותה. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:list {"title":"השרשרת — בכל חוליה תור","items":["[1.5, 9.0]","[ ריק ]","[2.5, 0.5]"]} ``` ```ds:table {"title":"מה נלקח מכל חוליה","rows":[["חוליה","התור","ראש התור","נכנס לסכום"],["1","1.5 · 9.0","1.5","1.5"],["2","ריק","אין","0"],["3","2.5 · 0.5","2.5","2.5"],["סה\"כ","","","4.0"]]} ```

הסרת כפילויות מתור

ממשו את הפעולה removeDuplicates שמקבלת תור של מספרים שלמים ומסירה ממנו את הערכים הכפולים. מכל ערך יישאר **המופע הראשון** שלו, במקומו המקורי. דוגמה: [3, 7, 3, 1, 7, 3] → [3, 7, 1] הנחיות: • הפעולה משנה את התור שהתקבל. • מותר להשתמש בתורים נוספים, ורק בהם. • פרקו לתת-בעיות. שתי פעולות עזר שיסייעו: - contains(q, x) — האם x קיים בתור, בלי לפגוע בו. - copyQueue(q) — מחזירה העתק, בלי לפגוע במקורי. • רשמו בהערה מהי יעילות הפעולה כפונקציה של מספר האיברים בתור המקורי. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:queue {"title":"לפני","items":["3","7","3","1","7","3"]} ``` ```ds:queue {"title":"אחרי — כל ערך נשאר במקום הופעתו הראשונה","items":["3","7","1"]} ```

התור בדואר

בדואר ישראל יש תור לקבלת שירות בדלפק. על פי החוק, אזרחים בני 80 ומעלה פטורים מהתור ומקבלים שירות לפני כולם. כל השאר עומדים לפי סדר הגעתם. בנו שתי מחלקות: **Customer** — לקוח, עם חמשת יסודות המחלקה: • name — שם • age — גיל **PostOffice** — מנהלת את התור. חשבו בעצמכם על התכונות. • addCustomer(c) — מוסיפה לקוח לתור, לפי כלל הקדימות. • callCustomer() — מדפיסה את שם הלקוח הבא ומסירה אותו מהתור. אם אין לקוחות — מדפיסה "אין לקוחות בתור". בפעולה הראשית, הכניסו לפי סדר הגעה: אזרח בן 23, אזרח בן 82, אזרח בן 34. אחר כך בצעו קריאה ללקוח **ארבע** פעמים. הפלט הצפוי: דוד (בן 82 — פטור מהתור) אבי (בן 23 — הראשון מבין הרגילים) רונית (בן 34) אין לקוחות בתור הנחיות: • רמז לתכונות: תור אחד לא מספיק כדי לתת קדימות בלי לשבור את סדר ההגעה של השאר. • 80 בדיוק כלול בפטור. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:table {"title":"סדר ההגעה מול סדר השירות","rows":[["סדר הגעה","שם","גיל","פטור?","סדר שירות"],["1","אבי","23","לא","2"],["2","דוד","82","כן","1"],["3","רונית","34","לא","3"]]} ``` ```ds:queue {"title":"תור הפטורים אחרי שלוש ההוספות","items":["דוד"]} ``` ```ds:queue {"title":"תור הרגילים אחרי שלוש ההוספות","items":["אבי","רונית"]} ```

מבנה הנתונים תור?

תור — FIFO והממשק שלו

תור — חידון סיכום

היפוך תור בעזרת מחסנית — סדרו את השלבים

נתון תור q עם הערכים 1, 2, 3 (1 בראש). המטרה: שהתור יכיל 3, 2, 1. השלבים מעורבבים — סדרו אותם לאלגוריתם נכון.

מחסנית או תור — הדלפק בסניף

בסניף דואר לקוחות מקבלים מספר בכניסה ומטופלים לפי סדר ההגעה. איזה מבנה נתונים מתאים לניהול ההמתנה?

בניית שרשרת והדפסתה

שני חלקים: 1. בפעולה הראשית, בנו שרשרת חוליות עם הערכים 1 → 2 → 3 → null. בנו אותה ידנית, חוליה אחר חוליה, בלי לולאה ובלי פעולת עזר. 2. כתבו פעולה printList שמקבלת מצביע לחוליה הראשונה ומדפיסה את השרשרת בפורמט: 1 -> 2 -> 3 -> null הנחיות: • לבנייה ידנית יש שתי דרכים, ושתיהן נכונות: מהסוף להתחלה עם הבנאי Node(x, next), או מההתחלה עם setNext. • הפעולה הזו תשמש אתכם בכל שאר תרגילי השרשרת — כדאי שתעבוד. המחלקה Node כבר מצורפת למשימה. ```ds:list {"title":"השרשרת שצריך לבנות","items":["1","2","3"]} ```

ספירת חוליות בשרשרת

כתוב פעולה שמקבלת מצביע לחוליה הראשונה בשרשרת ומחזירה כמה חוליות יש בה. דוגמאות: 1 → 7 → 4 → null → 3 null → 0 הנחיות: • עבור על השרשרת עם משתנה עזר מסוג Node, והתקדם עם getNext עד null. • אל תשנה את השרשרת. • שים לב: הפעולה מקבלת Node ולא List — זו הצורה שבה השאלות מנוסחות בבגרות. המחלקה Node כבר מצורפת למשימה. ```ds:list {"title":"השרשרת שבדוגמה — שלוש חוליות","items":["1","7","4"]} ```

הערך הגדול בשרשרת

כתוב פעולה שמקבלת מצביע לחוליה הראשונה בשרשרת של מספרים שלמים, ומחזירה את הערך הגדול ביותר בה. אם השרשרת ריקה (head הוא null) — החזר 0. דוגמאות: 4 → 9 → 1 → null → 9 -5 → -2 → -9 → null → -2 null → 0 הנחיות: • בדוק אם head הוא null **לפני** שאתה ניגש לערך שלו. • אתחל את המקסימום לערך של החוליה הראשונה, לא לאפס. המחלקה Node כבר מצורפת למשימה. ```ds:list {"title":"המקסימום כאן 9","items":["4","9","1"]} ``` ```ds:list {"title":"והמקרה שמפיל אתחול לאפס — המקסימום כאן -2","items":["-5","-2","-9"]} ```

האם הערך קיים בשרשרת

כתוב פעולה שמקבלת מצביע לחוליה הראשונה בשרשרת וערך שלם x, ומחזירה true אם קיימת חוליה שערכה x. דוגמאות עבור 4 → 9 → 1 → null: x=9 → true x=4 → true (החוליה הראשונה) x=1 → true (החוליה האחרונה) x=5 → false הנחיות: • ברגע שנמצא הערך אפשר להפסיק — אין טעם להמשיך עד הסוף. • שרשרת ריקה מחזירה false. המחלקה Node כבר מצורפת למשימה. ```ds:list {"title":"השרשרת שבדוגמה","items":["4","9","1"]} ```

הגדלת כל הערכים ב-1

כתוב פעולה שמקבלת מצביע לחוליה הראשונה בשרשרת של מספרים שלמים, ומעלה את הערך של **כל** חוליה ב-1. דוגמה: 4 → 9 → 1 → null הופך ל- 5 → 10 → 2 → null הנחיות: • השרשרת המקורית משתנה. הפעולה אינה מחזירה ערך ואינה בונה שרשרת חדשה. • השתמשו ב-setInfo כדי לשנות את הערך של חוליה. המחלקה Node כבר מצורפת למשימה. ```ds:list {"title":"לפני","items":["4","9","1"]} ``` ```ds:list {"title":"אחרי — אותן חוליות, לא שרשרת חדשה","items":["5","10","2"]} ```

ממערך לשרשרת

כתוב פעולה שמקבלת מערך של מספרים שלמים ומחזירה שרשרת חוליות שמכילה את אותם ערכים **באותו סדר**. דוגמה: {5, 2, 9} → 5 → 2 → 9 → null {} → null הנחיות: • שמירת הסדר היא הקושי. חיבור כל ערך חדש לראש השרשרת הופך את הסדר — נסו להבין למה, ואז בחרו: לעבור על המערך מהסוף להתחלה, או לשמור מצביע לחוליה האחרונה ולהוסיף אחריה. • מערך ריק מחזיר null. המחלקה Node כבר מצורפת למשימה. ```ds:array {"title":"המערך","items":["5","2","9"]} ``` ```ds:list {"title":"השרשרת שצריכה לצאת — אותו סדר","items":["5","2","9"]} ```

הערך המופיע במקום ה-n

נתונה שרשרת ממוינת של NumCount (מספר וכמות המופעים שלו), כמו בתרגיל הקודם. "הערך המופיע במקום ה-n" הוא הערך שיושב במקום ה-n אילו היינו פורשים את השרשרת לרשימת ערכים מלאה, לפי הסדר, כשכל ערך חוזר count פעמים. לדוגמה, עבור השרשרת 3(4) → 5(1) → 8(3) → 10(1), הרשימה הפרושה היא: 3, 3, 3, 3, 5, 8, 8, 8, 10 1 2 3 4 5 6 7 8 9 ולכן עבור n = 7 התשובה היא 8. כתוב פעולה valueN שמקבלת את ראש השרשרת ואת n, ומחזירה את הערך במקום ה-n. הנחיות: • הספירה מתחילה מ-1. • אפשר להניח שהערך במקום ה-n קיים בשרשרת. • אל תבנו רשימה פרושה בזיכרון — צברו את הכמויות תוך כדי מעבר. ```ds:table {"title":"השרשרת","rows":[["num","count"],["3","4"],["5","1"],["8","3"],["10","1"]]} ``` ```ds:array {"title":"הרשימה הפרושה — האינדקס מתחת, אבל הספירה כאן מתחילה מ-1","items":["3","3","3","3","5","8","8","8","10"]} ```

הסרת המופע הראשון

כתוב פעולה שמקבלת מצביע לחוליה הראשונה בשרשרת וערך שלם x, מסירה את **החוליה הראשונה בלבד** שערכה x (אם קיימת), ומחזירה מצביע לראש השרשרת החדשה. דוגמאות עבור x=5: 1 → 5 → 2 → 5 → null → 1 → 2 → 5 → null 5 → 1 → null → 1 → null 1 → 2 → null → 1 → 2 → null (אין מה להסיר) הנחיות: • **הפעולה מחזירה Node.** אם המופע הראשון הוא בראש השרשרת, הראש משתנה. • רק מופע אחד מוסר. אחרי שהסרתם — צאו. המחלקה Node כבר מצורפת למשימה. ```ds:list {"title":"לפני — removeFirst(head, 5)","items":["1","5","2","5"]} ``` ```ds:list {"title":"אחרי — רק המופע הראשון הוסר","items":["1","2","5"]} ```

הסרת כל המופעים של ערך

כתוב פעולה שמקבלת מצביע לחוליה הראשונה בשרשרת וערך x, מסירה מהשרשרת את **כל** החוליות שערכן x, ומחזירה מצביע לחוליה הראשונה של השרשרת החדשה. דוגמאות עבור x=5: 1 → 5 → 5 → 2 → 5 → null → 1 → 2 → null 5 → 5 → 5 → null → null 1 → 2 → 3 → null → 1 → 2 → 3 → null הנחיות: • **הפעולה מחזירה Node.** זו כל הנקודה: אם החוליה הראשונה עצמה צריכה להימחק, הראש משתנה — ומי שקרא לפעולה חייב לקבל את הראש החדש. • קישור מחדש נעשה עם setNext: כדי לדלג על חוליה, מקשרים את קודמתה לחוליה שאחריה. • שים לב למופעים רצופים — אחרי דילוג אסור להתקדם מיד, כי גם הבאה עשויה להיות x. המחלקה Node כבר מצורפת למשימה. ```ds:list {"title":"לפני — removeAll(head, 5)","items":["1","5","5","2","5"]} ``` ```ds:list {"title":"אחרי","items":["1","2"]} ``` ```ds:list {"title":"והמקרה שמפיל פתרון שלא מחזיר ראש חדש — כאן הראש עצמו נמחק","items":["5","5","5"]} ```

הכנסה לשרשרת ממוינת של ערך-וספירה

נתונה המחלקה NumCount — מספר ולה שתי תכונות: • num — ערך מספרי שלם • count — מספר המופעים של num, שלם וגדול מ-0 נתונה המחלקה OrderedList — שרשרת ממוינת, ולה תכונה אחת: • lst — מצביע לראש שרשרת חוליות מטיפוס NumCount השרשרת ממוינת בסדר עולה לפי num, וכל ערך num מופיע ב**חוליה אחת בלבד**. ממשו את הפעולה insertNum(int x) שמוסיפה מופע אחד של x: • אם קיימת חוליה שערך num שלה שווה ל-x — הגדילו את count שלה ב-1. • אחרת — הכניסו חוליה חדשה עם num = x ו-count = 1, במקום שישמור על סדר השרשרת. הנחיות: • שלושה מקומות הכנסה אפשריים: לפני הראשונה, באמצע, ואחרי האחרונה. כל אחד מהם מתנהג אחרת. זו כל הנקודה של השאלה. • רשמו בהערה מהי סיבוכיות זמן הריצה של הפעולה. ```ds:table {"title":"השרשרת ההתחלתית — num ו-count בכל חוליה","rows":[["num","count"],["3","9"],["5","1"],["8","2"]]} ``` ```ds:table {"title":"אחרי insertNum(5) — הערך קיים, רק count גדל","rows":[["num","count"],["3","9"],["5","2"],["8","2"]]} ``` ```ds:table {"title":"ואחרי insertNum(4) — חוליה חדשה נכנסת באמצע","rows":[["num","count"],["3","9"],["4","1"],["5","2"],["8","2"]]} ```

האם כל המספרים מוכלים בטווחים

נתונה המחלקה Range — טווח, ולה שתי תכונות: low ו-high (שלמים, high >= low). מספר x "מוכל" בטווח אם low <= x <= high. נתונות שתי שרשרות: • lst1 — שרשרת של מספרים שלמים, **ממוינת בסדר עולה** • lst2 — שרשרת של טווחים, **ממוינת בסדר עולה** (ה-high של כל טווח קטן מה-low של הטווח שאחריו) כתוב פעולה isIncluded שמחזירה true אם **כל** מספר ב-lst1 מוכל באחד הטווחים ב-lst2. דוגמה שמחזירה true: lst1: -9 → -8 → -7 → 12 → 14 → 15 lst2: [-20,-10] → [-9,0] → [2,4] → [12,12] → [14,17] דוגמה שמחזירה false: lst1: 1 → 5 → 8 → 12 lst2: [-20,-10] → [-9,0] → [1,6] → [9,12] → [20,100] המספר 8 אינו מוכל באף טווח. הנחיות: • **זמן ריצה O(N)**, כאשר N הוא אורך השרשרת הארוכה. לולאה בתוך לולאה תיתן תשובה נכונה אבל לא תעמוד בדרישה. • רמז: שתי השרשרות ממוינות. התקדמו על שתיהן במקביל עם שני מצביעים, והחליטו בכל צעד את מי לקדם. • שתי השרשרות אינן null. ```ds:array {"title":"lst1 בדוגמה המוכלת","items":["-9","-8","-7","12","14","15"]} ``` ```ds:table {"title":"lst2 בדוגמה המוכלת — כל מספר מוצא בית","rows":[["low","high"],["-20","-10"],["-9","0"],["2","4"],["12","12"],["14","17"]]} ``` ```ds:array {"title":"lst1 בדוגמה שאינה מוכלת — 8 נופל בין הטווחים","items":["1","5","8","12"]} ``` ```ds:ta…

תלמיד ורשימת ציונים

בנו שתי מחלקות, כל אחת עם חמשת יסודות המחלקה (שם באות גדולה, תכונות, בנאי, getters ו-setters, ו-toString). **Grade** — ציון: • name — שם המקצוע • value — ערך מספרי שלם בין 0 ל-100 **Student** — תלמיד: • id — מספר תעודת זהות (מחרוזת) • grades — שרשרת חוליות של ציונים הוסיפו ל-Student: • addGrade(g) — מוסיפה ציון לתלמיד. • countGrades() — מחזירה כמה ציונים יש לתלמיד. • hasFailing() — מחזירה true אם קיים אצלו ציון נכשל. ציון נכשל הוא ציון **מתחת ל-55**. ולבסוף, פעולה סטטית printFailing שמקבלת מערך של תלמידים ומדפיסה את תעודות הזהות של אלה שיש להם לפחות ציון נכשל אחד, כל אחת בשורה. הנחיות: • התכונות פרטיות. הגישה אליהן רק דרך פעולות המחלקה. • שימו לב לגבול: 55 עובר, 54 נכשל. המחלקה Node כבר מצורפת למשימה. ```ds:table {"title":"הנתונים שבדוגמה","rows":[["ת.ז.","ציונים","יש נכשל?"],["111","מתמטיקה 90 · אנגלית 40","כן"],["222","מתמטיקה 80 · אנגלית 55","לא — 55 עובר"],["333","אין ציונים","לא"],["444","היסטוריה 54","כן — 54 נכשל"]]} ```

רשימה מקושרת — מצביעים, חוליות ומה שביניהן

רשימה מקושרת — חידון סיכום

מעבר על רשימה — למה כלום לא מודפס פעמיים

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

הכנסת חוליה אחרי p — השלב החסר

האלגוריתם מכניס חוליה חדשה מיד אחרי החוליה p. שלב אחד חסר. השלימו אותו.

ספירת חוליות — לולאה או רקורסיה

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

מבצע מצביעים

מימוש מבני נתונים — לפתוח את הקופסה השחורה

מימוש מבני נתונים — חידון סיכום

מימוש מחסנית מעל מערך

עד עכשיו השתמשתם במחסנית מוכנה. עכשיו תבנו אחת. ממשו את ארבע הפעולות של המחלקה MyStack, כך שתתנהג בדיוק כמו מחסנית: האחרון שנכנס יוצא ראשון. התכונות כבר נתונות לכם: • items — מערך שמחזיק את הערכים • count — כמה ערכים יש כרגע במחסנית הנחיות: • push שם את הערך בתא count ומגדיל את count באחד. • pop מקטין את count ומחזיר את הערך שבתא הזה. • top מחזיר את הערך העליון בלי לשנות דבר. • אין להשתמש במחלקת מחסנית מוכנה. ```ds:table {"title":"מעקב אחרי count","rows":[["פעולה","count אחרי"],["מחסנית חדשה","0"],["push(5)","1"],["push(9)","2"],["pop()","1"]]} ```

מימוש מחסנית מעל שרשרת

אותו ממשק בדיוק, מימוש אחר לגמרי — הפעם בלי מערך. ממשו את המחלקה MyStack מעל שרשרת חוליות. התכונה היחידה היא head, מצביע לראש השרשרת. הנחיות: • push יוצר חוליה חדשה שה-next שלה הוא ה-head הנוכחי, ומעדכן את head לחדשה. • pop לוקח את הערך מה-head ומקדם את head לחוליה הבאה. • isEmpty בודק אם head שווה ל-null. • אין גבול על מספר האיברים — זה בדיוק היתרון על המימוש במערך. שימו לב: ראש השרשרת הוא ראש המחסנית. זה לא במקרה — רק שם אפשר להוסיף ולהסיר בזמן קבוע.

מימוש תור מעל שרשרת

תור דורש שני מצביעים, ולא אחד. הבינו למה לפני שאתם כותבים. ממשו את המחלקה MyQueue מעל שרשרת חוליות: • head — ראש התור, המקום שממנו מוציאים • tail — סוף התור, המקום שאליו מכניסים הנחיות: • insert מוסיף חוליה אחרי tail ומעדכן את tail. • remove לוקח את הערך מ-head ומקדם את head. • בלי tail כל insert היה מחייב מעבר על כל השרשרת — O(n) במקום O(1). שני מקרי הקצה שהמשימה נבדקת עליהם: 1. הכנסה לתור ריק — צריך לעדכן גם head וגם tail. 2. הוצאת האיבר האחרון — tail חייב לחזור ל-null יחד עם head.

ספירת צמתים בעץ

כתוב פעולה **רקורסיבית** שמקבלת שורש של עץ בינארי ומחזירה כמה צמתים יש בעץ. הנחיות: • מקרה הבסיס: עץ ריק (null) מכיל 0 צמתים. • צומת אחד + כל הצמתים בתת-העץ השמאלי + כל הצמתים בתת-העץ הימני. ממשק מבני הנתונים כבר מצורף למשימה — אין צורך לממש את BinNode. ```ds:tree {"title":"העץ שבדוגמה — ארבעה צמתים","nodes":["4","2","7","1"]} ```

גובה העץ

גובה של עץ הוא מספר הקשתות במסלול הארוך ביותר מהשורש לעלה. עץ בן צומת אחד — גובהו 0. עץ ריק — נגדיר את גובהו כ--1. כתוב פעולה **רקורסיבית** שמקבלת שורש ומחזירה את גובה העץ. הנחיות: • גובה העץ = 1 + הגבוה מבין גובה תת-העץ השמאלי וגובה תת-העץ הימני. • ההגדרה של -1 לעץ ריק היא מה שגורם לחשבון לצאת נכון — נסה להבין למה. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:tree {"title":"אותו עץ — הגובה 2, כי המסלול הארוך הוא 4 → 2 → 1","nodes":["4","2","7","1"]} ```

ספירת עלים

עלה הוא צומת שאין לו בן שמאלי ואין לו בן ימני. כתוב פעולה **רקורסיבית** שמקבלת שורש של עץ בינארי ומחזירה כמה עלים יש בו. דוגמה עבור העץ שבקוד — יש בו 2 עלים. הנחיות: • שני מקרי בסיס: עץ ריק (0), וצומת שהוא עלה (1). • השתמש ב-hasLeft ו-hasRight. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:tree {"title":"העלים הם 1 ו-7. הצומת 2 אינו עלה — יש לו בן שמאלי","nodes":["4","2","7","1"]} ```

סכום ערכי העץ

כתוב פעולה **רקורסיבית** שמקבלת שורש של עץ בינארי של מספרים שלמים ומחזירה את סכום כל הערכים שבו. הנחיות: • מקרה הבסיס: עץ ריק (null) — הסכום 0. • צעד הרקורסיה: הערך של הצומת הנוכחי, ועוד סכום תת-העץ השמאלי, ועוד סכום תת-העץ הימני. • זה בדיוק אותו שלד של ספירת הצמתים. ההבדל היחיד: במקום להוסיף 1 לכל צומת, מוסיפים את הערך שבו. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:tree {"title":"העץ שבדוגמה — הסכום 26","nodes":["4","2","7","1","3",null,"9"]} ```

שלוש הסריקות

כתוב **שלוש** פעולות רקורסיביות שמדפיסות את ערכי העץ, כל ערך בשורה נפרדת: 1. סריקה תחילית (Preorder): שורש, שמאל, ימין. 2. סריקה תוכית (Inorder): שמאל, שורש, ימין. 3. סריקה סופית (Postorder): שמאל, ימין, שורש. עבור העץ שבדוגמה: תחילית: 4 2 1 3 7 9 תוכית: 1 2 3 4 7 9 סופית: 1 3 2 9 7 4 הנחיות: • שלוש הפעולות זהות לחלוטין חוץ ממיקום אחד: היכן ממוקמת שורת ההדפסה ביחס לשתי הקריאות הרקורסיביות. זו כל השאלה. • מקרה הבסיס בשלושתן: עץ ריק — לא מדפיסים כלום ומסיימים. • עץ ריק אינו מדפיס דבר, וזה תקין. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:tree {"title":"העץ שבדוגמה","nodes":["4","2","7","1","3",null,"9"]} ``` ```ds:table {"title":"שלושת הפלטים","rows":[["סריקה","פלט"],["תחילית","4 2 1 3 7 9"],["תוכית","1 2 3 4 7 9"],["סופית","1 3 2 9 7 4"]]} ```

סכום רמה בעץ

רמה 0 היא השורש, רמה 1 היא בניו, וכן הלאה. כתוב פעולה **רקורסיבית** שמקבלת שורש של עץ בינארי ומספר רמה k, ומחזירה את סכום הערכים של כל הצמתים ברמה k. עבור העץ שבדוגמה: k=0 → 4 k=1 → 9 (2 + 7) k=2 → 13 (1 + 3 + 9) k=5 → 0 (אין רמה כזו) הנחיות: • הרקורסיה צריכה לדעת באיזו רמה היא נמצאת. אין דרך לדעת זאת מהצומת עצמו, ולכן העומק חייב לעבור כפרמטר. • שני מקרי בסיס: עץ ריק (0), והגענו לרמה המבוקשת (מחזירים את הערך ולא ממשיכים לרדת). • צעד הרקורסיה: יורדים לשני הבנים עם k קטן ב-1, ומחברים. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:tree {"title":"העץ — רמה 2 מכילה את 1, 3 ו-9","nodes":["4","2","7","1","3",null,"9"]} ``` ```ds:table {"title":"סכומי הרמות","rows":[["רמה","צמתים","סכום"],["0","4","4"],["1","2, 7","9"],["2","1, 3, 9","13"],["3","—","0"]]} ```

האם הערך קיים בעץ

כתוב פעולה **רקורסיבית** שמקבלת שורש של עץ בינארי וערך x, ומחזירה true אם x מופיע באחד מצמתי העץ. העץ **אינו** עץ חיפוש — אין הנחה על סדר הערכים, ולכן יש לחפש בשני הצדדים. הנחיות: • מקרה הבסיס: עץ ריק — הערך בוודאי אינו בו. • צעד הרקורסיה: הערך נמצא אם הוא בשורש, **או** בתת-העץ השמאלי, **או** בתת-העץ הימני. • שים לב להחזיר את תוצאת הקריאות הרקורסיביות. קריאה שתוצאתה נזרקת היא הבאג הנפוץ ביותר ברקורסיה בוליאנית. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:tree {"title":"העץ — 3 קיים, 5 אינו קיים","nodes":["4","2","7","1","3",null,"9"]} ```

הערך הקטן בעץ

כתוב פעולה **רקורסיבית** שמקבלת שורש של עץ בינארי של מספרים שלמים ומחזירה את הערך הקטן ביותר שבו. העץ **אינו** עץ חיפוש. אפשר להניח שהעץ אינו ריק. הנחיות: • מקרה הבסיס: עלה — צומת בלי בנים כלל. הערך שלו הוא המינימום שלו. • צעד הרקורסיה: המינימום הוא הקטן מבין שלושה — הערך שבצומת, המינימום בשמאל, והמינימום בימין. אבל צד שאינו קיים אינו משתתף בהשוואה, ולכן צריך לבדוק אותו לפני. • דרך נקייה לעקוף את זה: להתחיל מ-min = הערך שבצומת, ולעדכן אותו רק אם יש בן שמאלי, ואז רק אם יש בן ימני. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:tree {"title":"העץ — המינימום 1","nodes":["4","2","7","1","3",null,"9"]} ```

היפוך עץ

היפוך עץ = החלפת הבן השמאלי בבן הימני בכל צומת וצומת, לכל אורך העץ. כתוב פעולה **רקורסיבית** שמקבלת שורש ומהפכת את העץ **במקום**, בלי לבנות צמתים חדשים. עבור העץ שבדוגמה, הסריקה התוכית לפני ההיפוך היא 1 2 3 4 7 9, ואחריו 9 7 4 3 2 1. הנחיות: • בכל צומת: החלף בין getLeft ל-getRight בעזרת משתנה עזר, בדיוק כמו החלפת שני משתנים רגילים. • אחר כך הפוך רקורסיבית את שני תת-העצים. אפשר גם לפני ההחלפה — חשוב מדוע שתי האפשרויות נכונות כאן. • אסור ליצור צמתים חדשים. העץ המקורי הוא זה שמשתנה. • עץ ריק — אין מה לעשות. ממשק מבני הנתונים כבר מצורף למשימה. ```ds:tree {"title":"לפני ההיפוך","nodes":["4","2","7","1","3",null,"9"]} ``` ```ds:tree {"title":"אחרי ההיפוך","nodes":["4","7","2","9",null,"3","1"]} ```

עצים בינאריים — מבנה, סריקות ועץ חיפוש

עצים בינאריים — חידון סיכום

ספירת עלים בעץ — תכננו לפני שאתם כותבים

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