Ένα πεντάγωνο νησί έχει ένα αεροδρόμιο που βρίσκεται στην πόλη του Winchester. Ένας σιδηρόδρομος συνδέει τις πέντε πόλεις του νησιού - Winchester, Bennettsville, Columbus, Flint, και Ventura.
Όταν προσγειώνεστε στο αεροδρόμιο του Winchester, σας δίνεται ένα δωρεάν εισιτήριο, για οκτώ ταξίδια με το τρένο, μεταξύ μιας πόλης και της διπλανής. Με πόσους διαφορετικούς τρόπους μπορείτε να κάνετε ένα ταξίδι που αποτελείται από ακριβώς οκτώ μικρότερα ταξίδια και αρχίζει και τελειώνει στο Winchester;
Π. χ. μία διαδρομή είναι:
W - Β - W - Β - W - Β - W - B - W.
Μια πιθανή προσέγγιση θα ήταν ίσως η εξής:
ΑπάντησηΔιαγραφήΓια καθένα από τα 8 κομμάτια του ταξιδιού, με δεδομένη μια πόλη αφετηρίας, οι δυνατοί προορισμοί – γειτονικές πόλεις είναι 2. Ξεκινώντας από το W, τα 4 πρώτα κομμάτια του ταξιδιού, ανεξαρτήτως κατάληξης, μπορούν να γίνουν με 2^4=16 διαφορετικούς τρόπους / διαδρομές. Από τις 16 αυτές (μισές) διαφορετικές διαδρομές, οι 6 καταλήγουν στο W, οι 4 στο F, οι 4 στο C, η 1 στο B και η 1 στο V. Για να βρούμε τώρα, με αφετηρία καθεμιά από τις πόλεις αυτές, με ποιους τρόπους τα 4 τελευταία κομμάτια του ταξιδιού καταλήγουν ξανά στο W, πρέπει κάθε διαδρομή που κατέληξε στο τέλος των 4 πρώτων κομματιών σε μια συγκεκριμένη πόλη να συνδυαστεί με κάθε αντίθετη διαδρομή που ξεκινάει από την ίδια πόλη και καταλήγει στο W.
Επομένως, οι τρόποι για να ξεκινήσουμε από το W και να τελειώσουμε το πλήρες ταξίδι πάλι στο W είναι συνολικά: 6^2+4^2+4^2+1^2+1^2 = 70
H Brute force Ευριστική επιβεβαιώνει το Θανάση! 70 τρόποι. Ξεκινώντας με ρίζα (root) το W δημιουργείται δέντρο (tree graph) με συμμετρία άνω και κάτω μισού.
ΑπάντησηΔιαγραφήΑΝΩ ΜΙΣΟ (35 διαδρομές)
W-B-W-B-W-B-W-B-W
W-B-W-B-W-B-W-V-W
W-B-W-B-W-B-C-B-W
W-B-W-B-W-V-W-B-W
W-B-W-B-W-V-W-V-W
W-B-W-B-W-V-F-V-W
W-B-W-B-C-B-W-B-W
W-B-W-B-C-B-W-V-W
W-B-W-B-C-B-C-B-W
W-B-W-B-C-F-C-B-W
W-B-W-V-W-B-W-B-W
W-B-W-V-W-B-W-V-W
W-B-W-V-W-B-C-B-W
W-B-W-V-W-V-W-B-W
W-B-W-V-W-V-W-V-W
W-B-W-V-W-V-F-V-W
W-B-W-V-F-C-F-V-W
W-B-W-V-F-V-W-V-W
W-B-W-V-F-V-W-B-W
W-B-W-V-F-V-F-V-W
W-B-C-B-W-B-W-B-W
W-B-C-B-W-B-W-V-W
W-B-C-B-W-B-C-B-W
W-B-C-B-W-V-W-B-W
W-B-C-B-W-V-W-V-W
W-B-C-B-W-V-F-V-W
W-B-C-B-C-B-W-B-W
W-B-C-B-C-B-W-V-W
W-B-C-B-C-B-C-B-W
W-B-C-B-C-F-C-B-W
W-B-C-F-C-B-W-B-W
W-B-C-F-C-B-W-V-W
W-B-C-F-C-B-C-B-W
W-B-C-F-C-F-C-B-W
W-B-C-F-V-F-C-B-W
ΚΑΤΩ ΜΙΣΟ (35 διαδρομές)
w-v-f-c-b-c-f-v-w
w-v-f-c-f-c-f-v-w
w-v-f-c-f-v-f-v-w
w-v-f-c-f-v-w-b-w
w-v-f-c-f-v-w-v-w
w-v-f-v-f-c-f-v-w
w-v-f-v-f-v-f-v-w
w-v-f-v-f-v-w-b-w
w-v-f-v-f-v-w-v-w
w-v-f-v-w-b-c-b-w
w-v-f-v-w-b-w-b-w
w-v-f-v-w-b-w-v-w
w-v-f-v-w-v-f-v-w
w-v-f-v-w-v-w-b-w
w-v-f-v-w-v-w-v-w
w-v-w-b-c-b-c-b-w
w-v-w-b-c-b-w-b-w
w-v-w-b-c-b-w-v-w
w-v-w-b-c-f-c-b-w
w-v-w-b-w-b-c-b-w
w-v-w-b-w-b-w-b-w
w-v-w-b-w-b-w-v-w
w-v-w-b-w-v-f-v-w
w-v-w-b-w-v-w-b-w
w-v-w-b-w-v-w-v-w
w-v-w-v-f-c-f-v-w
w-v-w-v-f-v-f-v-w
w-v-w-v-f-v-w-b-w
w-v-w-v-f-v-w-v-w
w-v-w-v-w-b-c-b-w
w-v-w-v-w-b-w-b-w
w-v-w-v-w-b-w-v-w
w-v-w-v-w-v-f-v-w
w-v-w-v-w-v-w-b-w
w-v-w-v-w-v-w-v-w
Γιώργη, ευχαριστώ! Και μόνο που μπήκες στον κόπο να τους γράψεις, αν το 'χα το εισιτήριο να είσαι σίγουρος ότι θα σου το χάριζα :-)
ΑπάντησηΔιαγραφήΓια να είμαι ειλικρινής, δεν τούς έγραψα,αλλά τους αντέγραψα. Οπότε keep the ticket dude! It's rightfully yours! :-)
ΔιαγραφήLook, let me explain something to you. I'm not the Dude. You're the Dude. I'm Mr. Papadim :-)
Διαγραφή(Δεν τα είπε ακριβώς έτσι ο Bridges στο The Big Lebowski, αλλά το το Mr. Papadim - ή κ. Papadim καλύτερα - έχει γράψει..)
Aπαντώ με ορίτζιναλ Ντάσιελ Χάμετ και "Γεράκι της Μάλτας":
Διαγραφήyou’re not in Romeville now. You’re in my burg! (dude..)
Call me Spade :-)