marsenis
Νεοφερμένος
Ο Μάκης αυτή τη στιγμή δεν είναι συνδεδεμένος. Είναι 31 ετών, Μαθητής Γ' λυκείου και μας γράφει απο Αθήνα (Αττική). Έχει γράψει 19 μηνύματα.
19-01-09
17:38
Αυτή τη φορά η λύση σου φαίνεται ότι δουλεύει σωστά. Αν κατάλαβα καλά, το πρόγραμμά σου κατά κάποιο τρόπο ακολουθεί κάθε πιθανό μονοπάτι από τη θέση (n, 1) μέχρι τη θέση (1, n) και κρατάει εκείνο με το ελάχιστο κόστος. Όμως ο αριθμός των πιθανών μονοπατιών που υπάρχουν αυξάνετε πολύ γρήγορα σε σχέση με τις διαστάσεις της σκακιέρας οπότε το πρόγραμμά σου θα είναι πολύ αργό ακόμα και για σκακιέρες μικρών διαστάσεων. Για παράδειγμα δοκίμασα να τρέξω το πρόγραμμά σου από τον διερμηνευτή της γλώσσας με είσοδο μια σκακιέρα 7x7 και έκανε περίπου 2 λεπτά για να βρει το μονοπάτι με το ελάχιστο κόστος (δοκίμασα και από την γλωσσομάθεια αλλά βγάζει σφάλμα για σκακιέρες μεγαλύτερες από 7x7, μάλλον επειδή γίνονται πολλές αναδρομικές κλήσεις διαδικασιών).
Υπάρχει και πολύ πιο γρήγορη λύση αν παρατηρήσεις ότι μπορείς να βρεις το μονοπάτι με το ελάχιστο κόστος από την αρχή μέχρι τη θέση (x, y) πολύ γρήγορα αν ξέρεις το μονοπάτι με το ελάχιστο κόστος από την αρχή μέχρι τη θέση (x+1, y) και (x, y-1). Αυτή η μέθοδος ονομάζεται δυναμικός προγραμματισμός. Συγκριτικά η λύση αυτή ακόμα και για σκακιέρες με μέγεθος μεγαλύτερο από 100x100 βρίσκει λύση σε μερικά δευτερόλεπτα.
Θες να σου πω λεπτομέρειες για αυτή τη λύση ή θες να το προσπαθήσεις λίγο μόνος σου??
Υπάρχει και πολύ πιο γρήγορη λύση αν παρατηρήσεις ότι μπορείς να βρεις το μονοπάτι με το ελάχιστο κόστος από την αρχή μέχρι τη θέση (x, y) πολύ γρήγορα αν ξέρεις το μονοπάτι με το ελάχιστο κόστος από την αρχή μέχρι τη θέση (x+1, y) και (x, y-1). Αυτή η μέθοδος ονομάζεται δυναμικός προγραμματισμός. Συγκριτικά η λύση αυτή ακόμα και για σκακιέρες με μέγεθος μεγαλύτερο από 100x100 βρίσκει λύση σε μερικά δευτερόλεπτα.
Θες να σου πω λεπτομέρειες για αυτή τη λύση ή θες να το προσπαθήσεις λίγο μόνος σου??
Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.
marsenis
Νεοφερμένος
Ο Μάκης αυτή τη στιγμή δεν είναι συνδεδεμένος. Είναι 31 ετών, Μαθητής Γ' λυκείου και μας γράφει απο Αθήνα (Αττική). Έχει γράψει 19 μηνύματα.
15-01-09
17:35
Δοκίμασες να τρέξεις το πρόγραμμά σου χρησιμοποιώντας το διερμηνευτή της γλώσσας ή τη γλωσσομάθεια?? Εγώ δοκίμασα να τρέξω το πρόγραμμα σου αλλά μου βγάζει λάθος κινήσεις. Για παράδειγμα δοκίμασα μία σκακιέρα 3x3 με όλα τα κόστη να είναι 1 και το μονοπάτι είναι λάθος, δεν καταλήγει δηλαδή στο πάνω-δεξιά κουτάκι(εδώ μάλλον φταίει το ότι έχεις βάλει Π[2*Ν-1, 1] <-- Ν ενώ θέλει Π[2*Ν-1, 1] <-- 1 στη γραμμή 62). Δοκίμασα και με μία άλλη σκακιέρα αφού είχα διορθώσει το Π[2*Ν-1, 1] <-- Ν και μου βγάζει επιτρεπτές κινήσεις αυτή τη φορά αλλά όχι με το ελάχιστο δυνατό κόστος. Επίσης παρατήρησα τα εξής:
α)Δεν αρχικοποιείς ποτέ την μεταβλητή ΚΟ.
β)Στη διαδικασία ΣΤΕΠ γράφεις:
ΑΝ X>N1 τότε ο κώδικας μέσα στο ΓΙΑ δεν εκτελείτε. Το ίδιο συμβαίνει και όταν Χ<=Ν1. Άρα ο περισσότερος κώδικας που έχεις στην διαδικασία ΣΤΕΠ δεν εκτελείτε ποτέ.
Επίσης θα μπορούσες να εξηγήσεις λίγο τον κώδικά σου γιατί αν κατάλαβα καλά τι κάνει το πρόγραμμά σου μάλλον υπάρχει και πιο γρήγορος τρόπος να το λύσεις αυτό το πρόβλημα.
α)Δεν αρχικοποιείς ποτέ την μεταβλητή ΚΟ.
β)Στη διαδικασία ΣΤΕΠ γράφεις:
Code:
ΑΝ Χ>Ν1 ΤΟΤΕ
ΓΙΑ Χ1 ΑΠΟ Χ ΜΕΧΡΙ Ν1
.....
Επίσης θα μπορούσες να εξηγήσεις λίγο τον κώδικά σου γιατί αν κατάλαβα καλά τι κάνει το πρόγραμμά σου μάλλον υπάρχει και πιο γρήγορος τρόπος να το λύσεις αυτό το πρόβλημα.
Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.