سلسلة - شغل مخك 25

[هاني الأتاسي 3]

كيف يمكنك تصميم لعبة X و O حيث الشبكة عبارة عن n*n وليس من الشرط أن تكون 3*3 ..

المطلوب هو تصميم تابع نقوم باستدعائه عند لعب أي من اللاعبين ومعرفة إذا فاز أحد اللاعبين ..

[سالم دك الباب 0]

بما أنه لم يتم وضع شروط على بنية المعطيات التي نخزن عليها حالة اللعبة فسأفرض البنية التالية:

مصفوفة من n+1 × n+1 بدلاً من n × n

للتبسيط سنرقم المصفوفة من 0 إلى n

عناصر المصفوفة مبدئياً يمكن أن تكون integer

بدايةً المصفوفة كلها أصفار

عندما يلعب اللاعب 1 يسجل الرقم 1 في المكان الذي يكافئ لعبته في المصفوفة وليكن x,y

بالإضافة إلى ذلك نجمع العدد 1 إلى كل من العنصرين x,0 و 0,y

وكذلك الأمر بالنسبة للاعب 2 يسجل -1 على سبيل المثال (المهم أن تكون القيمتين مختلفتين، وغير الصفر).

ونطرح 1 من العنصرين x,0 و 0,y

بقي أن نقوم بفحص عناصر السطر 0 والعمود 0 غيما إذا كان قد وصل أحدها إلى القيمة n أو -n (واضح من هو الفائز في كل حالة). وبفحص تساوي عناصر القطرين الرئيسي أو الثانوي للمصفوفةوقيمة عنصر من المتساوية العناصر تحدد الفائز.

ملاحظة1: مهما كانت قيمة n فإننا نقوم بالمرور على 4*n عنصر على الأكثر (كلفة خطية) بدلاً من أن نقوم بالمرور على n^2 عنصر. والتي تتضح كلفة خوارزميتها بزيادة العدد n.

الكود سأقوم بكتابته قريباً، بس الفكرة واضحة على ما أظن.

ملاحظة2 (مالها طعمة كتير :D :D :D ) :من الناحية النظرية في حال أردنا التوفير في حجم التخزين، يمكن عندها بناء مصفوفة من n×n عنصر (عناصرها عبارة عن متحولين منطقيين) بالإضافة إلى مصفوفتين أحاديتين طول كل منها n (عناصرها أعداد صحيحة) ولكن هذا غير مجدي في الحقيقة لأن المتحول المنطقي boolean يمثل على بايت على الأقل (رغم أن المطلوب هو بت). لذا فلا يمكن تطبيق ذلك بشكل مباشر عملياً.

[هاني الأتاسي 3]

صح ولكن ماذا من أجل القطرين .؟؟

[سالم دك الباب 0]

القطر الرئيسي:

رقم سطره = رقم عموده

القطر الثانوي :

مجموع رقمي سطره وعموده = n+1