Το Project Euler είναι μια σειρά από συναρπαστικά προβλήματα προγραμματισμού, συχνά με μαθηματικό υπόβαθρο. Τα προβλήματα τίθενται συχνά με τέτοιο τρόπο ώστε να πρέπει να αναπτυχθούν εξελιγμένοι αλγόριθμοι προκειμένου να επιτευχθεί ο στόχος σε εύλογο χρόνο. Σήμερα λύνουμε το πρόβλημα 15: Διαδρομές δικτυωτού πλέγματος , για τις οποίες μπορείτε να βρείτε τη λύση με απλά συνδυαστικά μέσα.
Το ερώτημα έχει ως εξής:
„Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?“
Το πρόβλημα μπορεί επίσης να διατυπωθεί διαφορετικά: Αυτό που χρειάζεται είναι η δύναμη του υποσυνόλου όλων των διαδρομών
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Αυτό είναι ένα απλό συνδυαστικό πρόβλημα στο οποίο χρησιμοποιούμε το μοντέλο δοχείου (χωρίς αντικατάσταση και χωρίς εξέταση της παραγγελίας). Ενδιαφερόμαστε τώρα ακριβώς για αυτές τις διαδρομές για τις οποίες υποστηρίζει ότι \(R\) και \(D\) ακριβώς με την ίδια συχνότητα. Αυτό έχει ως αποτέλεσμα όλους τους πιθανούς συνδυασμούς:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Για \(n=20\) έχουμε:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Μπορούμε να επεκτείνουμε το πρόβλημα σε μη τετράγωνα πλέγματα. Η ακόλουθη λύση εφαρμόζει έναν υπολογισμό σε PHP με τη βοήθεια του bcmath με χρόνο εκτέλεσης \( O(n) \) με τη μορφή εισαγωγής "Αριθμός δοκιμαστικών περιπτώσεων, \(n_1\) \(m_1\) , ...":
47bb78215ee0531a787bb5034652eaf4
Παρεμπιπτόντως , όλα τα προβλήματα του Euler Project μπορούν επίσης να λυθούν στο διαδίκτυο στον προτεινόμενο ιστότοπο HackerRank .