עמוד 1 מתוך 1

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

הודעהפורסם: 17:35 23/06/2010
על ידי michal cohen
הבנתי למה n<=(2t)^h+1 אבל לא הבנתי למה מחסרים בסוף 1?
בנוסף...
החזקת h+1 יוצאת ככה כי מניחים שלשורש יכולים להיות 2t מפתחות?

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

הודעהפורסם: 07:30 24/06/2010
על ידי yuli0708
לכל BT בן n איברים וגובה h ודרגה מינימאלית t>=2 מתקיים

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

ואז מקבלים כי

n>=2t^h - 1

אם להציב פה את נתוני השאלה זה מה שיתקבל

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

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

תודה

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

הודעהפורסם: 00:13 25/06/2010
על ידי hades200621
ה-1 למקרה הקיצון בו ה-h שווה ל-0 כלומר רק השורש קיים.
h+1 הרי נתון שזה בעצם הגובה של העץ כאשר הספירה מתחילה מ-0
וה-2t מבטיח שהאי שוויון יתקיים... היחיד שעומד בדרישות. תשובה 3 אינה נכונה.

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

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

אז איך זה בדיוק יוצא מהמשוואה?

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

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

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

בהצלחה