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
21:15
αυτό το πρόβλημα, τι επιπέδου είναι; εννοώ, πανεπιστημιακό;
Τέτοιου είδους προβλήματα δεν κάνουμε στο Λύκειο (στην Ελλάδα τουλάχιστον) άρα μπορεί να θεωρηθεί πανεπιστημιακού επιπέδου αν και παρόμοια (και πολύ πιο δύσκολα συνήθως) προβλήματα βάζουν σε Διεθνείς Διαγωνισμούς Πληροφορικής στους οποίους παίρνουν μέρος μόνο μαθητές Γυμνασίου και Λυκείου!
Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.