מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/חיפוש לינארי ובינרי/תרגילים

מציאת מספר איברים בתחום

שאלה

אנא כתוב מימוש יעיל לפונקציה Find-Num-In-Range(A, a, b), המקבלת:

1. מערך ממויין A של מספרים שלמים חיוביים
2. מספר שלם חיובי a
3. מספר שלם חיובי b גדול ממש מa

ומחזירה את מספר האיברים בA שכל אחד מהם נמצא בתחום $\displaystyle [a,b)$.

דוגמה: אם A = [1, 2, 4, 5, 99 , 11999], אז Find-Num-In-Range(A, 3, 99) תחזיר 2 (יש שני איברים בתחום).

תשובה

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

# Takes an array (Values) and a value (v).
# Returns the position of the largest value less than v.
# Note that the array (Values) must be sorted.
Less-Than-Pos(Values, v)
1	return Less-Than-Pos'(Values, v, 1, Length(Values))


# Takes an array (Values), a value (v), and two boundaries (left and right).
# Returns the position of the largest value less than v.
# Note that the array (Values) must be sorted.
Less-Than-Pos'(Values, v, left, right)
1	if left > right
2		return right
		
3	mid = ⌊(left + right) / 2⌋
		
4	if v <= Values[mid]
5		return Less-Than-Pos'(Values, v, left, mid - 1)

6	if v > Values[mid]
7		return Less-Than-Pos'(Values, v, mid + 1, right)

נוכיח נכונות. ההוכחה כמעט זהה לזו של חיפוש בינרי, ולכן נציין רק את החלקים השונים.

הוכחה: האינדוקציה היא על right - left + 1 (אורך התחום). נקרא לכך $\displaystyle n$.

(בסיס האינדוקציה) אם האורך $\displaystyle n$ הוא 0 או 1, אז מהתבוננות בקוד, הטענה נכונה.

(מעבר האינדוקציה) נניח שהטענה נכונה לכל $\displaystyle n'<n$. אם 4 מתקיימת, אז v קטן מValues[mid] (או שווה לו); מספיק לכן לבדוק את האינדקס מבין האיברים בתחום השמאלי. עפ"י הנחת האינדוקציה, נקבל את התשובה הנכונה. באופן דומה, אם 6 מתקיימת, אז נקבל את התשובה הנכונה.

נוכיח שהסיבוכיות היא $\displaystyle \Theta (\log(n))$.

הוכחה: קל לראות שנוסחת הנסיגה של הפונקציה היא $\displaystyle T(n)=T(n/2)+O(1)$. המשך ההוכחה דומה לאחת הדוגמות שראינו בפרישה.

נממש את הפונקציה המבוקשת בעזרת פונקציית העזר:

Find-Num-In-Range(A, a, b)
1	return Less-Than-Pos(A, b) - Less-Than-Pos(A, a + 1)

נוכיח נכונות.

הוכחה: נתבונן בLess-Than-Pos(A, b).

1. אם האינדקס הוא 0, אז כל האיברים גדולים מ$\displaystyle b$.
2. אם אינו 0, אז כל איבר שמימינו (אם יש) גדול מ$\displaystyle b$ או שווה לו, וכל איבר שמשמאלו קטן ממש מ$\displaystyle b$.

נתבונן בLess-Than-Pos(A, a + 1).

1. אם האינדקס הוא Length(A) + 1, אז כל האיברים קטנים מ$\displaystyle a$ או שווים לו.
2. אם אינו 0, אז כל איבר שמשמאלו הוא לכל היותר $\displaystyle a$, וכל איבר בו או מימינו (אם יש) גדול ממש מ$\displaystyle a$.

ההוכחה מתקבלת לאחר מחשבה על כל אחד מארבעת המקרים האפשריים (צירוף שני המקרים הראשונים והאחרונים).

קל לראות שהסיבוכיות היא $\displaystyle \Theta (\log(n))$, משום שהאלגוריתמים מורכב משתי קריאות לפונקציית העזר שבנינו.

מציאת מספר בינרי חסר

שאלה

נתונה מטריצה בת $\displaystyle n$ עמודות ו$\displaystyle m=2^{n}-1$ שורות. כל כניסה במטריצה היא 0 או 1, ולכן כל שורה מתארת מספר בינרי בעל $\displaystyle n$ ביטים. השורות אינן מסודרות בסדר ידוע, אך ידוע שאין שתי שורות זהות. מכאן נובע שחסרה שורה להשלמת כל $\displaystyle 2^{n}$ המספרים האפשריים בעלי $\displaystyle n$ ביטים.

דוגמה: עבור $\displaystyle n=2$, ייתכן שהשורה הראשונה היא המערך [0, 1] (המתאר בבינרית את המספר 1), השורה השנייה היא המערך [1, 1] (המתאר בבינרית את המספר 3), והשורה השלישית היא המערך [0, 0] (המתאר בבינרית את המספר 0). השורה החסרה היא המערך [1, 0] (המתאר בבינרית את המספר 2).

אנא תאר אלגוריתם המקבל מטריצה כזו, ומדפיס את השורה החסרה. נסה להגיע לאלגוריתם שסיבוכיותו $\displaystyle \Theta (m)$.

