חידה

[טיקטי1]

חידה

נתון המשחק הבא. יש n קערות ובכל קערה מספר כלשהו של אגוזים (לכל היותר p אגוזים בקערה). במשחק משחקים שני שחקנים. כל שחקן בתורו בוחר את אחת הקערות ולוקח ממנה מספר אגוזים כלשהו. מי שלקח את האגוז האחרון הוא המנצח. (שני השחקנים יודעים את מספר האגוזים בכל קערה) מצא אלגוריתם בעל זמן ריצה מסדר גודל O(nlogp) המקבל מצב נתון של המשחק (כלומר את מספר האגוזים בכל קערה) שמשחק בצורה מושלמת, כלומר אם יש דרך לנצח הוא מוצא צעד מנצח. נלקח מהאתר: http://www.tau.ac.il/~cstasks/

 

[טלמון סילבר]

הרי זה ../images/Emo26.gif

הרי זה משחק "נִים" המפורסם, שסיפרתי עליו הרבה פעמים. האלגוריתם הוא אחד ויחיד, וסדר גודל הריצה הוא (O(n log p.