באוניברסיטה מפתחים מערכת למעקב אחר כוכבים חדשים שמתגלים מדי יום. מספר הכוכבים הוא גדול מאוד, לכן הוחלט לייצג את המספר באמצעות שרשרת חוליות של ספרות. סדר החוליות הוא לפי סדר הופעת הספרות במספר, כך שספרת האחדות היא החולייה האחרונה בשרשרת.
באוניברסיטה מפתחים מערכת למעקב אחר כוכבים חדשים שמתגלים מדי יום. מספר הכוכבים הוא גדול מאוד, לכן הוחלט לייצג את המספר באמצעות שרשרת חוליות של ספרות. סדר החוליות הוא לפי סדר הופעת הספרות במספר, כך שספרת האחדות היא החולייה האחרונה בשרשרת.
לדוגמה:
- השרשרת 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
כותרת הפעולה:
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 שכתבתם בסעיף ב'? הסבירו את תשובתכם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.