שירשור החידות הגדול

dudib · שליחה #401 16/09/2007 22:47

משה
למה שהסופר יוכנס על ידי הסוהר כל ערב ?
הרי הוא בוחר אסירים אקראית .

amirbd · שליחה #402 16/09/2007 22:47

משה - חיה רעה!!!

השרביט אצלך...

moco · שליחה #403 16/09/2007 23:11

dudib,
לא אמרתי כל ערב, רק שמובטח שמתישהו הוא ייכנס, ומתישהו שוב יכנס וכך הלאה לגבי כל אחד.

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

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

amirbd · שליחה #404 17/09/2007 0:39

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

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

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

הערות :
1. פתרון זה הורסני (הורס את הרשימות), אך בשאלה לא נדרש לשמר את הרשימות.
2. אם נסמן את אורך השרשרת הראשונה עד האיחוד ב-n, ואת אורך השרשרת השניה עד האיחוד ב-m, ונניח ללא הגבלת הכלליות ש-n<=m אזי הפתרון משתמש בשני פוינטרים בלבד, ומוצא את נקודת החיבור בזמן 2*m
3.. אם נדרש להחזיר את הרשימות למצבן המקורי, או שאסור לשנות את הלינקים המקוררים אזי יש פתרון אחרת יותר מסובך.

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

moco · שליחה #405 17/09/2007 8:43

התחלה יפה.
האמת, שכחתי לציין שאסור להרוס את הרשימה

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

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

osherov · שליחה #406 17/09/2007 9:08

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

amirbd,
חתיכת פתרון הבאת, הרגת את כל החיילים שלך בדרך כדי להגיע למטרה.
כשאתה מגיע למצביע שמצביע על null איך אתה יודע שזאת הייתה נקודת החיבור ולא סוף הרשימה המקושרת ?
דוגמה לשתי רשימות:
1) 1->2->3->4->5->100->101->NULL
2) 6->100->101->NULL

לפי האלגוריתם שלך אתה תגיע קודם ל NULL של רשימה 2 ותניח שאיבר 101 הוא נקודת החיבור
מה שלא נכון, נקודת החיבור בדוגמה הזאת הוא איבר 100

moco · שליחה #407 17/09/2007 9:14

יפה osherov, לא שמתי לב לטעות הזו.

osherov · שליחה #408 17/09/2007 9:48

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

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

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

סיבוכיות - (O(n~
זיכרון - קבוע

amirbd · שליחה #409 17/09/2007 10:07

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

וגם פותרים לו את החידה. תצה, תצה, תצה...

לא נורא, לא נורא, לכל שבת יש מוצאי שבת...

moco · שליחה #410 17/09/2007 10:16

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

יש פתרון בזיכרון קבוע ממש ובלי לכתוב על הרשימות עצמן.

osherov · שליחה #411 17/09/2007 10:20

בא'נה, הבנאדם הולך לישון, ועד שהוא קם גם אומרים לו שהוא הרג את החיילים שלו
...

תיקון,
את החיילים הרגת כבר אתמול בערב (לא סתאם הרגת אלא תקעת להם null בגב

)

amirbd · שליחה #412 17/09/2007 10:38

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

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

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

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

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

moco · שליחה #413 17/09/2007 10:52

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

שתשמע או תגלה את הפתרון, אתה לא תבין איך הצלחת להסתבך כל כך

amirbd · שליחה #414 17/09/2007 11:31

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

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

האם הפתרון הבא חוקי -

בכל איטרציה נחצה את גודל החיפוש.

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

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

moco · שליחה #415 17/09/2007 11:42

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

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

לתת את הפתרון הפשוט?

osherov · שליחה #416 17/09/2007 11:43

פתרון נוסף:
נספור את כמות האיברים ברשימה 1 - נסמן כ M
נספור את כמות האיברים ברשימה 2 - נסמן כ N

נסמן ב i את ההפרש בין M ל N כלומר i=M-N (לשם הפשטות נניח ש M>N)
עכשיו נעבור על שתי הרשימות במקביל ונחפש שוויון איברים (מצביעים) רק שברשימה הראשונה נהיה תמיד 1+i איברים לפני הרשימה השניה (כאילו חיפוש ב Shift קדימה של 1+i איברים)

כלומר נניח שתי רשימות

1->2->3->4->5->6->7->8->9->100->101
20->21->22->100->101

M=11
N=5
i=6
נתחיל לבדוק את האיבר ה 7 ברשימה הראשונה מול האיבר ה 1 ברשימה השנייה אח"כ איבר 8 מול איבר 2 וכך עד שנמצע את האיבר הזהה

moco · שליחה #417 17/09/2007 11:49

Osherov,
זה מה שהתכוונתי

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

amirbd · שליחה #418 17/09/2007 11:52

פשוט ויפה

amirbd · שליחה #419 17/09/2007 11:56

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

moco · שליחה #420 17/09/2007 12:14

אתה צודק, יש הנחה שלא אמרתי בפירוש שמדובר ברשימות בלי מעגלים ולכן סופיות.
אתה צודק גם בטענה השנייה אבל כשאומרים "ליניארי" בלי qualifiers נוספים, הכוונה היא ל
[left]
O( n )
[/left]
כאשר n הוא גודל הקלט, לא גודל של תכונה מסוימת בקלט.