טוב אני יודע שכבר דנו בבעיה הזאת

[ש ב ו ז]

טוב אני יודע שכבר דנו בבעיה הזאת

אבל אני לא זוכר שמישהו מצא פתרון של ממש אז אני שואל שוב כי זה משגע אותי נתון מערך עם N+1 איברים ובו ערכים בתחום שבין 1 ל N מס' ערכים חוזרים על עצמם על האלגוריתם למצוא ערכים אלו אם אני לא טועה סיבוכיות ריצה נדרשת היא של(O(N ויעילות בזיכרון של (O(1. רעיון לפתרון: ניקח איבר במקום I במערך (נגיד וערכו K) ונעביר אותו למקום הK במערך ואת האיבר במקום הK (נגיד שערכו M) נעביר למקום הM במערך עד שנגיע למצב שבו יש כבר איבר במקומו בתא אליו אנו ניגשים ואז ניתן להדפיס אותו. זה כמובן לא פותר את השאלה משום שאחרי שנסגר מעגל אחד איך ממשיכים (בסיבוכיות הרצויה)?

 

[MegaMango]

לא ממש הבנתי את השאלה..

נתון מערך עם n+1 איברים כאשר כל ערכי האיברים במערך חייבים להיות בין 1 ל-n ואנחנו צריכים למצוא אילו ערכים חוזרים על עצמם? הנה הרהור...אבל אני לא בטוח שהוא טוב. אני אסביר אחר כך למה . לדעתי אפשר להשתמש בסימון בתא של המערך המקורי בלי לפגוע בערך עצמו. למשל, כל פעם שאנחנו קוראים תא , נעשה שהתא במקום של הערך שקראנו יגדל ב-n. ככה נדע שכל תא שערכו גדול מ-n הוא תא שכבר קראנו מס' בערך שלו. נוכל לעבור פעם אחת על המערך כדי לשנות את התאים הנכונים ופעם נוספת כדי לבדוק מיהם כל אלה שערכם גדול מ-n . כדי לחזור לערך המקורי פשוט עושים מודולו n (כאשר 0 אומר שהערך המקורי היה n). הבעיה היא שזה לא ממש o(1) מבחינת זיכרון .. אם למשל n הוא המספר הכי גדול שתא יכול להכיל למשל, אז לא תהיה אפשרות לסמן תאים בעצם. יכול להיות שבאמת הפיתרון הנכון הוא מה שכבר הצעת עם כמה שיפורים >.>

 

[ש ב ו ז]

מממ... לא הבנתי

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

 

[MegaMango]

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

עובר על המערך ובודק את התוכן של כל אחד מהתאים. נגיד שעכשיו מצאתי בתא i את הערך k , אז אני מוסיף לתא k פלוס n. אחר כך אני ממשיך לתא i+1 ועושה אותו דבר. מה נעשה אם כבר חירבשנו את הערך של התא ב- i+1? מודולו n יחזיר לנו את הערך המקורי. אגב, עם העניין של הסימונים יש גם דרך לעשות את הפיתרון שלך בלי לולאה.. אבל שוב, אין דרך לדעת אם תא מסויים הוא מסומן או שיש בתוכו ערך. הסימון היחיד שאפשרי הוא 0 בעצם, אבל חייבים שני סימונים לפחות כדי לשמור את המספרים שחוזרים על עצמם. אפשר לעשות את הרעיון שלך, רק מתי שאנחנו קופצים ממספר אחד למספר אחד אנחנו מאפסים גם את התא (ושומרים את המקום האחרון שהגענו אליו בלולאה וחוזרים אליו אחרי שהגענו לתא מאופס). אחרי שאנחנו מגיעים שוב לתא שכבר איפסנו, אנחנו כבר יודעים שיש את המספר הזה פעמיים. אם למשל היינו מתבקשים רק להדפיס את המספרים שחוזרים על עצמם זה היה טוב כי היינו יכולים להדפיס בכל פעם שהיינו מוצאים מספר כזה(אם כי בהדפסה היינו מדפיסים גם כמה פעמים את אותו מס' כי שוב, אין דרך לזכור). בלעע אני לא אוהב תא השאלה הזאת. אני מכריז עליה כשיקוץ ומגנה אותה.

 

[ש ב ו ז]

אני מצטרף אליך

ומוקיע את כל מי שעוסק בה ככופר.

 

[MegaMango]

עם הגישה הזאת אני לא בטוח שעוד

אנשים יטרחו וינסו לפתור אותה P:

 

[MegaMango]

דייייייייייייייייי

אני מסרב לקבל את זה שיש משהו אחר. גם אם נעשה רדוקציה לתורת הגרפים נצטרך לשמור על o(1) זיכרון וזה אומר שאסור לנו להגדיל את התאים במערך או ליצור מערך עזר. זה בעצם לא ברור בשאלה כשאומרים עלינו "למצוא" את המספרים. מה זה למצוא? להחזיר מערך סופי עם סימונים של הסמפרים שחוזרים על עצמם? להדפיס אותם על המסך? להדפיס אותם על כרטיס לוטו? אם אנחנו רוצים להדפיס אותם אז כבר אמרתי מה לעשות.. אם רוצים להחזיר מערך אז חיים להשתמש במערך המקורי ואז חייבים דרך לסמן ואם אין דרך לסמן אז זה פשוט בלתי אפשרי כי אין לנו מערך אחר! הבעיה בסימון היא שאו שאנחנו לא יודעים אם הערך ששמנו הוא סימון או מספר אמיתי, או שאין מקום תמיד לשים את הערך שאנחנו רוצים. אם הפתרונות שהצעתי לא אפשריים, אז לדעתי השאלה הזאת בלתי אפשרית >< נמאס לי 'לחפור' אבל זה פשוט מוציא אותי מדעתי >____<

 

[ron369]

אני חושב שאפשר לעשות רדוקציה,

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

(אה, ואתה צריך גם לשים לב ש: ZZZ|E| = O(N)ZZZ, ככה שהסיבוכיות לא תשתנה עם אלגוריתמים לינאריים בגרפים. איך הרעיון?

 

[vinney]

איכפת לך לכתוב את האלגוריתם?

לא כל כך הבנתי את הרעיון...

 

[ron369]

זה בעצם מעין המשך של הרעיון שלו

אבל בגרף. יש קשת מכוונת בין הצומת i לצומת j, אם"ם בתא i במערך יש את הערך j. הייתרון הוא רק בכך שאתה, אולי, יכול להשתמש באלגוריתמים מוכנים על גרפים, ולא להתחיל "להסתבך" עם מימושים שונים. אגב, יש כמה חידות נחמדות דומות. למשל, למצוא את ה"מרחק" של המערך הזה ממערך ממויין, כאשר מגדירים את ה"מרחק", כמספר המקומות במערך שבהם: ZZZ A>A[j] ZZZ, אבל i<j.

 

[ron369]

בעצם, *דופק את הראש בקיר* ../images/Emo10.gif

O(1) זיכרון, איכשהו שכחתי מזה. אני צריך להספיק "לפתור" שאלות ב3 וחצי בלילה...

 

[siro1]

אם מדובר במספרים, אפשר לחשב

את סכום המספרים מ- 1 עד N ,ע"י הנוסחא )N+1)N /2 ולשים במשתנה SUM , אח"כ לחשב את סכום המערך ולשים במשתנה ARRSUM , ואז המס' שמופיע פעמיים הא ARRSUM-SUM . אני לא בטוחה אבל שזה בסיבוכיות מקום של 1...

 

[ש ב ו ז]

ומה אם יותר ממספר אחד מופיע פעמיים?