Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

18. Обработка вещественных выражений в электронных таблицах

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Обработка вещественных выражений в электронных таблицах

Задание 1 #15421

В стране Крабодуя телефонные номера состоят из \(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\):

image

Тогда, сложив все числа в последнем столбце, мы найдет количество всевозможных вариантов.

Пример программы на \(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

Задание 2 #15423

В стране Крабоклюва телефонные номера состоят из \(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 = 20\) количество возможных номеров в стране Крабоклюва, если на \(10\)-м месте (считая слева) может находиться только цифра 7 Для решения задачи рекомендуется написать программу или использовать электронные таблицы

Решим задачу динамически. Сначала поймем, в какие цифры из каких конь может попасть за 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}\). Третий столбец заполним аналогично, прибавляя числа из предыдущего столбца. В \(10\)-м столбце присвоим всем \(A_{i\hspace{1pt} 10}\) значение \(0\), кроме \(A_{7\hspace{1pt} 10}\), т.к. на 10-м месте может стоять только цифра 7. Пример таблицы для слов длины \(4\):

image

Сложив все числа в последнем столбце, мы найдет количество всевозможных вариантов.

Пример программы на \(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. \; \quad if\; j\; ==\; 10: \\ 31. \; \quad\quad for\; i\; in\; range(10): \\ 32. \; \quad\quad\quad if\; i\; !=\; 7: \\ 33. \; \quad\quad\quad\quad a[i][j]\; =\; 0 \\ 34. \; for\; i\; in\; range(10): \\ 35. \; \quad ans\; +=\; a[i][N-1] \\ 36. \; print(ans) \\ \hline \end{array}\]

Ответ: 4055552

Задание 3 #15424

В стране Краболяндия каждому крабу выдается уникальный номер, состоящий из \(M\) цифр. Номер устроен следующим образом: на \(k\)-й позиции (нумерация начинается с единицы) могут стоять только цифры, являющиеся делителем числа \(k\). Например, на первом месте может стоять только цифра \(1\), на втором месте могут стоять цифры \(1\) и \(2\), на десятом месте могут стоять только цифры \(1, 2\) и \(5\). Найдите количество возможных номеров при \(M=18\)

Решим задачу динамически. Пусть \(N_k\) – количество номеров длины \(k\), и \(s_k\) – количество цифр, которые делят \(k\). Заметим, что \(N_k = N_{k-1}\cdot s_k\), при \(k > 1\). Мы получили рекуррентную формулу, тогда можем решить задачу динамически: \(N_2 = N_1\cdot 2\), \(N_3 = N_2\cdot 2\), \(N_4 = N_3\cdot 3\) и т.д. до \(N_M\).

Пример программы на \(Python\) для решения данной задачи. В \(ans\) будем записывать ответ, а в \(a[i]\) количество цифр, делящих \(i\). \[\begin{array}{ | l |} \hline Python \\ \hline 1.\ \; a\; =\; [] \\ 2.\ \; ans\; =\; 1 \\ 3.\ \; N\; =\; int(input()) \\ 4.\ \; for\; i\; in\; range(N+1): \\ 5.\ \; \quad a.append(0) \\ 6.\ \; for\; i\; in\; range(1,\; N+1): \\ 7.\ \; \quad for\; digit\; in\; range(1,\; 10): \\ 8.\ \; \quad\quad if\; i\; \%\; digit\; ==\; 0: \\ 9.\ \; \quad\quad\quad a[i]\; +=\; 1 \\ 10. \; \quad ans\; *=\; a[i] \\ 11. \; print(ans) \\ \hline \end{array}\]

Ответ: 6220800

Задание 4 #15430

Ладья ходит по шахматной доске размера \(10\times 10\). Определите количество путей, по которым можно попасть из точки \((1, 1)\) в точку \((10, 7)\) (10 – номер строки, 7 – номер столбца), если ладья может ходить только вверх и вправо и не может ходить на закрашенные клетки.

image

Решим задачу динамически. Сначала посчитаем, количество путей в ячейки \((1,1), (1, 2), ..., (1,10)\), \((2, 1), (3, 1), ..., (10, 1).\) Пусть \(A_{ij}\) – количество путей, ведущих в клетку \((i, j)\). \(A_{11} = 1\) (т.к. мы стартуем из этой клетки), \(A_{12} = A_{11}\), \(A_{13} = A_{11} + A_{12}, ... , A_{1\hspace{1pt} 10} = A_{11} + A_{12} + ... + A_{19}\). Аналогично с \(A_{21}, A_{31}, ... , A_{10\hspace{1pt} 1}\). Далее заметим, что количество способов попасть в любую клетку, это сумма всех клеток, которые находятся ниже и левее данной. Получим:

image

Динамически посчитаем все остальные \(A_{ij}\) способом, описанным выше. При этом закрашенные клетки будем обнулять, т.к. количество способов попасть в них равно \(0\). Тогда ответом будет \(A_{10\hspace{1pt} 7}\).

Пример программы на \(Python\) для решения данной задачи. В программе все индексы на 1 меньше, т.к. нумерация начинается с 0.

\[\begin{array}{ | l |} \hline Python \\ \hline 1. \; a\; =\; [] \\ 2. \; for\; i\; in\; range(10): \\ 3. \; \quad a.append([]) \\ 4. \; \quad for\; j\; in\; range(10): \\ 5. \; \quad\quad a[i].append(0) \\ 6. \; a[0][0]\; =\; 1 \\ 7. \; \quad \\ 8. \; for\; j\; in\; range(1,\; 10): \\ 9. \; \quad for\; k\; in\; range(j): \\ 10. \; \quad\quad a[0][j]\; +=\; a[0][k] \\ 11. \; for\; i\; in\; range(1,\; 10): \\ 12. \; \quad for\; k\; in\; range(i): \\ 13. \; \quad\quad a[i][0]\; +=\; a[k][0] \\ 14. \; \quad \\ 15. \; for\; i\; in\; range(1,\; 10): \\ 16. \; \quad for\; j\; in\; range(1,\; 10): \\ 17. \; \quad\quad for\; k\; in\; range(i): \\ 18. \; \quad\quad\quad a[i][j]\; +=\; a[k][j] \\ 19. \; \quad\quad for\; k\; in\; range(j): \\ 20. \; \quad\quad\quad a[i][j]\; +=\; a[i][k] \\ 21. \; \quad\quad if\; (i\; ==\; 3\; and\; j\; ==\; 1)\; or\; (i\; ==\; 5\; and\; j\; ==\; 3)\; or \\ 22. \; \quad\quad\quad (i\; ==\; 6\; and\; j\; ==\; 3)\; or\; (i\; ==\; 2\; and\; j\; ==\; 7)\; or \\ 23. \; \quad\quad\quad (i\; ==\; 7\; and\; j\; ==\; 9): \\ 24. \; \quad\quad\quad a[i][j]\; =\; 0 \\ 25. \; print(a[9][6]) \\ \hline \end{array}\]

Ответ: 698476