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

לדוגמה:

  • השרשרת 2➔8➔5 מייצגת את המספר 258.
  • השרשרת 1➔2➔0➔9➔4➔5 מייצגת את המספר 120,945.

המחלקה StarCount אחראית על ספירת הכוכבים ביקום.

public class StarCount
{
    private Node<int> number;
}

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

(א)כתבו פעולה פנימית המתקנת את שרשרת החוליות number כך שכל החוליות יכילו ספרה אחת. חוליה המכילה מספר דו-ספרתי תפוצל לשתי חוליות, חוליה מכילה מספר תלת-ספרתי תפוצל לשלוש חוליות וכן הלאה.
לדוגמה:
השרשרת: `23➔5➔174➔6`
תהפוך לשרשרת: `2➔3➔5➔1➔7➔4➔6`
כותרת הפעולה:
```csharp
public void FixNumber()
```
(ב)בכל יום מתגלים כוכבים חדשים על ידי טלסקופים הפזורים במקומות שונים בכדור הארץ. כדי לשמור על הנתונים מעודכנים, נדרש לאפשר ביצוע של פעולות חשבון על המספרים המיוצגים על ידי שרשרת החוליות.
הפעולה הבסיסית ביותר הנדרשת היא AddOne - פעולה המגדילה ב-1 את מספר הכוכבים.
לדוגמה:
| שרשרת החוליות לפני AddOne | שרשרת החוליות אחרי AddOne |
|---|---|
| 1➔2➔8 | 1➔2➔9 |
| 4➔7➔5➔9 | 4➔7➔6➔0 |
| 9➔9 | 1➔0➔0 |

ממשו את הפעולה הפנימית AddOne המגדילה את מספר הכוכבים ב-1.
שימו לב! מספר הכוכבים הוא עצום, הרבה מעבר ליכולת הייצוג של טיפוסי נתונים רגילים כמו int, double או long ולכן אין לחבר את חוליות השרשרת כדי ליצור מספר שלם.
(ג)מהי סיבוכיות הפעולה AddOne שכתבתם בסעיף ב'? הסבירו את תשובתכם.

🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה בטיחות

שאלו כאן — ותקבלו מענה מוסמך.

🎓 מרצה בטיחות מוסמך עונה כאן — תקבלו מענה מקצועי

רוצים לתרגל אלפי שאלות נוספות?

המשיכו לתרגול מלא עם משוב אישי ←

מבחני מה"ט אמיתיים · משוב מיידי · וידאו לכל נושא · מעקב התקדמות

המשיכו לתרגול מלא ←