לא הצלחתי לפתור איזשהו תרגיל מסויים ב- C# והייתי שמח אם מישהו יוכל לפתור אותו.

זה התרגיל:

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

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

איך ניסית לפתור? יש לך רעיון כלשהו?

קוראים לזה רשימה מקושרת, לא שרשרת חוליות.

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

...ומה אם הוא לא מגיע לסוף?

בגלל זה הוא קביל ולא מכריע.

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

התכוונתי - אם אין סוף, הוא נתקע בלולאה אינסופית.

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

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

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

אפשר להניח שיש מזהה יחודי כלשהו לכל חוליה ברשימה? (נראה לי שחייב להיות כדי שתוכל להבדיל בין איבר לאיבר ברשימה)

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

תחזיק מצביע שישאר קבוע על האיבר הראשון ברשימה.

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

זה לא אמור להיות כ"כ בעייתי.

תחזיק מצביע שישאר קבוע על האיבר הראשון ברשימה.

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

זה לא אמור להיות כ"כ בעייתי.

אהם c# אהם

זה קוד אנסייפ וזה לא הכי מומלץ בסי שארפ

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

אני טועה?

השאלה נשאלת הרבה בראיונות למקומות עבודה.

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

אם אחד מהם הגיע לסוף - אין מעגל.

אם יש מעגל - הם יפגשו בהכרח.

האלגוריתם דטרמיסטי.

adamshar, תוכל להסביר מה היתרון של שני מצביעים שהאחד "רודף" אחרי האחר על פני מצביע אחד ששומר את כתובת ההתחלה ומצביע אחר שרץ בקפיצות של אחד? הרי עד המפגש בשני המקרים יתקיים אותו מספר איטרציות בדיוק לא?

כן, הפתרון של 2 המצביעים הוא הנכון.

הבעיה עם שמירת ראש הרשימה היא שהלולאה לא חייבת להיות דווקא דרך ראש הלולאה(אלא דרך אחר מהאיברים שאחריו).

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

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

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