רמז נסה להפוך את הבעיה לבעיה קטנה בחצי (בערך) בזמן לינארי.

תשובה

נתבונן בעמודה האחרונה, ונספור את מספר ה0-ים ומספר ה1-ות שאנו רואים. היות שיש $\displaystyle m=2^{n}-1$, שורות, אז מספר ה0-ים גדול ב1 ממספר ה1-ות, או הפוך. נניח שמספר ה0-ים גדול ב1 ממספר ה1-ות (המקרה השני סימטרי). נוכל להסיק שני דברים:

1. הספרה החסרה בעמודה זו היא 1.
2. עלינו להתמקד רק בשורות בהן הספרה בעמודה זו היא 1 (קומבינטורית, לא ייתכן אחרת).

כעת נתחיל את הבעיה מחדש, תוך התמקדות בחצי (בערך) מהשורות (רק אלה בהן הספרה בעמודה זו היא 1): נסתכל בעמודה הלפני אחרונה,נספור את מספר ה0-ים ומספר ה1-ות שאנו רואים , וכולי.

להלן פסוודו-קוד יעיל המממש זאת:

Print-Missing-Number(M)
1	n = Num-Cols(M)

2	Rows = Make-Stack()

3	for j in [1, … 2^n - 1]
4		Insert-Front(Rows, j)
	
5	for i in [1, … n]
6		Zeros = Make-Stack()
7		Ones = Make-Stack()
	
8		while Size(Rows) > 0
9			row = Pop(Rows)
		
10			if M[row][i] == 0
11				Push(Zeros, row)
12			else
13				Push(Ones, row)
			
14		if Size(Zeros) > Size(Ones)
15			Print(1)
16			Rows = Ones
17		else
18			Print(0)
19			Rows = Zeros

1-4 מאתחלות את המחסנית Rows כך שתכיל את כל (מספרי השורות). 5-19 עובורת על כל העמודות. בכל איטרציה, 8-13 מחלקות את מספרי השורות בRows לשתי מחסניות, לפי ערך ביט העמודה הנכחית. 14-19 מדפיסות את הביט החסר בעמודה הנכחית, ומחליטות באיזו משתי המחסניות להתמקד.

נותר לנתח הסיבוכיות. נשים לב שהאיטרציה הראשונה פועלת בזמן $\displaystyle \Theta (m)$, האיטרציה השניה בזמן $\displaystyle \Theta (m/2)$, ובאופן כללי, האיטרציה ה$\displaystyle i$ בזמן $\displaystyle \Theta (m/2^{i})$. זמן הריצה, לכן, הוא $\displaystyle \sum _{i=1}^{n}\left[\Theta (m/2^{i})\right]=\Theta (m).$

מציאת מספר איברים מרוכבים בתחום

שאלה

אנא כתוב מימוש יעיל לפונקציה Find-Num-In-Range(A, a, b), המקבלת:

1. מערך A של מספרים מרוכבים לאו דווקא שלמים, הממויין לפי מרחק המספרים מראשית הצירים
2. מספר ממשי לאו דווקא שלם $\displaystyle a$
3. מספר ממשי לאו דווקא שלם $\displaystyle b$

ומחזירה את מספר האיברים בA שמרחק כל אחד מהם מראשית הצירים נמצא בתחום $\displaystyle [a,b)$.

הנח שברשותך פונקציה Dist(x) המקבלת מספר מרוכב ומחזירה את מרחקו מראשית הצירים.

תשובה

שאלה זו ותשובתה דומים מאד לשאלה על מציאת איברים שלמים בתחום. מטרת השאלה היא להבין כיצד לעקוף הבדלים טפלים בין בעיות שונות.

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

Less-Than-Dist(Values, v)
1	return Less-Than-Dist'(Values, v, 1, Length(Values))


Less-Than-Dist'(Values, v, left, right)
1	if left > right
2		return right
		
3	mid = ⌊(left + right) / 2⌋
		
4	if Dist(v) <= Dist(Values[mid])
5		return Less-Than-Pos'(Values, v, left, mid - 1)

6	if Dist(v) > Dist(Values[mid])
7		return Less-Than-Pos'(Values, v, mid + 1, right)

כעת נותר לטפל בפונקציה האחרונה. פונקציה זו ביצעה שתי קריאות:

• Less-Than-Dist(A, b) - כאן אין הבדל.
• Less-Than-Dist(A, a + 1) - מדוע הוספנו דווקא את המספר 1? מהתבוננות בתשובה עולה שכל שהיינו צריכים לעשות הוא להוסיף ל$\displaystyle a$ מספר שגודלו הוא לכל היותר ההפרש בין שני איברים שונים במערך. במקרה שמדובר במספרים שלמים, ההפרש בין שני מספרים שונים במערך הוא לפחות 1.

במקרה החדש, נעבור על המערך, ונמצא את $\displaystyle d$ - ההפרש הקטן ביותר בין שני מספרים שונים. היות שהמערך ממויין, ברור שנוכל לעשות זאת בזמן לינארי. נסיים את הפתרון בהצגת הקריאה האחרונה:

Find-Num-In-Range(A, a, b)
1	d = Min-Dist-Between-Two-Elements(A) # Finds the smallest distance as was just described.
2	return Less-Than-Dist(A, b) - Less-Than-Dist(A, a + d)