חידה בת זונה

[ברנדל]

חידה בת זונה

שגלעד ואלדד ענו יפה במסרים אישיים: נתונה פונקציה שמחזירה מספר רנדומלי בין 1 ל 10 לדוגמא אם נפעיל את הפונקציה 10 פעמים, הערכים המוחזרים עשויים להיות: 3 10 8 2 4 3 2 1 8 4 כמו כן נתון מערך שגודלו 10. יש למלא את התאים באופן רנדומלי כך שבכל אחד מהתאים תהיה ספרה אחרת בין 1 ל 10, כך שסידור יהיה רנדומלי לחלוטין, כלומר לא יתן עדיפות לספרה מסוימת בתא מסוים. דוגמא לסידור כזה: 3 5 8 2 1 9 6 4 7 10 אין צורך בקוד כתוב, רק הסבר

 

[alex11m]

פתרון בPASCAL

while i<=10 do begin x=random; if a[x]=0 than begin a[x]=i; i:=i+1; end; end;​

 

[alex11m]

הבהרות:

A הוא המערך RANDOM היא הפונקציה הנתונה...

 

[ברנדל]

אם זה היה כל כך פשוט

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

 

[alex11m]

לא הבנתי את הבעיה...?

יש לי השמה וקידום ה-I רק כאשר התא ריק....

 

[alex11m]

אם יהיה 7 פעמים אותו מספר אז

בפעם הראשונה נכניס בבתא של המספר את I ובפעמים האחרות לא נכניס....

 

[ברנדל]

כן רק ש..

אם יהיה 100000000000000 פעמים אותו מספר רצוף, יקח הרבה זמן עד שהעסק יגמר. אני מדבר על פתרון עם זמן קבוע וחסום, וכאן בדיוק החידה! אל תנסה לשכנע אותי שמקרה כזה לא סביר כי המטרה היא לפתור את החידה ולא לשנות את המטרה שלה. מה גם שאם הייתי שואל את החידה על ערכים הנעים בין 1 ל 1000 במקום על ערכים הנעים בין 1 ל 10 אז בשלבים מתקדמים של הלולאה היה לוקח כל פעם זמן משמעותי עד שהפונקציה היתה מגרילה מס' שעוד לא היה. במילים אחרות אני מדבר על פתרון עם זמן קבוע וחסום, וכאן בדיוק החידה! הזמן הוא אגב O(n כאשר n הוא גודל המערך. אגב זו חידה מראיונות עבודה

 

[aperture]

ניתן לחסום את הפיתרון ב (O(nlogn אם

נישתמש ב Hash Table במקום בלולאת While, כאשר (h(k פונקצית הגישה ל Hash, תהיה הפונקציה Random.

 

[ברנדל]

אם יש לך פתרון של

O(n אז תתן

 

[oketz1]

אם כבר אז רצוי להשתמש בטבלה סגורה

עם הפונקציה h(k,i) כאשר i מציין את הניסיון

 

[neko]

יש לי את זה, כך נדמה לי ../images/Emo58.gif

להשתמש בפונק' הרנדומלית כדי לבחור את התא במערך שאליו לכתוב את המספר הבא ברשימה (נתחיל מ-1 למשל), ואם התא תפוס, לרוץ קדימה עד שימצא תא פנוי (דומה מעט למימושים מסויימים של HASHTABLE). חביב.

 

[ברנדל]

פתרון לא טוב

אתה יכול לרוץ ולרוץ ולא למצוא תא פנוי

 

[neko]

מה פתאום?

מקסימום N תאים ריצה.

 

[shpits77]

פתרון אפשרי...

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

 

[ברנדל]

פתרון לא טוב

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

 

[shpits77]

נראה לי שלא הבנת את הפתרון...

הלולאה הפנימית מגרילה מספר "תנועות" מהמיקום העכשוי במערך על "תאים לא מאותחלים". זאת אומרת : אם באיטרציה האחרונה הגרלתי 3 תזוזות אני ארוץ על המערך כולו 3 פעמים ובפעם השלישית אשים את המספר 10 בתא הפנוי. פתרון זה טוב אם אנחנו לא רוצים להשתמש במחסנית נוספת לאגירת המספרים, אם יש לנו אפשרות למחסנית, אנחנו פשוט מאתחלים אותה עם המספרים וכל איטרציה מגרילים איזה מהמספרים להוציא (ולא מחזירים אותו חזרה פנימה)...

 

[ברנדל]

בסדר, הפתרון יעבוד והוא חסום

אבל... עדין הפתרון לא מספק אותי. יש פתרון מעולה לבעיה! תראה, אם נגיד שהחידה מדברת על מערכים בסדר גודל של 1000000 למשל (כמובן עם הפונקציה הרנדומלית המתאימה שמגרילה בין 1 ל 1000000) אז במקרה שנגריל בטעות 1000000, זה יקח המון זמן, שלא נדבר על הגרלת כמה כאלה רצופים. אני מדבר על זמן O(n כאשר זמן פעולה של כל איטרצית n היא מידית. אתה מציע זמן O של n בריבוע במקרה הגרוע.

 

[ברנדל]

אם לדייק

הפתרון הוא אולי O של 2n אבל זה לא משנה, בכל מקרה תחפש זמן קצר משמעותית. אגב לא אמרתי שאסור להשתמש במבנה נתונים נוסף, פשוט אין בו צורך.

 

[shpits77]

עוד שיטה...

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

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

מקוה שזה מספק

 

[ברנדל]

שני הפתרונות קרובים

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