Алгоритмы и структуры данных: продвинутый уровень Сколько способов вернуться в исходную ячейку через n шагов
Выпуск 2. Сколько способов вернуться в исходную ячейку через n шагов
Здравствуйте, !
В этой рассылке я предлагаю прокачивать знания по алгоритмам и
структурам данных. Эти навыки необходимы для программистов,
разработчитков, софтверных инженеров, - для тех, кто хочет создавать быстрые и элегантные фрагменты кода.
Для фрагментов моего кода я буду использовать язык программирования Java.
Не буду растекаться мыслью по древу, а предлагаю сразу же приступить к делу.
Задача. Вы находитесь в ячейке с индексом 0 в массиве длины h. На каждом шаге вы можете перейти влево (но только не в точке 0) или вправо. Из точки 0 можно перейти только вправо. Остаться на месте - это тоже шаг. Сколько способов есть обнаружить себя в точке 0 через n шагов (включая стояние на месте)?
Элегантное рекурсивное решение:
int solve(int pos, int i, int n, int h) {
if (i == n && pos == 0) return 1;
if (i == n) return 0;
if (pos >= h || pos < 0) return 0;
int cnt = 0;
cnt += solve(pos - 1, i + 1, n, h);
cnt += solve(pos, i + 1, n, h);
cnt += solve(pos + 1, i + 1, n, h);
return cnt; }
Для решения нашей задачи нужно вызвать solve(0, 0, n, h), то есть мы в ячейке 0, сделали 0 шагов, нужно сделать n шагов, массив из h элементов.
В рекурсивном решении есть много шагов, которые считаются многократно,
например solve(1, 3, 3, 3) считается аж 5 раз! (Распишите просто
формулу, для n=3). Это означает, что оказаться в точке 1 через 3 шага,
если n=3 и h=3, можно 5 раз.
Для того, чтобы не пересчитывать функция с одними и теми же параметрами несколько раз, мы воспользуемся динамическим программиранием.
public static int solve(int h, int n) {
int d[][] = new int[n+1][h];
for (int i = 0; i<h; i++) {
d[0][i]=0;
}
// first step
d[1][0]=1;
d[1][1]=1;
// other steps
for (int step=2; step<n+1; step++){
for (int position = 0; position<h; position++) {
int a = 0; int b=0;
if (position-1 >= 0) a = d[step-1][position-1];
if (position+1 <h) b = d[step-1][position+1];
d[step][position] = a + d[step-1][position] + b;
}
}
return d[n][0];
}
Объяснение:
Каждая ячейка d[s][x] содержит колинество возможных способов очутиться в точке x после s шагов.
За 1 шаг мы можем остаться в точке 0 или перейти в точку 1. Другие точки недостижимы. Это описано в двух строках после коментария // first step
На шаге 2 мы можем
очутиться в точке 0, оставаясь в ней, или вернувшись из точки 1;
продолжать стоять в точке 1 или перейти из точки 0;
из 1 перейти в 2.
Обобщим: перейти в точку position на шаге step мы можем из точек
position-1, position, position+1, учитывая границы (начало и конец
массива). Но в эти точки мы попали соответственно a, b, c способами за
step-1 шагов. Поэтому суммируем способы достижения этих точек, чтобы
оказаться в точке position на шаге step. Это закодировано в двойном цикле for.
Таким образом, каждую ячейку d[s][x] мы считаем не более 1 раза (некоторые ячейки мы не рассматриваем вообще, как это видно из описания шага 1). Например d[3][1]=5, то есть в ячейке 1 через 3 шага можно попасть 5 способами! И это значение мы подсчитали ровно 1 раз.
Мы заключаем, что сложность алгоритма O(n*h).
***
Всё ли вам было понятно в этом выпуске? Все ли термины известны? Задавайте вопросы, если что-то хотелось бы прояснить.
С уважением, Наталия Македа natalia.macheda at gmail.com 2021-03-03, Trento
Внимание! Письмо, которое вы мне отправите с вопросами и коментариями по тематике данной рассылки, может быть опубликовано полностью или частично в данной рассылке, если в нём нет явного запрета на это.
