האלגוריתם של טוגזר

[נתנאל]

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

פורסם במקור בפורום CODE613 ב10/06/2017 22:26 (+03:00)

[dovid]

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

פורסם במקור בפורום CODE613 ב10/06/2017 23:04 (+03:00)

[נתנאל]

אכן כן. באמת הוא מחזיר שיש חוקיות.

Random rnd = new Random();
            
            List<List<int>> arrList = new List<List<int>>();
      
            for (int i = 0; i < 1500; i++)
            {
                List<int> intlist = new List<int>();
                while (intlist.Count < 8)
                {
                    int t = rnd.Next(1, 16);
                    if (!intlist.Contains(t))
                    {
                        intlist.Add(t);
                    }
                }
                arrList.Add(intlist);

            }
            int ctr = 0;
            for (int i = 0; i < arrList.Count; i++)
            {
                
                for (int j = 0; j < arrList.Count; j++)
                {
                    if (!SeeIfListCont(arrList[i], arrList[j]))
                    {
                        ctr++;
                    } 
                }
            }
            MessageBox.Show(ctr.ToString());

         
        }


        public bool SeeIfListCont(List<int> f , List<int> s)
        {
            int ctr = 0;
            for (int i = 0; i < f.Count; i++)
            {
                if (s.Contains(f[i]))
                {
                    ctr++;
                    break;
                }
            }
            return ctr > 0;

        }

פורסם במקור בפורום CODE613 ב11/06/2017 09:16 (+03:00)

[נתנאל]

for (int j = 0; j < arrList.Count; j++)
                {
                    if (!SeeIfListCont(arrList[i], arrList[j]))
                    {
                        ctr++;
                    } 
                }

כאן הוא בודק כל רשימה עבור רשימה אחרת אם יש בה את אחד האברים ומכיון שכן הוא מחזיר true ואם לא הוא מחזיר ספירה לctr ומכיון שתמיד הספירה מציגה 0 זה אומר שתמיד יש התאמה (נכון שזה לא מוכיח את זה - כי ההוכחה עצמה היא מסברא אבל זה מראה את זה...)

פורסם במקור בפורום CODE613 ב11/06/2017 11:23 (+03:00)

[dovid]

טוב. אם יש בדיוק 16 איברים הסבירות של אי התאמה נמוכה. לכן לא ראית, ו"לא ראינו אינה ראיה".
תשנה את זה:
int t = rnd.Next(1, 16)
לעד 32.

אז יהיה הרבה אי התאמות, אבל זה לא ראיה כלל שאי אפשר לסדר שתמיד יתאים.
בקיצור זה לא הוכחה.

פורסם במקור בפורום CODE613 ב11/06/2017 11:53 (+03:00)