שאלה

[הזחל הכחול]

שאלה

אהלן, אשמח אם מישהו יוכל לתת לי רעיון, לתוכנית ב-C. הגבלות: אסור להשתמש במערך עזר, אסור רקורסיה, אסור לשנות את המערך f. סדר גודל של הפעולות צריך להיות k כאשר k הוא אורך הסדרה (לא אורך המערך). ישנה פונקציה המקבלת מערך int f ובודקת האם יש ב-f מעגל. המשמעות של מעגל היא כזו: נאמר: f[0]=2 אז הערך הבא שנבדק הוא f[2]=6 ואז f[6] = 5 ז"א הערך של איבר i במערך יהיה האיבר הבא במערך שיבדק. נאמר למשל ש-f[5]=2 , במקרה כזה הפונקציה מחזירה שיש מעגל (כי 2 כבר היה...). תודה מראש על כל רעיון.

 

[הזחל הכחול]

רעיונות?

מישהו?

 

[הזחל הכחול]

לא הלכה

ההקפצה... מנסה שוב.

 

[Metheny]

לא הבנתי ...

למה אתה פשוט לא יכול להתחיל באיזשהו תא, ולעבור על כל הסדרה, ולראות אם אתה חוזר באיזשהו שלב לתא ההתחלתי?

 

[הזחל הכחול]

ואיפה אתה

שומר אינדיקציה שכבר היית שם... המעגל הוא לא דווקא לתא ההתחלתי הוא יכול להיות לכל איבר בסדרה שקדם לאיבר הנוכחי. לדוגמא במערך: {a={2,4,5,7,8,8,3,5,5 a[0] = 2 a[2] = 5 a[5] = 8 a[8] = 5 ו-5 כבר היה.

 

[Metheny]

אולי...

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

 

[הזחל הכחול]

לא פותר לי

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

 

[Metheny]

דווקא כן עובד...

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

 

[mr small]

האם תוכל

להסביר בבקשה.

 

[Metheny]

איזה חלק לא הבנת?

 

[mr small]

לא הבנתי

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

 

[אלדד28]

פשוט מאוד,

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

int pos1, pos2; pos1 = 0; pos2 = arr[pos1]; while ((pos1 != pos2) && (pos1 != END) && (pos2 != END)) { pos1 = arr[pos1]; pos2 = arr[pos2]; if (pos1 != pos2) { pos2 = arr[pos2]; } } if (pos1 == pos2) printf("loop!");​

END מציין איזשהו "סוף" לשרשרת הזו.

 

[אינגולמו]

האם זה עונה על הדרישה

של סדר גודל של K ולא של גודל המערך? אני לא כ"כ בטוח....

 

[אינגולמו]

לדוגמה:

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

 

[אלדד28]

סדר הגודל של הפתרון הנ"ל

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

 

[אינגולמו]

הזכרת "סדרה"

בשאלה שלך. על איזו סדרה באורך K אתה מדבר? האם אתה מתכוון לגודל המעגל?

 

[mr small]

כן

אורך המעגל