Αποστολέας Θέμα: σκακιέρα  (Αναγνώστηκε 2918 φορές)

nekis

  • Βετεράνος
  • ****
  • Μηνύματα: 76
  • U R NT A #
σκακιέρα
« στις: 20 Δεκ 2004, 11:29:54 πμ »
Αγαπητοί συναγωνιστές, έχω να προτείνω μια άσκηση για συζήτηση.

Σε μια σκακιέρα (δισδιάστατος α[8,8] )τοποθετούμε αρχικά έναν λευκό ίππο και δεχόμαστε είσοδο για τη θέση ενός μαύρου ίππου. Η έξοδος του αλγόριθμου είναι ένα μύνημα, αν τα δυο κομμάτια "τρώγονται", ή όχι.

Θεωρώ ότι η άσκηση μπορεί να επεκταθεί σε πολλές άλλες εκδοχές  και με άλλα κομμάτια.

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Re: σκακιέρα
« Απάντηση #1 στις: 20 Δεκ 2004, 02:56:31 μμ »
Αν a, b οι (νόμιμες) συντεταγμένες του πρώτου αλόγου και i, j οι (νόμιμες) συντεταμένες του δεύτερου μια συμπαγής συνθήκη που σκέφτηκα είναι η:

x<-απόλυτη τιμή(a-i)
y<-απόλυτη τιμή(b-j)  

Αν x+y=3 και απόλυτη τιμή(x-y)=1 τότε
Απειλούνται<-Αληθής
Αλλιώς
Απειλούνται<-ψευδής
Τέλος_αν

Δείτε το και σεις γιατί προσπάθησα να το κάνω συμπαγές και κάτι μπορεί μου ξέφυγε.

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5705
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Re: σκακιέρα
« Απάντηση #2 στις: 20 Δεκ 2004, 08:18:32 μμ »
Χε χε Γιώργο καλό αυτό ;)

Δηλαδή στο «Αν» λες:
(α) Αν απέχουν συνολικά 3 τετράγωνα μεταξύ τους «x+y = 3»
και
(β) Αλλά να απέχουν μόνο 1 γραμμή ή μόνο 1 στήλη «απόλυτη τιμή(x-y)=1»

Για να ισχύει το (α), το (Χ,Υ) ή το (Υ,Χ) θα πρέπει να είναι (1,2) ή (0,3), δηλαδή να απέχουν π.χ. 1 γραμμή και 2 στήλες ή 0 στήλες και 3 γραμμές.

Με την (β) συνθήκη αποκλείεις το ζεύγος αποστάσεων (0,3) και μένει (Χ,Υ) = (1,2) ή (Υ,Χ) = (1,2) και άρα είσαι ΟΚ.
Το ίδιο θα μπορούσε να γίνει και με την (β) συνθήκη ως «x*y <> 0»

Η απορία μου βέβαια είναι πόσο εύκολο είναι να το καταλάβει αυτό κάποιος μαθητής ;D ;D ;D


Εγώ στην τάξη θα πρότεινα τον πιο «χαμαλίτικο» τρόπο, δηλαδή ξεχωριστό τσεκάρισμα ότι απέχουν 1 γραμμή και 2 στήλες Η 2 γραμμές και 1 στήλη:

[glossa] x <-- Α_Τ(a-i)
y <-- Α_Τ(b-j)
απειλούνται <-- ((x = 1) ΚΑΙ (y = 2))
           Ή ((x = 2) ΚΑΙ (y = 1))[/glossa]
Εκτός τάξης όμως και για γενικότητα (όχι μόνο για άλογα) θα όριζα συναρτήσεις που να μου επιστρέφουν τις έγκυρες κινήσεις για το κάθε πούλι (θα έπαιρναν σαν παράμετρο και την σκακιέρα, π.χ. τα πιόνια μπορούν να κινηθούν και διαγώνια ΑΝ υπάρχει εκεί κάτι να «φάνε»)...

nekis

  • Βετεράνος
  • ****
  • Μηνύματα: 76
  • U R NT A #
Re: σκακιέρα
« Απάντηση #3 στις: 22 Δεκ 2004, 01:31:00 μμ »
Αγαπητοί συναγωνιστές ευχαριστώ για τα post.
Άλκη η αλήθεια είναι ότι όταν τη σκέφτηκα δεν είχα υπολογίσει την περίπτωση (1,2) (1,2).
Καλές γιορτές σε όλους στο forum

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Re: σκακιέρα
« Απάντηση #4 στις: 12 Ιαν 2005, 11:13:45 πμ »
Καλημέρα

Χρωστάω μια μικρή εξήγηση ως προς το πώς θα μπορούσε να σκεφτεί ο μαθητής έτσι ώστε να βρει τη συνθήκη που έγραψα παραπάνω. Μια λύση δεν είναι χρήσιμη στη σελίδα αν δεν προσφέρει έστω και κάτι με τη μορφή γνώσης στο μαθητή. Ακόμα και δύσκολη να είναι βοηθάει στο να ωριμάσει η σκέψη του μαθητή και τελικά να βελτιωθεί στις πιο εύκολες ασκήσεις.

Υποθέτουμε ότι έχουμε τις συντεταγμένες 2 αλόγων δηλαδή  (a,b) για το ένα και (i,j) για το άλλο. Εξετάζουμε την πιο γενική περίπτωση δηλαδή το να είναι τα πιόνια στο μέσο της σκακιέρας για να υπάρχουν όσο το δυνατό περισσότερες περιπτώσεις που απειλούνται. Κάνουμε ένα σχήμα και γράφουμε όλες τις δυνατές περιπτώσεις. Αν i,j η θέση του πρώτου ίππου τότε οι θέσεις που πρέπει να έχει ο δεύτερος για να απειλούνται είναι:

