שאלה

[i1991]

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

[שניצל]

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

[i1991]

עוד משהו,

אין איזה בעיה בפתרון שהצעת לגבי זמן ריצה של flip(לא ה-part flip)?

כי כשנרצה להפוך צריך להפוך את כל אחד מהביטים של כל אחת מהרשימות הקודמות וזה יקח o(k)

כאשר k זה מספר הרצפים ברשימה

[שניצל]

לא. ב-flip הופכים רק את הביט הראשי (להזכירך, יש ביט היפוך אחד לכל הרשימה כולה + ביט לכל תת רשימה).

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

[i1991]

לא. ב-flip הופכים רק את הביט הראשי (להזכירך, יש ביט היפוך אחד לכל הרשימה כולה + ביט לכל תת רשימה).

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

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

(עושים xor ביניהם)-אולי לא בדיוק הבנתי את הכוונה כאן? התכוונת שם סימנתי באחד ובמינוס אחד אז לכפול בינהם?

[שניצל]

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

תחשוב על זה ככה: לכל תת רשימה יש ביט היפוך "וירטואלי". במקום לשמור אותו, אתה תמיד שומר את ה-xor של הביט הזה עם ביט ההיפוך של הרשימה הראשית.

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

[Ghosthunter]

אתה יכול להגיד שXOR בין 2 ביטים (X^Y) זה כמו השלילי של הכפל (-X*Y), כאשר בXOR אתה שם ב- X -ו Y ערכים שהם 0 או 1, ובכפל אתה שם ערכים שהם -1 או +1. 0 יהפוך ל- -1 ו- 1 ישאר 1.

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

[i1991]

תודה רבה!!עזרתם המון