| Главная » Статьи » Java » Java Ranger Basic |
День 21/21
| Recursion, Graph Theory При построении каких-то алгоритмов в любом языке программирования зачастую приходится какие-то блоки кода повторять и повторять. Есть два способа множество раз повторить один и тот же кусок кода в ситуации, когда мы кодируем программу и то, сколько раз повторить код, будет известно только в момент выполнения. Это либо циклы, либо рекурсия. Рекурсия – это ситуация, когда объект является частью самого себя. Рекурсия очень важна, потому что она показывает очень детально, что такое вызов метода, а также это очень важно при работе с исключениями (исключения – это такой «странный» способ покинуть метод. И вопрос если мы покидаем метод – где мы оказываемся? При return мы возвращаемся в предыдущий метод, а при исключении – на много методов назад, и тут надо понимать, как методы вызывались). Еще одна причина – большинство красивых математических задач решаются рекурсивными алгоритмами, потому что в большинстве задач рекурсия работает лучше, чем циклы. Рекурсия может быть прямая и косвенная. Прямая проще, чем косвенная, и используется она чаще. Прямая рекурсия – это когда прямо в теле метода непосредственно вызывается он. Косвенная рекурсия – это когда в теле одного метода вызывается второй метод, а в теле второго – вызывается первый метод. Косвенность может быть еще большей. Рекурсия также может быть без ветвления и с ветвлением. Если мы видим, что внутри какого-то метода он же вызывается более одного раза, то это называется рекурсия с ветвлением. Яркий пример рекурсии с ветвлением – числа Фибоначчи. Функция Фибоначчи имеет вид: F(k) = F(k – 2) + F(k – 1), то есть каждое следующее значение функции получается, как сумма двух предыдущих. Эта примерно степенная функция и она растет со скоростью: Fk ~ (1.68)k. Реализация имеет вид: public static int fib(int arg) { return arg < 2 ? 1 : fib(arg - 2) + fib(arg - 1); } Граф – это совокупность непустого множества вершин и наборов пар вершин (связей между вершинами). Дерево – это связанный ациклический граф. Связанность означает наличие путей между любой парой вершин, ацикличность – отсутствие циклов и то, что между парами вершин имеется только по одному пути. Когда в программировании появляются деревья, есть много способов перебрать все вершины, но есть два основных: обход в глубину и обход в ширину.  public static void main(String args) { fib(5); } -> 5 3 1 2 0 1 4 2 0 1 3 1 2 0 1 // Обход рекурсией в глубину Здесь обход в ширину будет идти в такой последовательности: 5; 3, 4; 1, 2, 2, 3; 0, 1, 0, 1, 1, 2; 0, 1; Но рекурсия обходит не так! Рекурсия действует в глубину: она приходит к развилке, обходит с какой-то стороны, например, справа налево. Она берет правый ход, заходит туда и когда справа она все обойдет до 1 или 0 (потому что у нас arg < 2 = 1), тогда возвращается и заходит в следующий, погружается, все обходит, возвращается, заходит в следующий. Обход в глубину в схеме выше будет идти в такой последовательности: 5 -> 3 -> 1; 3 -> 2 -> 0; 2 -> 1 5 -> 4 -> 2 -> 0; 2 -> 1 4 -> 3 -> 1; 3 -> 2 -> 0; 2 -> 1 Обход в глубину применяется еще при формировании дерева папок в файловой системе. Во многих случаях нужен обход в ширину, а рекурсия его не делает. Яркий пример – как компьютерные программы играют в шахматы. Машина смотрит на поле и перебирает все возможные ходы (их не так много: всего 16 фигур, пустых ячеек 32, всего около 100 ходов). В итоге получается дерево. И дальше появляется проблема, вообще говоря, в шахматной программе нельзя делать поиск в глубину, потому что некоторые ветки бесконечно глубокие (например, когда одна фигура убегает от другой). Тут рекурсия вообще не работает, потому что в результате будет исключение StackOverflowError. Правда существует правило, что если в результате 50 ходов ни была убита ни одна фигура, то объявляется ничья. Тут нужно обходить все возможные варианты в ширину, углубляясь на несколько шагов и учитывая результативность каждого хода. Источник: http://becomejavasenior.com/courses/?utm_source=Java+Email+Courses&utm_campaign=aa710df388-JavaRangerBasicIntro&utm_medi | |
| Просмотров: 438 | | |
| Всего комментариев: 0 | |