מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/מציאת איבר הרוב במערך/שאלה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

יהי A מערך שבו מספרים שלמים. מספר יקרא איבר רוב של A אם מספר ההופעות של ב-A הוא לפחות .


דוגמה:

אם ו-A = [1, 5, 2, 5, 5, 14, 5], אז 5 הוא איבר רוב, כי הוא מופיע לפחות פעמים.


שימו לב כי אם קיים איבר רוב במערך A אזי הוא יחיד.

נגדיר בעיה שנקרא לה "בעיית איבר הרוב": בהינתן המערך A וגודלו , יש למצוא האם יש בA איבר רוב. אם כן יש להדפיס איבר זה; אחרת, יש להדפיס שלא קיים איבר רוב.


בסעיפים הבאים נעסוק בבעיית איבר הרוב.

תוכן עניינים

א'[עריכה]

אנא כתוב פסוודו-קוד עבור אלגוריתם לפתרון בעיית איבר הרוב הרץ בזמן . אנא הסבר בקיצור מה עושה האלגוריתם, מדוע הוא פותר את בעיית איבר הרוב, ונתח את זמן הריצה שלו.


רמז

העזר באלגוריתם אשר למדנו כבר בכיתה.

ב'[עריכה]

הניחו שברשותכם שגרה בשם Candidate(A,n) שמקבלת את המערך A וגודלו . אם בA יש איבר רוב, אז השגרה מחזירה את איבר הרוב. אחרת, השגרה מחזירה איבר כלשהוא מאיברי A. נקרא לזמן הריצה של Candidate(A,n) (כלומר, על קלט באורך )‏ .

אנא כתבו פסוודו-קוד עבור אלגוריתם שפותר את בעיית איבר הרוב בזמן על ידי שימוש בשגרה Candidate. הסבירו את נכונותו ואת זמן הריצה שלו.


שימו לב:

אינכם צריכים לכתוב את השגרה Candidate עצמה, אלא רק אלגוריתם שמשתמש בשגרה.

ג'[עריכה]

יהיו שני אינדקסים כך ש A[i] != A[j]. יהי B מערך המכיל איברים שהם כל איברי A מלבד A[i] ו]A[j



דוגמה:

עבור:

  • A=[1,5,2,5,5,14,5]

יש לנו B=[2,5,5,14,5].


אנא הוכיחו את הטענה הבאה: אם בA יש איבר רוב , אז הוא גם איבר רוב בB.

ד'[עריכה]

נתונה השגרה הבאה, בשם Candidate , המקבלת מערך A ומספר שלם בתחום , ומחזירה מספר.

Candidate(A, k)
1	if  k = 1 
2		return A[1] 
3	val = A[k] 
4	j  = 1;  count = 1
5	while( j < k and count > 0 )
6		if   ( A[k-j] = val ) then 
7			++count
8		else
9			--count
10			++j
14	if  j  == k 
15		return val
16	else
17		return Candidate(A ,k - j)

אנא הראה כי אם בA יש איבר רוב, אזי (Candidate(A, n תחזיר אותו; כמו כן, אנא נתח את סיבוכיות הפונקציה.