HELP !!!

[פורטו ריקו]

HELP !!!

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

 

[gmorphus]

חציון של שלושת המערכים כמצטרפים את

כל האיברים שלהם? או של כל מערך בנפרד? השאלה לא ברורה...

 

[פורטו ריקו]

הסבר...

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

 

[פורטו ריקו]

אני ממש ממש ממש ממש זקוק לעזרה...

בבקשה... מישהו...

 

[אלדד27]

אין לי רעיון קונקרטי,

אבל מה שבטוח זה שאתה לא יכול למזג את המערכים, כי מיזוג חייב לקחת (O(N, שזה כמובן יותר מ - logN ** 2. צריך פתרון אחר. אני אמשיך לחשוב על זה, נראה אם יהיה לי משהו להציע.

 

[פורטו ריקו]

תודה...

לפחות על הניסיון

 

[אלדד27]

מחשבות בקול רם.

אם אני לוקח את חציון המערך הראשון (X), ומאתר אותו בשני המערכים האחרים, יש לי בעצם אלגוריתם שעובד בסדר גודל של LOG N, ויכול לומר לי כמה מספרים יש אחרי X וכמה יש לפני X. לדוגמה, אם יש לי 11 איברים בכל מערך, האיבר ה - 6 הוא החציון של המערך הראשון (X). נניח שאנחנו מאתרים את X במיקום השלישי במערך השני, ובמיקום השמיני במערך השלישי. זה אומר שלפני X יש 5+2+7 איברים, כלומר 14 איברים, ואחריו יש 16 איברים. אה! יש לי פתרון. נניח שזה המצב - כמו שתיארתי אותו. עכשיו אנחנו יודעים שהחציון יהיה אחרי X, למעשה. נחצה את שארית המערך הראשון ל - 2, ניקח את החציון החדש, ונעשה שוב את אותו אלגוריתם, עד שנגיע למעשה לחציון האמיתי (כלומר נמצא מספר שיש 15 אחריו ו - 15 לפניו). בסה"כ זה logN**2. אבל יש בעיה עם הפתרון הזה. החציון הכולל לא חייב להיות במערך הראשון בכלל - הוא יכול להיות בכל אחד מהמערכים האחרים. אולי מישהו אחר יוכל לשפר את הפתרון שלי ככה שהוא יעבוד באמת

 

[aaa123]

אני לא חושב שיש בעיה

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

 

[אלדד27]

אתה צודק - אז הנה, יש פתרון ../images/Emo13.gif

 

[aaa123]

קצת מחשבה על הנושא

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

 

[אלדד27]

אני חושב שהפתרון שלך נכון -

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

 

[aaa123]

הבעיה היא שבמקרה שהמערכים לא שווים

אני לא מוריד חלקים שווים. אם זאת אני יודע את המיקום של מה שאנו צריכים למצוא אז נכון שגם זה נכון. עם המערכים שווים אז אני מוריד חצי מהגודל בכל אחד. אם המערכים לא שווים אז אז יתכן שבשלב הבא אני כבר לא אצטרך למצוא את החציון. נניח מערך אחד הוא של 100 איברים ו2 הם של 50 איברים אם החציון של 50 אחד הוא 7 ושל השני 6 כאשר החציון של המערך של 100 האיברים 8 אז אני יודע שהחציון האמיתי הוא בין 6 ל8. אני יכול להוריד חצי מהמערך של ה100 איברים(חצי עליון) וחצי מהמערך של ה50 איברים חצי תחתון) אבל בגלל שהחלקים שהורדתי לא שווים בשלב הבא לא צריך לחפש את האמצע.

 

[aaa123]

יש להחליף אם ועם בהתחלת ההודעה

 

[gmorphus]

יש לי פתרון

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

 

[aaa123]

לא נכון אפילו אם הגלים שווים

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

 

[aaa123]

גדלים ולא גלים ואגב זה שקיבלת

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