שאלה 4מבני נתונים2022 קיץ מועד ארשימה מקושרתסה״כ 25 נק׳
בדיקת הכלה בין שרשרת מספרים לשרשרת טווחים
שימו לב
בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן.
נתונה המחלקה Range - טווח, ולה שתי תכונות:
low - מספר מטיפוס שלם
high - מספר מטיפוס שלם
המספר high גדול או שווה ל־low (low ≤ high).
הניחו שיש פעולות get ו־set בעבור תכונות המחלקה.
מספר כלשהו, x, "מוכל" בעצם מטיפוס Range אם הוא נמצא בטווח המספרים שבין low ובין high (low ≤ x ≤ high).
שרשרת חוליות lst1 מטיפוס שלם "מוכלת" בשרשרת חוליות lst2 מטיפוס Range אם בעבור כל מספר בשרשרת lst1 קיימת חוליה בשרשרת lst2 המכילה אותו.
הפעולה מחזירה true אם lst1מוכלתשרשרת חוליות lst1 מטיפוס שלם "מוכלת" בשרשרת חוליות lst2 מטיפוס Range אם בעבור כל מספר בשרשרת lst1 קיימת חוליה בשרשרת lst2 המכילה אותו. ב־lst2, אחרת היא מחזירה false. הפעולה חייבת לעבוד בסיבוכיות זמן ריצה של O(N).
הערה
N הוא אורך השרשרת הארוכה יותר מבין שתי השרשראות.
הנחות:
lst1 ו־lst2 אינם null.
בשרשרת lst2 כל העצמים מטיפוס Range אינם null.
השרשרת lst1 ממוינת בסדר עולה.
השרשרת lst2 ממוינת בסדר עולה, כלומר, ערך ה־high של כל חוליה קטן מערך ה־low של החוליה הבאה אחריה בשרשרת (כפי שמופיע בדוגמאות לעיל).
משימות
אמשימה א
מימוש100%
שפת התכנות שלי
שאלה 4מבני נתונים2022 קיץ מועד ארשימה מקושרתסה״כ 25 נק׳
בדיקת הכלה בין שרשרת מספרים לשרשרת טווחים
שימו לב
בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן.
נתונה המחלקה Range - טווח, ולה שתי תכונות:
low - מספר מטיפוס שלם
high - מספר מטיפוס שלם
המספר high גדול או שווה ל־low (low ≤ high).
הניחו שיש פעולות get ו־set בעבור תכונות המחלקה.
מספר כלשהו, x, "מוכל" בעצם מטיפוס Range אם הוא נמצא בטווח המספרים שבין low ובין high (low ≤ x ≤ high).
שרשרת חוליות lst1 מטיפוס שלם "מוכלת" בשרשרת חוליות lst2 מטיפוס Range אם בעבור כל מספר בשרשרת lst1 קיימת חוליה בשרשרת lst2 המכילה אותו.
הפעולה מחזירה true אם lst1מוכלתשרשרת חוליות lst1 מטיפוס שלם "מוכלת" בשרשרת חוליות lst2 מטיפוס Range אם בעבור כל מספר בשרשרת lst1 קיימת חוליה בשרשרת lst2 המכילה אותו. ב־lst2, אחרת היא מחזירה false. הפעולה חייבת לעבוד בסיבוכיות זמן ריצה של O(N).
הערה
N הוא אורך השרשרת הארוכה יותר מבין שתי השרשראות.
הנחות:
lst1 ו־lst2 אינם null.
בשרשרת lst2 כל העצמים מטיפוס Range אינם null.
השרשרת lst1 ממוינת בסדר עולה.
השרשרת lst2 ממוינת בסדר עולה, כלומר, ערך ה־high של כל חוליה קטן מערך ה־low של החוליה הבאה אחריה בשרשרת (כפי שמופיע בדוגמאות לעיל).
