קרין
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 18 December 2008 בשעה 22:53 | | IP רשוּם
|
|
|
|
קיבלתי את התרגיל הזה , אני פשוט לא יודעת איך להתחיל אותו אם אפשר לעזור לי ברעיון באלגוריתם ואהיה ממש ממש מודה:
בעיר חדשה רוצים לבנות מערכת בנקאית שתענה על השאילתות הבאות. להלן רשימת השאילתות בהם תומך המבנה:
Init():
אתחול בזמן קבוע, לא מדפיס כלום.
NewBank( bank_no, initial_budget)
קליטת בנק חדש למערכת. bank_no הוא מספר יחידי שלם, המזהה בנק. אם הפעולה הצליחה ,יש להדפיס את ההודעה ""Bank bank_no Established.במקרה שיש כזה מספר בנק ,תודפס ההודעה
"Bank bank_no already exist ".
סיבוכיות זמן O(log( #banks)).
NewCitizenWithoutAccount(id_no )
הצטרפות אזרח חדש לעיר,ללא פתיחת חשבון בשום בנק. אם הפעולה הצליחה ,יש להדפיס את ההודעה ""Citizen id_no arrived.אחרת ,תודפס ההודעה "Citizen id_no already exists ".
סיבוכיות זמן O(log( #people)).
NewAccount( id_no,bank_no, account_no)
פתיחת חשבון חדש עם סכום התחלתי בחשבון - 0. account_no הוא מספר יחידי שלם, המזהה חשבון.
יש לבדוק האם הפעולה הצליחה או לא,ולהדפיס הודעה מתאימה,בדומה לנעשה בשתי הפעולות הקודמות.
סיבוכיות זמן O(log( #banks)+log(#accounts)+log(#pe ople)).
AmountModification(bank_no, account_no,ammount)
שינוי היתרה(הוספת/ הוצאת סכום כלשהו ammount) בחשבון קיים.בסיום הפעולה היתרה בחשבון אמורה להיות מספר שלם אי-שלילי.
יש לבדוק האם הפעולה הצליחה או לא,ולהדפיס הודעה מתאימה.
סיבוכיות זמן O(log( #banks)+log(#accounts)+log(#pe ople)).
BalancedBank()
הדפסת bank_no של הבנק הכי מאוזן.
נגדיר:תקציב הבנק.תקציב הבנק כולל את התקציב ההתחלתי הניתן לבנק ברגע פתיחתו+סכום היתרות בכל החשבונות הקיימים באותו הבנק.יש להדפיס את bank_no של הבנק המהווה חציון מבין כל הבנקים לפי התקציב. במקרה שלשני בנקים יש בדיוק אותו התקציב ,יש להתייחס לבנק עם bank_no הקטן ביותר.
החציון מחושב הצורה הבאה:
נסתכל על סדרת מספרים הממויינת בסדר לא יורד:
אם כמות הנתונים בסדרה היא אי-זוגית,ז"א a1,a2,....,an,a(n+1).....,a(2n ),a2n+1 החציון הוא an+1
אם כמות הנתונים בסדרה היא זוגית,ז"א a1,a2,....,an,a(n+1).....,a2n החציון הוא an
סיבוכיות זמן O(1).
TopClient()
הפקודה הזו תדפיס את id_no של הלקוח הכי עשיר - עם סכום היתרות בכל השבונות המקסימלי מבין כל לקוחות הבנקים. במקרה שלשני לקוחות יש בדיוק אותה יתרה ,יש להתייחס ללקוח עם id_no הקטן ביותר.
סיבוכיות זמן O(1).
End
משחרר את כל המבנים ולא מדפיס כלום.
סיבוכיות זמן O(#accounts + #banks + #people).
הערות:
1. סיבוכיות המקום של המבנה הינה O(#accounts + #banks + #people).
2. בן אדם יכול לפתוח כמה חשבונות ,אבל כל חשבון בבנק אחר.לא ניתן לפתוח כמה חשבונות באותו הבנק.
3.לא ניתן להניח שתקציב הבנקים שונה זה מזה.
|
ראלף
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 25 December 2008 בשעה 20:00 | | IP רשוּם
|
|
|
|
את יכולה להשתמש בעץ סטוכסטי המכיל 8 מצביעים לעצי דרגה 2-3 אבסטרקטים הממוינים לפי החציון המינימלי ומשתנה ביניים סטטי סופי.
כשתציירי את התמונה הכל יתבהר לך ותראי שזה בעצם פשוט.
בבקשה ושיהיה לך בהצלחה
ראלף
|
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