α    β
i+2, j-1
i+2, j+1
i+1, j+2
i-1, j+2
i-2, j+1
i-2, j-1
i-1, j-2
i+1, j-2

Αν κάποιος γράψει και τις 8 παραπάνω σχέσεις συνδέοντας της με ένα λογικό «ή» η άσκηση είναι σωστή. Ενδιαφερόμαστε τώρα για να μικρύνουμε τη συνθήκη.

Λόγω του ότι το πρόβλημα δεν εξαρτάται από το σημείο της σκακιέρας αλλά μόνο η σχετική θέση των πιονιών έχει σημασία είναι φανερό ότι η διαφορά των συντεταγμένων έχει σημασία. Έτσι σχηματίζουμε τις ποσότητες a-i και b-j

α    β   α-i  b-j
i+2, j-1  2   -1
i+2, j+1  2    1
i+1, j+2  1    2
i-1, j+2 -1    2
i-2, j+1 -2    1
i-2, j-1 -2   -1
i-1, j-2 -1   -2
i+1, j-2  1   -2

παρατηρούμε ότι οι ποσότητες a-i και b-j παίρνουν τις τιμές 1,-1,2,-2. Επίσης παρατηρούμε  ότι το +1 και το -1 ζευγαρώνουν πάντα με το +2 ή το -2. Άρα η απόλυτη τιμή του αθροίσματος είναι πάντα 3. Μέχρι στιγμής λοιπόν έχουμε τη συνθήκη: |a-i|+|b-j|=3. Όλες οι παραπάνω περιπτώσεις καλύπτονται από αυτή τη συνθήκη.

Το πρόβλημα είναι το εξής: Μήπως υπάρχουν και άλλες περιπτώσεις που καλύπτονται από την παραπάνω συνθήκη ενώ δε θα έπρεπε; Δηλαδή μήπως η συνθήκη |a-i|+|b-j|=3 εκτός από τις παραπάνω 8 περιπτώσεις περιέχει και άλλες. Αν συμβαίνει κάτι τέτοιο τότε σε κάθε μια από τις «άλλες» περιπτώσεις θα καταλήξουμε σε αλγόριθμο που δείχνει τα άλογα να απειλούνται ενώ δε συμβαίνει κάτι τέτοιο.

Πρέπει λοιπόν αναγκαστικά να γίνει ανάλυση της συνθήκης |a-i|+|b-j|=3 και να δούμε τι ακριβώς σημαίνει.

Επειδή οι ποσότητες |a-i| και |b-j| είναι θετικές και ακέραιες, οι μόνες περιπτώσεις που υπάρχουν είναι οι :
|a-i| =0 και |b-j | = 3
|a-i| =1 και |b-j | = 2
|a-i| =2 και |b-j | = 1
|a-i| =3 και |b-j | = 0

Βλέπουμε λοιπόν ότι οι φόβοι μας επαληθεύονται. Οι πρώτη και η τελευταία περίπτωση θα πρέπει να εξαιρεθούν. Άρα χρειαζόμαστε και μια δεύτερη συνθήκη η οποία θα πρέπει να εξαιρεί αυτές τις περιπτώσεις ΧΩΡΙΣ να αγγίζει τις νόμιμες.

Προς εξαίρεση της πρώτης και τελευταίας περίπτωσης μπορούμε να γράψουμε ρητά
(|a-i| =1 και |b-j| =2) ή (|a-i| =2 και |b-j| =1)
Όπου κρατάμε μόνο τις περιπτώσεις που πρέπει και διώχνουμε τις υπόλοιπες.
Ε. . . τώρα μια που φτάσαμε ως εδώ κοιτάμε αν μπορεί να μαζευτεί κι άλλο η συνθήκη.
Αυτό μπορεί να γίνει με |a-i| * |b-j|<>0 που έγραψε ο Άλκης ή με ||a-i|-|b-j||=1 που έγραψα εγώ. Για να μην κουβάλαω και υπολογίζω συνέχεια τις απόλυτες τιμές
τις ονομάζω x και y αντίστοιχα  και προκύπτει ο αλγόριθμος που έγραψα.

ΠΡΟΣΟΧΗ ΤΩΡΑ γιατί δεν έχουμε τελειώσει. Θα πρέπει να επαληθεύσουμε ότι η σύνθετη συνθήκη : (|a-i|+|b-j|=3) και (||a-i|-|b-j||=1) δεν εξαιρεί κάποια από τις 8 συνθήκες απειλής των αλόγων που αναφέρονται αρχικά. Τελικά φαίνεται πως δε συμβαίνει κάτι τέτοιο αλλά ο έλεγχος πρέπει να γίνει. Κάθε νέα συνθήκη που μπαίνει θα πρέπει να δούμε τι πλευρικά αποτελέσματα έχει!

Με τα παραπάνω βλέπουμε ότι ο σχετικά άκομψος τρόπος του να αναφέρεις ρητά και τις 8 συνθήκες  είναι πολύ πιο εύκολο να τον σκεφτείς. Ο «κομψός» τρόπος της συμπαγούς συνθήκης στην πραγματικότητα απαιτεί πολύ περισσότερη δουλειά!