מבקש ליעל את הפונקציה (C++) בעזרת חיפוש בינארי

[assaf990]

הפונקציה להלן מקבלת מערך a של מס' שלמים ואת אורכו n.

ידוע שתמיד:[0]a הוא זוגי, האיבר האחרון במערך הוא אי זוגי( a [i-1) וכן: n>=2

הפונקציה מחזירה ערך כלשהו i בין 0 ל- n-2 , המקיים: [a[i הוא זוגי והבא אחריו הוא אי זוגי.

int check (int a[],int n)
{
	for (int i=0;i<=(n-2);i++)
	{
		if (a[i]%2==0 && a[i+1]%2 !=0) 
		{
			return i;
		}
	}

}

הבעייה: אני צריך ליעל אותה בעזרת חיפוש בינארי. איך עושים זאת? :s05:

[icebreak]

אתה יכול לסרוק את המערך על פי האינדקסים הזוגיים שלו בלבד למשל ואז לבדוק אם הערך של התא הוא אי זוגי, אז תבדוק אם הערך של התא קודם זוגי, אחרת (אם הערך של התא זוגי), אם תבדוק האם הבא אחריו הוא אי זוגי.

[Boomerang]

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

אתה מתחיל עם קטע שבקצה שמאלי שלו יש מספר זוגי ובימני - מספר אי-זוגי, וזה מה שהולך להישמר בכל לולאה (loop invariant).

אתה שולף נקודה מאמצע הקטע. אם המספר בה זוגי, אתה מגדיר את הנקודה בתור הקצה הימני של הקטע, ואם הוא אי-זוגי, אתה מגדיר את הנקודה בתור השמאלי של הקטע.

אתה ממשיך לשלוף נקודות עד שיש לך קטע באורך 2 (וכיוון שה- loop invariant נשמר, הקצה הימני של הקטע הוא בדיוק הנקודה שחיפשת)

שים לב שזה מייעל רק את המקרה הגרוע ואם המערך מסודר רנדומלית אז במקרה הממוצע עדיף לך לעבור בצורה לינארית (מספר האיטרציות הממוצע יהיה 2 במקום lg(n) (

[bla7]

פיתרון שלי, נדמה לי שהוא עובד:

const ArraySize = 100;
int currentArraySize = ArraySize / 2;
int currentIndex = ArraySize / 2;

while (currentArraySize > 0)
{
	currentArraySize /= 2;
	if (a[currentIndex] % 2 == 0)
		currentIndex += currentArraySize;
	else
		currentIndex -= currentArraySize;
}

if (a[currentIndex] % 2 == 0)
	return currentIndex;
else
	return (currentIndex - 1);

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

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

[Boomerang]

הבעיה עם הפיתרון הזה היא השארית בחלוקה ב- 2.

אם המערך היה של 31 איברים והמספר האי זוגי הראשון נמצא אחרי המקום ה- 26 לא היית מוצא אותו.

עדיף לך לעבוד עם קצה ימני וקצה שמאלי.

[assaf990]

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

אתה מתחיל עם קטע שבקצה שמאלי שלו יש מספר זוגי ובימני - מספר אי-זוגי, וזה מה שהולך להישמר בכל לולאה (loop invariant).

אתה שולף נקודה מאמצע הקטע. אם המספר בה זוגי, אתה מגדיר את הנקודה בתור הקצה הימני של הקטע, ואם הוא אי-זוגי, אתה מגדיר את הנקודה בתור השמאלי של הקטע.

אתה ממשיך לשלוף נקודות עד שיש לך קטע באורך 2 (וכיוון שה- loop invariant נשמר, הקצה הימני של הקטע הוא בדיוק הנקודה שחיפשת)

שים לב שזה מייעל רק את המקרה הגרוע ואם המערך מסודר רנדומלית אז במקרה הממוצע עדיף לך לעבור בצורה לינארית (מספר האיטרציות הממוצע יהיה 2 במקום lg(n) (

אימצתי

אתה יכול לסרוק את המערך על פי האינדקסים הזוגיים שלו בלבד למשל ואז לבדוק אם הערך של התא הוא אי זוגי, אז תבדוק אם הערך של התא קודם זוגי, אחרת (אם הערך של התא זוגי), אם תבדוק האם הבא אחריו הוא אי זוגי.

רעיון נחמד אבל אין בו שימוש בחיפוש בינארי..(מקווה שאני צודק בזה)

[bla7]

הבעיה עם הפיתרון הזה היא השארית בחלוקה ב- 2.

אם המערך היה של 31 איברים והמספר האי זוגי הראשון נמצא אחרי המקום ה- 26 לא היית מוצא אותו.

עדיף לך לעבוד עם קצה ימני וקצה שמאלי.

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

const ArraySize = 100;
double currentArraySize = ArraySize / 2;
double currentIndex = ArraySize / 2;

while (currentArraySize > 0)
{
	currentArraySize /= 2;
	if (a[(int)currentIndex] % 2 == 0)
		currentIndex += currentArraySize;
	else
		currentIndex -= currentArraySize;
}

if (a[(int)currentIndex] % 2 == 0)
return (int)currentIndex;
else
return ((int)currentIndex - 1);

[Boomerang]

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

בנוסף, השגיאה מצטברת, ולא הייתי סומך על החישוב הזה שתמיד יצליח עבור 100 מספרים (צריך לעגל במקום להמיר ל- int וזה כבר נהיה ממש מיותר לעומת האלטרנטיבה)

[bla7]

ל-Double יש... כמה? 32 ספרות עשרוניות אחרי הנקודה, אם אני לא טועה.

אם נתחשב בעובדה שכל האי-דיוקים העשרוניים הם שברים שהמכנה שלהם הוא חזקה של 2, אז ב-31 המספרים הראשונים בכלל אין שגיאה. החל מהמספר ה-32 יש שגיאות שקטנות מ-2 בחזקת מינוס 31. צריך סדר גודל של מיליארד מספרים קטנים כאלה כדי להצטבר לכדי 1.

אני רגוע...

[Boomerang]

אז ככה, ל- double יש 15 ספרות עשרוניות אחרי הנקודה, אי-הדיוקים מתחילים כבר מהתחלה, ומספיק שמספר יהיה קטן (בכל גודל שהוא) ממספר שלם כלשהו כדי שהוא יא יומר אליו בהמרה ל- int.

זאת הסיבה שצריך לעגל בכל המרה ל- int (בכלל, השוואה בין double למספר אחר חייבים לעשות ע"י בדיקה שההפרש קטן מערך מסויים ולא ע"י ==)

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

[bla7]

טוב, בדקתי את זה...

אני מזכיר לך שאנחנו מדברים על double ולא float.

יש לו סה"כ 64 סיביות. סיבית אחת מייצגת סימן. 11 סיביות מייצגות אקספוננט. והשאר, 52 ספרות מייצגות את המספר (מנטיסה). בסה"כ האינדקס לא אמור לחרוג מ-100, לכן מספיק 7 ספרות עבור החלק שמשמאל לנקודה העשרונית - אז יש לנו, בעצם, 45 ספרות עבור הערך אחרי הנקודה. זה 13 ספרות יותר ממה שחשבתי.

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

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

אז שוב, אני רגוע

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

(אגב, אני מצטער על העקשנות, אבל במעט ת'רדים בהם אני משתתף פעיל, אני משתדל שיהיו מועילים ומדוייקים - לפחות כשהידע שלי עוזר לצורך העניין)

[Boomerang]

צודק, טעיתי.

אתה מתגבר על השגיאה שאני דיברתי עליה בזה שאינדקס ההתחלתי שלך הוא קצת מעבר לאמצע המערך ואתה עושה את הבדיקה הנוספת בסוף.

אם כבר, אז נראה לי שאתה יכול לעצור כאשר המערך שאתה מחפש בו כולל רק מספר שלם אחד (זה ייקרה אחרי לוג2 (n) איטרציות, ומה שאתה עושה מוסיף עוד קצת יותר מ- 1000 איטרציות).

עדיין, אני הייתי עושה את זה עם מספרים שלמים.

זה כבר לא קשור, אבל לגבי הדיוק של double, לפחות בקומפיילר של מייקרוסופט, ל- double יש דיוק של 15 ספרות

שזה לוג10 של 2 בחזקת 52

[bla7]

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

לא הבנתי את מה שהסברת על 1000 איטרציות... :-\

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

[Boomerang]

נגיד שבמערך יש 100 אברים. אתה מתחיל מהאיבר באינדקס 50 למרות שהאיבר האמצעי הוא 49. (אולי לא התכוונת, אבל בלי זה זה לא תמיד יפעל).

הקטע של ה- 1000 איטרציות - אצלך אתה ממשיך לחלק את המערך עד שהגודל שלו "שווה" 0 (כלומר עד שהוא מגיע למספר החיובי הכי קטן, מחלק אותו בשתיים ומקבל 0). מבדיקה שעשיתי, לוקח לו קצת יותר מ- 1000 פעמים לחלק את הקטע עד שהוא מגיע לאורך 0.

[Ghosthunter]

צריכים להיות יעילים מבחינת מקום, ולא רק מבחינת זמן. כמובן שDOUBLE לא "יחנוק" את הRAM שלך, אך פתרון חסכוני במקום יהייה עדיף.