חידה בת זונה

[shpits77]

הצצתי לצונאמי...

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

 

[צונאמי]

פתרון.

int rand_1_to_10() { return 1; // return randon number 1-10 } int main() { int array[10] = {1,2,3,4,5,6,7,8,9,10}; int arrLastIndex = 9; int randArray[10]; int a1; for (int i = 0; i < 10; i++) { a1 = 0; int randRange = 9-i; // 0 to 9-i for (int j = 0; j <= randRange; j++) { int num = rand_1_to_10(); a1 += num; } a1 %= randRange; // a1 is a random index from array index 0 to 9-i randArray = array[a1]; array[a1] = array[arrLastIndex]; arrLastIndex--; } return 0; }​

 

[ברנדל]

תסביר בעיברית

בכל מקרה זה לא הפתרון, אם תסביר אני גם אוכל להסביר לך למה זה לא טוב.

 

[צונאמי]

אוקי

קודם על ממלאים מערך A במספרים מ-1 עד 10. עכשיו ממלאים מערך אחר לפי הסדר האינדקסים מ-0 עד ל-9 כאשר ממלאים את תא 0 יש לבחור מבין 10 מספרים (ש-ב-A) כאשר ממלאים את תא 1 יש לבחור מבין 9 מספרים הנותרים (ש-ב-A) .... כאשר ממלאים את תא 9 יש לבחור מבין 1 מספרים. (ש-ב-A) (בכל שלב כמובן שמוציאים מהמערך A את אותו מספר שהשתמשנו בו - כדי שלא יהיו חזרות) הטריק הוא איך למצא מספר רנדומלי בין 0 ל-i ע"י הפונקציה שמוצאת מספר אקראי בין 1 ל-10 .... וזאת נעשה ע"י כך שעבור i נבחר i+1 מספרים בין 1-10 ונחבר אותם ומהם נוציא מודולו i. יש לי כמה טעויות בתוכנית אז הנה מתוקנת (אני מקווה)

int rand_1_to_10() { return 1; // return randon number 1-10 } int main() { int array[10] = {1,2,3,4,5,6,7,8,9,10}; int arrLastIndex = 9; int randArray[10]; int a1; for (int i = 0; i < 10; i++) { a1 = 0; int randRange = 10-i; for (int j = 0; j <= randRange; j++) { int num = rand_1_to_10() - 1; a1 += num; } a1 %= randRange; // a1 is a random index from array index 0 to 9-i randArray = array[a1]; array[a1] = array[arrLastIndex]; arrLastIndex--; } return 0; }​

 

[ברנדל]

הטריק שלך...

for (int j = 0; j <= randRange; j++) { int num = rand_1_to_10() - 1; a1 += num; } a1 %= randRange;​

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

 

[צונאמי]

נכון אבל כל מספר אפשר להגריל אותו

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

 

[צונאמי]

אההה לא הבנתי אותך בפעם הראשונה

שים לב לטיפול במערך array המספרים הנותרים תמיד נמצאים בין אינדקס 0 לאינדקס x . (מצורה רציפה) בוחרים כל פעם מספר מבין הנותרים. ומכניסים אותו לאינדקס i הנוכחי.

 

[ברנדל]

קיצר, עזוב

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

 

[GPhoenixX]

אין לי מושג איך ליישם את זה אבל ...

ממה שהבנתי מהשאלה, הפיתרון צריך להיות קשור למספר התא במערך שבו אנחנו נמצאים. ז"א לא צריך להשתמש בפונקצית random אלא לכתוב אחת עם time שבהגרלה הראשונה תגריל מספר מ1-10 (כשנשארו 10 תאים) בהגרלה השנייה תגריל את המספרים שנותרו וכו' ........ כמובן שאין לי מושג איך לעשות את זה, אני רק אומר שלדעתי לא צריך להשתמש בפונקצית random מוכנה =O

 

[GPhoenixX]

אין לי מושג איך ליישם את זה אבל ...

ממה שהבנתי מהשאלה, הפיתרון צריך להיות קשור למספר התא במערך שבו אנחנו נמצאים. ז"א לא צריך להשתמש בפונקצית random אלא לכתוב אחת עם time שבהגרלה הראשונה תגריל מספר מ1-10 (כשנשארו 10 תאים) בהגרלה השנייה תגריל את המספרים שנותרו וכו' ........ כמובן שאין לי מושג איך לעשות את זה, אני רק אומר שלדעתי לא צריך להשתמש בפונקצית random מוכנה =O

 

[צונאמי]

פתרון אפשרי נוסף

לסדר את המספרים במערך בסדר רנדומלי כלשהו. ועכשיו לעבר תא תא לפי הסדר מ-0 עד -9 ועבור כל תא להגריל מספר (של תא כלשהו נוסף) ופשוט להפוך את הערכים שבהתאים. זמן לינארי.

 

[צונאמי]

במשפט הראשון התכוונתי ...

סדר רנדומלי = סדר כלשהו

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

 

[ברנדל]

אתה גדול!!!!

כל הכבוד. למי שלא רוצה להרוס לעצמו, שלא יקרא את התשובה.

 

[צונאמי]

תודה תודה ../images/Emo9.gif

 

[neko]

הערה קטנה:

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

 

[F 0 X]

אבל מה קורה אם...

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

 

[zagzagzag]

זה לא פרדוקס...

הדרישה הייתה שתקבל כל סידור אפשרי בהסתברות שווה (כלומר לכל סידור יהיה אותו סיכוי להתקבל) בפתרון יש רק מקרה אחד שבו תקבל את הסידור 1, 2 עד 10, וזו בדיוק הדוגמה שהבאת

 

[IP yuval]

לא נכון.

הדרישה הייתה שתקבל כל סידור אפשרי בהסתברות שווה (כלומר לכל סידור יהיה אותו סיכוי להתקבל) כשאין שני מספרים שווים! לכן, יש הרבה מצבים בהם יצאו הספרות 1,2,3,4,5... (בסדר עולה). אם יצאו המספרים: 0143256789 (יביא להחלפת כפולה של הספרות 2 ו4.).

 

[omni96]

מממ

אז הזמן ריצה הוא 2n בדיוק

 

[rubens1]

אכן, תשובות נכונות ראית כאן

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