בתשובה לגדי אלכסנדרוביץ', 15/07/09 16:33
 |
|
 |
||
|
||||
 |
למרות שעכשיו ברור הפתרון, איך מנוסחת החידה על אורך מעגל? |  |
 |
 |
|
|
|
||
|
||||
|
יש לך מעגל שנתון באמצעות רשימה מקושרת (כלומר, סדרה של מצביעים שכל אחד מצביע לכתובת של הבא). תמצא את האורך שלו. מקום אחר, ופרקטי, שבו החידה צצה - מציאת מעגלים בפונקציות תמצות קריפטוגרפיות. כאן אתה מתחיל ממספר כלשהו, מפעיל עליו את הפונקציה שוב ושוב עד שאתה מגיע למספר שכבר "ביקרת" בו. אותו רעיון נמצא בשימוש גם באלגוריתם ה-rho של פולרד לפירוק לגורמים. |
|
|
|
|
|
|
||
|
||||
|
יש לך דרך אלגנטית לחסום בניסוח החידה את הפתרון הטריוויאלי, לזכור את הכתובת הראשונה? שמא לתת כנתון לא רק מעגל, אלא גרף קשיר שמכיל מעגל? |
|
|
|
|
|
|
||
|
||||
|
אה... כן, זה כמובן מה שהתכוונתי אליו (גרף קשיר שמכיל מעגל). | |
|
|
|
|
|
||
|
||||
|
ואז, כשזיהית ששני ה"פועלים" שלך באותו מקום, כבר השלמת סיבוב, אבל צריך לעשות אותו שוב כדי לספור, נכון? | |
|
|
|
|
|
||
|
||||
|
אז מה. זה לא מוסיף לסיבוכיות (לכל היותר מעלה את זמן הביצוע פי 1.5 או משהו בסביבה). | |
|
|
|
|
|
||
|
||||
|
ברור. זה רק גורע, ואני קטנוני פה, שמץ של שמץ מהחן של הפתרון, בעיקר אם לפני-כן חשבת שנתון שאתה על המעגל, שאז זה לא נחוץ. | |
|
|
|
|
|
||
|
||||
|
העניין הוא שלא חושבים כך. למשל, בדוגמה שהתחילה את העניין (סימולציה של מכונת טיורינג עם חסם זכרון) לא ידוע אם בכלל יש מעגל, ומאוד לא סביר שנהיה עליו כבר בהתחלה. | |
|
|
|
|
|
||
|
||||
|
הנוסח שאני מכיר הוא למצוא אם רשימה מקושרת מכילה מעגל. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |