שיחה:בעיית יוספוס
הפתרון לבעיה המקורית: יוספוס וחברו עמדו במקומות ה-16 וה-31 בסדר המתאבדים.
שאלה[עריכת קוד מקור]
אני מצטט מתוך הערך: "הנוסח הכללי של בעיה זו הוא: n אנשים עומדים במעגל, ונתון מספר טבעי m < n", מדוע ההגבלה הזו האם אותה בעיה לא קיימת כאשר m=n או אפילו m > n?
מה הפתרון??[עריכת קוד מקור]
לא נמצאה תשובה לבעיה? למקרה הכללי? מה הפתרון/האלגוריתם?אוהד 23:05, 17 יוני 2006 (IDT)
העתקתי משיחת משתמש של דוד שי[עריכת קוד מקור]
9 בעיית יוספוס
קראתי את הערך, אך אבוי, נשארתי במתח משום שפתרון הבעיה לא מופיע בערך. תוכל להוסיף אותו? גושניק יקר 20:41, 19 בספטמבר 2006 (IDT)
הלוואי וידעתי. דוד שי 20:44, 19 בספטמבר 2006 (IDT)
יש לך מזל שאתה לא יוספוס... :) אני אפנה למישהו אחר. גושניק יקר 20:47, 19 בספטמבר 2006 (IDT)
אכן מזל עצום. מבדיקה קצרה שערכתי, נוצר אצלי רושם שזו בעיה אלגוריתמית, כלומר כזו שלא תמצא נוסחה שנותנת את פתרונה, אלא תצטרך לדמות את התהליך כדי לקבל את סדר ההוצאות ובפרט את היוצא אחרון (כאן יש דוגמה נאה). בכל אופן זו בדיקה קצרה ושטחית, כך שכדאי להמשיך לחפש. דוד שי 21:04, 19 בספטמבר 2006 (IDT)
אני חושב שהמידע נחוץ כאן. חגי אדלר 06:22, 3 באוקטובר 2006 (IST)
יוספוס או יוסיפוס?[עריכת קוד מקור]
משתמש שינה את שם הערך ל"בעיית יוסיפוס" בנימוק "זה הכתיב הנכון (הערך עליו עצמו מאוית כך)". אינני יודע למה כוונתו - בערך יוסף בן מתתיהו מופיע צילום של עטיפת ספרו, ועליה כתוב "יוספוס". בגוגל יש יתרון מוחץ לתעתיק "יוספוס" החזרתי את המצב לקדמותו. דוד שי 07:36, 22 בינואר 2007 (IST)
אתה צודק מאד, ביצעתי חיפוש בגוגול וראיתי שהאיות "יוספוס" שכיח פי כמה מהאיות "יוסיפוס". מה שקרה הוא שחיפשתי את "בעיית יוספוס" ע"י מילת המפתח "יוסיפוס" (כך אני רגיל לכתוב משום מה) וקיבלתי רק את הערך "יוסף בן מתתיהו" ולא את הערך הנוכחי. לולי שזכרתי שכן ראיתי אותו פעם הייתי משוכנע שהוא לא קיים. על כל פנים, היות והערך על האיש עצמו כן הופיע (כי ישנו דף הפניה בשם "יוסיפוס פלאביוס") אפילו לא הבטתי בכותרת וחשבתי שזה שם הערך. מכאן נובע מה שכתבתי. אורח נטה ללון 11:32, 23 בינואר 2007 (IST)
יש לי פיתרון, אבל מישהו צריך לערוך אותו[עריכת קוד מקור]
להלן טיוטה: דרך פשוטה, אך יחסית מסורבלת, למצוא את מספרו של האדם האחרון, היא רקורסיה. נגדיר פונקציה (sk(n שנותנת את מספר האדם האחרון שנשאר במעגל עם n אנשים כאשר כל אדם k מוצא. נוציא את האדם הראשון, שנמצא במקום ה-k מודולו n. לו היינו ממספרים את המעגל מחדש כך שהאדם במקום שאחרי זה שהוצא יקבל את המספר אחד, הפונקציה הייתה למעשה נותנת את אותו הערך שתתן הפונקציה של n-1. כלומר, הפונקציות עבור n כאשר מתחילים ממספר 1 ועבור n-1 כאשר מתחילים מ-1+(k modulo n) מחזירות את אותו ערך ולכן ניתן לומר ש-(sk(n) = (k modulo n) + sk(n-1. (כל הנוסחה לעיל צריכה להיכנס למודולו n). עבור n=1 הפונקציה תחזיר 1 לכל n ולכל k. ניתן לפתוח את הרקורסיה ולקבל את הטור 1+(k modulo i) (גם הנוסחה הזו צריכה להיכנס למודולו n
