В стране Крабодуя телефонные номера состоят из \(N.\) цифр от 0 до 9. Также в этой стране разрешены только номера, полученные спомощью последовательности ходов шахматного коня по данной панели цифр: \[\begin{array}{|c|c|c|} \hline 0 & 1 & 2 \\ \hline 3 & 4 & 5 \\ \hline 6 & 7 & 8 \\ \hline & 9 & \\ \hline \end{array}\]
Т.е. для \(N = 3\) можно составить такие номера: \(1\)-\(8\)-\(3\), \(0\)-\(7\)-\(0\) или \(9\)-\(3\)-\(2\), однако, например, номер \(1\)-\(0\)-\(5\) составить нельзя, т.к. конь не может попасть на цифру 0 за один ход, стоя на цифре 1. Коню запрещается ходить по пустым клеткам. Определите для \(N = 15\) количество возможных номеров в стране Крабодуя. Номер может начинаться и заканчиваться любой из цифр. Для решения задачи рекомендуется написать программу или использовать электронные таблицы
Решим задачу динамически. Сначала поймем, в какие цифры из каких конь может попасть за 1 ход.
В 0 – 5, 7 В 1 – 6, 8
В 2 – 3, 7 В 3 – 2, 8, 9
В 4 – ни откуда не попасть В 5 – 0, 6, 9
В 6 – 1, 5 В 7 – 0, 2
В 8 – 1, 3 В 9 – 3, 5
Создадим двумерную таблицу размера \(10\times N\) и для удобства строки будем нумеровать с \(0\), а столбцы с \(1\). В ячейке \(A_{ij}\) (\(i\) – номер строки, \(j\) – номер столбца) будем хранить количество возможных номеров длины \(j\), оканчивающихся цифрой \(i\). \(1\)-й столбец будет заполнен только единицами, т.к. для любой цифры существует только 1 возможный номер длины 1, заканчивающийся на эту цифру. Второй столбец будем заполнять следующим образом: в цифру \(0\) можно попасть только из цифр \(5\) и \(7\), тогда \(A_{02} = A_{51} + A_{71}\) – получим количество номеров длины \(2\), оканчивающихся цифрой \(0\), аналогично заполним \(A_{12}, A_{22}, ... , A_{92}\). Третий столбец заполним аналогично, прибавляя числа из предыдущего столбца. Так же заметим, что никакой номер длины больше \(1\) не может заканчиваться цифрой \(4\), то есть начиная со второй строки все \(A_{4k}\) будут равны \(0\). Пример таблицы для слов длины \(4\):
Тогда, сложив все числа в последнем столбце, мы найдет количество всевозможных вариантов.
Пример программы на \(Python\) для решения данной задачи
\[\begin{array}{ | l |} \hline Python \\ \hline 1.\ \; a\; =\; [] \\ 2.\ \; ans\; =\; 0 \\ 3.\ \; N\; =\; int(input()) \\ 4.\ \; for\; i\; in\; range(10): \\ 5.\ \; \quad a.append([]) \\ 6.\ \; \quad for\; j\; in\; range(N): \\ 7.\ \; \quad\quad a[i].append(0) \\ 8.\ \; for\; i\; in\; range(10): \\ 9.\ \; \quad a[i][0]\; =\; 1 \\ 10. \; for\; j\; in\; range(1,\; N): \\ 11. \; \quad for\; i\; in\; range(10): \\ 12. \; \quad\quad if\; i\; ==\; 0: \\ 13. \; \quad\quad\quad a[i][j]\; +=\; a[5][j-1]\; +\; a[7][j-1] \\ 14. \; \quad\quad elif\; i\; ==\; 1: \\ 15. \; \quad\quad\quad a[i][j]\; +=\; a[6][j-1]\; +\; a[8][j-1] \\ 16. \; \quad\quad elif\; i\; ==\; 2: \\ 17. \; \quad\quad\quad a[i][j]\; +=\; a[3][j-1]\; +\; a[7][j-1] \\ 18. \; \quad\quad elif\; i\; ==\; 3: \\ 19. \; \quad\quad\quad a[i][j]\; +=\; a[2][j-1]\; +\; a[8][j-1]\; +\; a[9][j-1] \\ 20. \; \quad\quad elif\; i\; ==\; 5: \\ 21. \; \quad\quad\quad a[i][j]\; +=\; a[0][j-1]\; +\; a[6][j-1]\; +\; a[9][j-1] \\ 22. \; \quad\quad elif\; i\; ==\; 6: \\ 23. \; \quad\quad\quad a[i][j]\; +=\; a[1][j-1]\; +\; a[5][j-1] \\ 24. \; \quad\quad elif\; i\; ==\; 7: \\ 25. \; \quad\quad\quad a[i][j]\; +=\; a[0][j-1]\; +\; a[2][j-1] \\ 26. \; \quad\quad elif\; i\; ==\; 8: \\ 27. \; \quad\quad\quad a[i][j]\; +=\; a[1][j-1]\; +\; a[3][j-1] \\ 28. \; \quad\quad elif\; i\; ==\; 9: \\ 29. \; \quad\quad\quad a[i][j]\; +=\; a[3][j-1]\; +\; a[5][j-1] \\ 30. \; for\; i\; in\; range(10): \\ 31. \; \quad ans\; +=\; a[i][N-1] \\ 32. \; print(ans) \\ \hline \end{array}\]
Ответ: 944000