שאלה 1ד מבחן סמסטר ג 2009

מנהל: TA_Isana

שלח תגובה
zoran
הודעות: 30
הצטרף: 21:18 10/11/2009

שאלה 1ד מבחן סמסטר ג 2009

שליחה על ידי zoran » 19:31 18/06/2010

נתון מערך בן n מספרים שלמים. ידוע שהוא מכיל את הערך 10 k פעמים. ידוע גם שכל ה10-ים מרוכזים בסוף המערך. האם ניתן לחשב את k
ב(O(logk? ענה בכן ולא
אין תשובה בפתרון שניתן. האם זה כן או לא?

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

Re: שאלה 1ד מבחן סמסטר ג 2009

שליחה על ידי TA_Yakim » 22:17 20/06/2010

כן
קודם כל נמצא באיזה תחום לחפש

קוד: בחירת הכל

i=0
len=A.length
while(A[len-2^i]=10){ 
                                i=i+1
}   // now 2^i >= k >= 2^(i-1)
הלולאה בזמן הדרוש ועכשיו נותר רק לחפש במערך בגודל 2k מה שגם עומד בזמן הדרוש

שלח תגובה

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