עבודה 5 והאלגוריתם למציאת האיבר ה-i בגודלו

מנהל: TA_Isana

עבודה 5 והאלגוריתם למציאת האיבר ה-i בגודלו

הודעהעל ידי Brk » 17:55 16/07/2010

שאלה: האלגוריתם למציאת האיבר הn/k בגודלו מתבצע על ידי מציאת האיבר הn/2 בגודלו ואז באופן רקורסיבי מציאת החציונים בשאר תתי המערכים.נמשיך בתהליך הזה עד אשר נגיע לתתי מערכים בגודל n/k . בראש הקבוצה הראשונה בגודל n/k ישב האיבר ה-n/k ?(כערימת מקסימום כמובן)
אם ידרשו למצוא את האיבר שמופיע n/k פעמיים הרי שזה אותה אסטרטגיה,רק שעכשיו יש לי k מועמדים בk קבוצות,האיבר הn/k ,האיבר ה-2n/k וכך הלאה....
אם ידרשו למצוא את האיבר בגודל k אז פשוט מפעילים אלגוריתם Randomize_select או האלגוריתם הדטרמניסטי?
אם ידרשו למצוא איבר שמופיע k פעמיים אז מה האסטרטגיה?
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: עבודה 5 והאלגוריתם למציאת האיבר ה-i בגודלו

הודעהעל ידי Brk » 13:18 17/07/2010

הקפצה
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: עבודה 5 והאלגוריתם למציאת האיבר ה-i בגודלו

הודעהעל ידי Raz.A » 15:10 17/07/2010

לגבי מציאת האיבר הK בגודלו, יש פה
http://www.math.tau.ac.il/~matias/Class ... -video.ppt
תרגום של מצגת מעולה, שמסבירה את התהליך

בגדול, מציאת חציונים עפ"י אלגוריתם החמישיות ואז מצאת איזשהו איבר בין 3/10 ל 7/10 מהמערך. ואז לחפש משמאל או מימין לפיבוט (מוסבר מעולה במצגת)

לגבי חיפוש איבר שמופיע k פעמים במערך, יש שאלות שונות שנוגעות לזה (אחת מהן במועד קיץ 2009)
אבל בגדול אני לא חושב שיש איזשהו פיתרון כללי לשאלה הזאת.
Raz.A
 
הודעות: 64
הצטרף: 22:00 26/10/2009


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

מי מחובר

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