מבחן 2008 מועד א' שאלה 1 סעיף ג'

מנהל: TA_Isana

מבחן 2008 מועד א' שאלה 1 סעיף ג'

הודעהעל ידי michal cohen » 17:35 23/06/2010

הבנתי למה n<=(2t)^h+1 אבל לא הבנתי למה מחסרים בסוף 1?
בנוסף...
החזקת h+1 יוצאת ככה כי מניחים שלשורש יכולים להיות 2t מפתחות?
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: מבחן 2008 מועד א' שאלה 1 סעיף ג'

הודעהעל ידי yuli0708 » 07:30 24/06/2010

לכל BT בן n איברים וגובה h ודרגה מינימאלית t>=2 מתקיים

h<=logt(n+1) לוג בבסיס t של n+1 חלקי 2

ואז מקבלים כי

n>=2t^h - 1

אם להציב פה את נתוני השאלה זה מה שיתקבל
yuli0708
 
הודעות: 13
הצטרף: 15:30 04/12/2009

Re: מבחן 2008 מועד א' שאלה 1 סעיף ג'

הודעהעל ידי lironsam » 15:53 24/06/2010

שני דברים עדיין לא מסתדרים לי פה.....
החזקה של ה h( שבנתוני השאלה היא באמת h+1 ) היא רק על הt אז למה התשובה היא 1 ולא 3?
ומשהו נוסף
גובה העץ הרי קטן מהלוג ז"א שאם הופכים את הכל ל t בחזקת.. הביטוי בו נמצא t עדיין אמור להיות קטן יותר אבל בכל התשובות הוא גדול יותר ( פה אני בטוח מפספסת איזה החלפת סימן... רק שלא הצלחתי לראות איפה פספסתי ....)

תודה
lironsam
 
הודעות: 25
הצטרף: 23:12 04/12/2009

Re: מבחן 2008 מועד א' שאלה 1 סעיף ג'

הודעהעל ידי hades200621 » 00:13 25/06/2010

ה-1 למקרה הקיצון בו ה-h שווה ל-0 כלומר רק השורש קיים.
h+1 הרי נתון שזה בעצם הגובה של העץ כאשר הספירה מתחילה מ-0
וה-2t מבטיח שהאי שוויון יתקיים... היחיד שעומד בדרישות. תשובה 3 אינה נכונה.
hades200621
 
הודעות: 35
הצטרף: 01:00 24/10/2009

Re: מבחן 2008 מועד א' שאלה 1 סעיף ג'

הודעהעל ידי michal cohen » 18:57 26/06/2010

עדיין לא הבנתי איך זה יוצא מהנוסחא
h<=logn+1/2 כאשר לוג בבסיס t.
הרי מעלים את שני האגפים לחזקה של t ומקבלים:
t^h<=(n+1)/2
מכפילים ב-2 ומעבירים את אחד אגף ומקבלים:
2t^h-1<=n
כשהחזקת h היא על ה-t ולא על ה-2

אז איך זה בדיוק יוצא מהמשוואה?
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: מבחן 2008 מועד א' שאלה 1 סעיף ג'

הודעהעל ידי Shahar » 21:26 26/06/2010

מסתכלים על עץ B מלא לגמרי.
אז בכל קודקוד יש 2t-1 מפתחות, ולכן יש לו 2t בנים.
קוד: בחר הכל
sigma i=0 to h: (2t)^i = [(2t)^(h+1)  -1]/(2t-1)

זה מס' הקודקודים המקסימלי בגובה h.
נכפיל ב2t-1 כדי לקבל מס' מקסימלי של איברים/מפתחות.
ונקבלך בדיוק מה שצריך

בהצלחה
Shahar
 
הודעות: 160
הצטרף: 16:49 29/10/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים