Поиск игры(Найдено Nest)
Вспомнилась игра с какого то видео. Она сама очень простая. Вроде нужно пройти прямо и влево. В конце игрок заходит в комнату с компьютером, на котором запускает опять эту игру и управляет уже вторым героем через 1го. И так можно много рекурсий сделать. Но после 4-5 вроде невозможно управлять. Это 3d игра с видом от первого лица. Никто не знает что за игра такая?
Это сложно, да и зачем мне алгоритмы? Я же фронтендер! Объясняем алгоритмизацию простыми словами
Так как тема прошлого поста про рекурсию был сложноватой для новичков, я решил залупить цикл публикаций о самой алгоритмизации. При этом попытаюсь разжевать все понятнейшим языком, чтобы джун смог с нуля всё понять.
И кстати, мы здесь рассказываем не только про алгоритмы и банально, там нас будет удобнее читать
Зачем мне алгоритмы? Я фронтендер!
Вы наверняка задумались: «А зачем мне нужно тратить своё время на изучение этих сложных алгоритмов, если я работаю с фронтендом? Как знание графов и бинарных деревьев поможет мне лучше отцентровать одну div-ку внутри другой div-ки?»
Многие веб-разработчики на таких форумах, как Reddit и Stack Overflow, отмечали, что, освоив даже на базовом уровне эти фундаментальные основы программирования, чувствовали себя увереннее, профессиональнее и писали более чистый и структурированный код.
Также это помогло им прокачать главный скилл разработчика – умение логически думать и решать сложные технические задачи.
Кстати, именно по этой причине многие крупные IT-компании требуют от своих потенциальных сотрудников знания фундаментальных основ computer science, к которым как раз относятся алгоримты и структуры данных, и с пристрастием спрашивают их на собеседованиях (даже на позицию фронтенд-разработчика!).
Что такое алгоритмы и структуры данных
Алгоритм — это совокупность последовательных операций, направленных на решение определенной задачи.
Структуры данных — это особый способ организации и хранения данных в компьютере, который обеспечивает эффективный доступ к этим данным и их изменение. Для оценки сложности и скорости работы алгоритма используют так называемую «О-нотацию» или «О-большое».
Эта запись имеет вид O(n), где n – это количество операций, которое предстоит выполнить алгоритму. Важное замечание: O(n) всегда описывает худший возможный случай выполнения алгоритма. Это дает нам гарантию, что наш алгоритм никогда не будет работать медленнее O(n).
Скорость работы алгоритмов измеряется не в секундах, а в темпе роста количества операций. Т.е. нас интересует, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.
Вот так выглядит время работы некоторых алгоритмов:
O(1) – константное время. Например, чтение данных из ячейки в массиве.
O(log n) – логарифмическое время. Например, бинарный поиск.
O(n) – линейное время. Например, поиск наименьшего или наибольшего элемента в неотсортированном массиве.
O(n * log n) – линейно-логарифмическое время. Например, быстрая сортировка.
O(n2) – квадратичное время. Например, сортировка пузырьком.
O(n!) – факториальное время. Например, решение задачи коммивояжера полным перебором.
Давайте для начала рассмотрим такой простейший алгоритм, как линейный поиск элемента в массиве, и реализуем его на JavaScript.
Итак, есть массив чисел, и нам нужно найти в нем конкретное число.
Создадим функцию линейного поиска и назовем ее linearSearch. Эта функция будет принимать в себя два параметра: array (т.е. сам массив элементов, в котором ведется поиск) и item (элемент, который мы ищем в этом массиве).
Линейный поиск происходит достаточно предсказуемо: мы используем цикл for, в котором пробегаемся по элементам массива и сравниваем каждый элемент с искомым.
Далее инициализируем счётчик и установим его исходное значение, которое будет равно нулю, так как мы собираемся проверять массив с самого первого элемента.
let i = 0;Наш цикл будет выполняться до тех пор, пока не пройдет по всем элементам массива. В качестве конечной точки мы используем значение array.length, которое возвращает количество элементов в массиве. Так как массив array начинается с нулевого индекса, то мы используем при сравнении знак «<».
i < array.length;
После каждой итерации цикла увеличиваем значение переменной i на единицу.
i++
Далее с помощью условной конструкции if будем проверять на истинность одно условие. Данная проверка будет выполняться при каждой итерации цикла, но код внутри нее сработает только один раз, после чего функция завершится.
Здесь мы сравниваем каждый элемент массива (array[i]) c искомым элементом (item) и, если эти элементы совпадают, то возвращаем i (индекс массива, по которому находится этот искомый элемент item).
Если же искомый элемент не был найден, то по завершении работы цикла мы возвращаем -1.
Дальше нам остается только вызвать функцию linearSearch, первым параметром передать в нее массив элементов, а вторым параметром — искомое число.
Затем, с помощью функции console.log, выводим результат в консоль.
Как видите, алгоритм линейного поиска довольно прост в реализации. Сложность данного алгоритма: линейное время или O(n).
Давайте теперь рассмотрим более сложный и интересный алгоритм, который еще называют алгоритмом бинарного поиска.
Алгоритм бинарного поиска
Бинарный (или двоичный) поиск — это алгоритм, при котором массив данных будет последовательно делиться пополам до тех пор, пока не будет обнаружен искомый элемент.
Важное замечание: данный алгоритм будет работать только для отсортированного массива.
Бинарный поиск может быть реализован следующим образом:
0. Берём исходный массив отсортированных данных (например, по возрастанию).
1. Делим его на две части и находим середину.
2. Сравниваем элемент в середине с искомым элементом.
3. Если искомое число меньше этого центрального элемента — продолжаем искать элемент в левой части массива. Для этого мы делим левую часть массива на 2 части. Если искомый элемент больше центрального элемента, то мы отбрасываем левую часть массива и продолжаем поиск в правой.
И повторяем данную процедуру до тех пор, пока не найдем искомый элемент. Как только мы его нашли, то возвращаем индекс в массиве, по которому он находится. Если же данный элемент не будет найден, то возвращаем -1.
Давайте сначала взглянем на реализацию данного алгоритма, а потом разберем ее детально.
Итак, у нас есть массив чисел arr, отсортированный по возрастанию. Как вы помните, если заранее не отсортировать массив, то бинарный поиск не будет работать.
Создаем функцию binarySearch и передаем в нее два параметра: отсортированный массив arr и искомый элемент value.
Затем определяем следующие переменные:
let start = 0;
Так как мы должны найти центральный элемент, то сначала необходимо определить начальный и конечный элементы.
Задаем таким образом начальный элемент и устанавливаем его значение равным нулю, так как наш массив начинается с нулевого индекса.
let end = arr.length - 1;
Затем определяем конечный элемент. Его позиция будет вычисляться по длине массива arr.length - 1.
Далее мы создадим цикл while, который будет работать до тех пор, пока начальная и конечная позиция массива не сравняются (start <= end).
let middle;
Внутри цикла мы будем высчитывать позицию центрального элемента в массиве и сохранять ее в переменную middle. Для этого мы складываем начальную позицию с конечной и делим результат на две части.
Результат обернем в функцию Math.floor(), так как в результате деления у нас может получиться дробное число. С помощью данной функции мы округляем полученное число до нижней границы.
Далее с помощью условной конструкции if создаем проверку: если центральный элемент в массиве по индексу middle равен искомому элементу, то мы возвращаем индекс найденного элемента, сохраненный в переменной middle. И на этом наша функция завершает свою работу.
Если на данной итерации цикла мы не нашли искомый элемент, то необходимо выполнить еще одну проверку с помощью условной конструкции if. Если искомый элемент меньше, чем элемент, находящийся в середине, то это значит, что нам нужно продолжить поиск в левой части массива, а правую можно отбросить.
Для этого нам нужно изменить значение переменной end. В итоге мы получим end = middle + 1. А в блоке else мы прописываем такое же условие, только для случая, если искомый элемент будет больше, чем элемент, находящийся в середине. Тогда мы отбрасываем левую часть массива и продолжаем поиск в правой.
После завершения цикла while возвращаем -1 на случай, если искомое число не будет найдено в массиве. Далее вызываем функцию binarySearch и передаем в нее два параметра: массив элементов и искомое число.
И выводим результат в консоль.
Что касается оценки сложности приведенных алгоритмов: бинарный поиск эффективнее линейного, поскольку массив данных на каждом шаге разделяется надвое и одна половина сразу отбрасывается.
Последовательная сложность бинарного поиска в худшем и среднем случаях равна O(log n), в лучшем — O(1) (если обнаруживаем искомый элемент на первой итерации). Для сравнения: вычислительная сложность линейного поиска, как вы помните, равна O(n).
На этом мы закончили вторую статью из нашего цикла статей по алгоритмам. Спасибо за внимание.
Не так страшен черт, как его малюют. Объясняем рекурсию в Javascript простыми словами
Для многих разработчиков рекурсия кажется чем-то очень сложным и непонятным, но это только на первый взгляд. В этой статье мы разложим все по полочкам, чтобы вы в следующий раз не боялись этого страшного слова "рекурсия".
Мы узнаем, как устроена рекурсия, а также разберем алгоритм сортировки массива под названием Quick Sort или, как еще его называют, быстрая сортировка Хоара. Как вы уже догадались, этот алгоритм рекурсивный.
Читайте нас в телеграме, там мы каждый день выкладываем полезные материалы из вселенной Front-end
Перейдем к статье
Рекурсия
Рекурсия, если максимально упростить, это вызов функцией самой себя. Этот приём программирования можно использовать, когда есть возможность разбить задачу на несколько более простых подзадач. И, написав решение этой подзадачи в функции и вызывая такую функцию рекурсивно, мы можем все эти подзадачи итеративно решить.
Давайте взглянем на простой пример.
У нас есть простая функция обратного отсчёта:
Данная функция принимает аргументом число n и выводит на экран числовую последовательность от n до 1 включительно, а в конце, после завершения работы цикла, выводит на экран слово «Финиш».
Давайте вызовем эту функцию, передав в нее число 3. В консоли мы получим следующий результат: «3 2 1 Финиш».
Теперь перепишем эту функцию на рекурсивный манер:
Разберемся, как эта функция работает. Первым делом, чтобы не получить бесконечный цикл вызовов функции и как результат ошибку «stack overflow», которая говорит нам о превышении лимита вызовов для функции в стеке, нужно определить так называемый базовый случай.
Базовый случай — это условие, при котором наша функция должна перестать вызывать саму себя рекурсивно.
Так как наш цикл работал до тех пор, пока i > 0, то здесь условие для прерывания цикла должно быть следующим:
То есть, как только n будет меньше или равно нулю, мы перестаем рекурсивно вызывать функцию и выходим из нее. Перед выполнением оператора return необходимо будет вызвать наш console.log('Финиш'), потому что именно это действие и будет последним в работе функции.
По сути, базовый случай работает как оператор break в циклах, то есть прерывает вызов функцией самой себя, чтобы мы могли вернуть результат ее выполнения.
Дальше мы выводим в консоль текущее значение числа n. И, следующим шагом, снова вызываем нашу функцию countDownRecursive() и передаем в нее n - 1.
Как вы помните, в примере с циклом for, на каждой итерации цикла мы уменьшали число i на единицу (i--), поэтому здесь, по аналогии, передаем n - 1.
Запустим функцию и получим в консоли следующий результат:
Результат, как вы видите, аналогичен результату работы простой функции countDown.
Давайте теперь чуть подробнее разберём, как работает рекурсивная функция.
Как работает рекурсивная функция
Итак, сначала мы вызываем функцию countDownRecursive со значением 3.
Базовый случай не отрабатывает, потому что n > 0. Мы выводим число 3 в консоль и дальше снова вызываем функцию, передав в нее n - 1, то есть 3 - 1 или просто число 2.
Повторяем эту процедуру, пока не дойдем до нуля:
И вот здесь уже срабатывает базовый случай. Так как 0 === 0, выводим в консоль слово «Финиш» и дальше срабатывает оператор return.
Дальше происходит завершение работы всех предыдущих функций (потому что неявно завершенная функция возвращает undefined, то есть как только выполнение нашей функции доходит до закрывающей фигурной скобки, происходит return undefined).
Здесь вы можете подумать, что это всё очень сложно, и почему бы не использовать такой понятный и простой цикл for?
Важно отметить, что, действительно, не везде нужно применять рекурсию. Но бывают задачи, где рекурсивное решение выглядет очень элегантно и занимает гораздо меньше строчек кода, чем с использованием традиционных циклов.
Давайте разберем один из таких примеров.
Числа Фибоначчи
Как вы знаете, ряд Фибоначчи — это числовая последовательность, первые два числа которой являются единицами, а каждое последующее за ними число является суммой двух предыдущих.
Автором данной числовой последовательности был Леонардо Пизанский (более известный под прозвищем Фибоначчи) из итальянского города Пизы — один из крупнейших математиков средневековой Европы.
Вот так ряд Фибоначчи выглядит на практике:
Иногда перед первой единицей добавляют еще и ноль, но мы не будем рассматривать данный случай, а рассмотрим классический ряд Фибоначчи, как в средневековых книгах (но только без кроликов).
Наша задача — написать функцию, которой можно передать номер элемента ряда Фибоначчи, и на выходе из функции получить значение этого элемента.
Допустим, мы ищем 10-ый элемент в последовательности. Значением этого элемента будет 55. Для 12-го элемента значением будет 144 и так далее.
Вот так будет выглядеть эта функция, написанная с применением рекурсии:
В результате работы функции в консоли мы получим число 8. Можете это проверить: если вы посмотрите на ряд Фибоначчи выше, то увидите, что значением 6-го элемента в ряду будет число 8.
Давайте разберём, как работает данная функция.
Объявляем стрелочную функцию fibonachi, которая принимает аргументом число искомого элемента в ряду — n.
Далее определяем базовый случай, т.е. условие, при котором выходим из рекурсии.
Так как мы будем последовательно уменьшать число n (об этом ниже), то нет смысла делать это бесконечно.
Как только n оказывается меньше 2, то это значит, что мы достигли начала ряда Фибоначчи, а значит дальше нам двигаться не нужно и можно возвращать n обратно вызывающему коду.
Если же базовый случай не отработал, то снова вызываем функцию, передав в ее аргументы n - 1 и n - 2 соответственно, и складываем результат этих функций между собой по следующей формуле: F(n) = F(n - 1) + F(n - 2). Эта формула позволяет нам найти число из ряда Фибоначчи. Так как каждое число равно сумме двух предыдущих чисел в цепочке, то именно эту формулу мы реализовали в нашей функции.
Если вам до конца не понятно объяснение данного алгоритма, то, во-первых, это абсолютно нормально, а во-вторых, можете посмотреть подробное видео, объясняющее работу данной функции здесь.
Быстрая сортировка Хоара
А теперь рассмотрим более сложный алгоритм. Он называется быстрая сортировка (Quick Sort) или сортировка Хоара.
Данный алгоритм был разработан английским информатиком Тони Хоаром во время работы в МГУ в 1960 году.
И вот здесь как раз будет применяться рекурсия.
Как вы помните, в предыдущей статье мы с вами разбирали широко известный в узких кругах алгоритм — пузырьковую сортировку. Ее единственный недостаток — это крайне низкая эффективность. Быстрая же сортировка является улучшенной версией подобных алгоритмов сортировки с помощью прямого обмена.
Итак, в чем суть. Имеется неотсортированный массив чисел arr.
Наша задача написать функцию, которая будет принимать в себя аргументом этот массив и возвращать его полностью отсортированным по возрастанию.
Быстрая сортировка относится к алгоритмам из серии «разделяй и властвуй».
Небольшое отступление. Алгоритмы типа «разделяй и властвуй» (англ. divide and conquer) — это парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Наш алгоритм будет сводиться к следующим шагам:
1. Выбираем элемент из массива и считаем его опорным (в англоязычной литературе его называют pivot).
2. Сортируем элементы в массиве таким образом, чтобы элементы меньше опорного размещались в подмассиве перед ним, а большие или равные — в подмассиве после.
3. Рекурсивно применяем первые два шага к двум подмассивам слева и справа от опорного элемента. Т.е. дробим наш массив на подмассивы и сортируем их относительно опорного элемента, пока в этих подмассивах не останется по одному элементу или меньше. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы. Это как раз и будет базовым условием, при котором мы прервем рекурсию.
Вот здесь вы можете увидеть визуализацию работы быстрой сортировки (а также многих других алгоритмов).
А вот так выглядит реализация сортировки Хоара на JavaScript:
Подробный разбор алгоритма сортировки Хоара
Давайте подробно разберём, как работает данная сортировка.
Создаем функцию quickSort() и передаем аргументом неотсортированный массив.
Дальше, как вы помните, необходимо определить базовый случай выхода из рекурсии.
Так как нам предстоит дробить основной массив на подмассивы и сортировать элементы в этих подмассивах относительно опорного элемента (об этом ниже), то как только такие подмассивы будут содержать по одному элементу или будут пустыми, нам нет смысла дальше продолжать разбивать их на более мелкие части, поэтому здесь мы выйдем из рекурсии.
Теперь определим индекс в массиве так называемого опорного элемента. Для этого создадим переменную pivotIndex, передадим в функцию Math.floor длину массива, поделим результат на 2 и получившееся число присвоим переменной pivotIndex. Функция Math.floor, как вы знаете, округляет результат в меньшую сторону:
Math.floor(5.5); // 5
Затем определим сам опорный элемент. Для этого кладем в переменную pivot значение массива по индексу pivotIndex. В массиве arr значением pivotIndex будет 5 (длина массива — 11. 11 делим на 2 и округляем в меньшую сторону, получаем 5). Значением pivot будет -12.
Дальше нужно объявить два пустых подмассива less и greater. В массив less будем сохранять все элементы, которые меньше опорного, а в greater все элементы, которые больше опорного.
Дальше в цикле for мы пробегаем по всем элементам массива и сравниваем каждый элемент с опорным.
Затем у нас идут три условия. В первом условии мы сравниваем индекс текущей итерации цикла с индексом опорного элемента в массиве.
Если они совпадают, то текущую итерацию цикла мы завершаем с помощью ключевого слова continue, так как нам не нужно добавлять опорный элемент в один из наших подмассивов.
Далее во втором условии мы сравниваем элемент массива с опорным элементом. Если опорный элемент больше, то добавляем наш текущий элемент массива в массив less.
В противном же случае, добавляем текущий элемент массива в массив greater (третье условие).
В итоге, после завершения цикла for, у нас на выходе будет 2 массива: less с числами меньше опорного и greater с числами больше опорного или равными ему.
И дальше мы возвращаем массив, в который разворачиваем результат рекурсивного выполнения функции, принимающей в качестве аргумента массив less. Дальше вставляем наш опорный элемент pivot, а после снова разворачиваем результат выполнения функции для массива greater.
Когда функция доходит до базового случая, рекурсивный вызов функции заканчивается и все одиночные массивы соединяются в один большой отсортированный массив.
Выведем в консоль результат работы функции и убедимся в этом.
Быстрая сортировка в среднем и лучшем случае выполняется за Θ(n * log(n)) и Ω(n * log(n)) соответственно.
В худшем случае время выполнения алгоритма занимает О(n^2).
Более подробно про лучшее, среднее и худшее время выполнения алгоритма быстрой сортировки можно прочитать здесь.
Спасибо тем, кто дочитал, пишите ваше мнение, вопросы и предложения в комментариях. Не забудьте поставить плюсик этому посту, если он вам понравился :3
Переиграл всех!
Gobtober 2022. День 19 - Барменша
Котейка
Мой первый пост на пикабу. Вот такого зеленоглазика изобразил в Blender
Поиграем в бизнесменов?
Одна вакансия, два кандидата. Сможете выбрать лучшего? И так пять раз.
Рекурсия
Х: Продолжаю собирать комьюнити из CIO и приближенных в фармацевтической отрасли. Специфики у нас хоть отбавляй, давайте объединяться!
Y: Написал тебе в Вацап еще днëм!
Z: Это просто прекрасно: написать в Telegram о том, что написал в WhatsApp. А в WhatsApp написать, что прислал СМС о том, что написал на электронную почту о том, что послал Почтой России бумажное письмо. 🤪🤪🤪
Рекурсия уровня Бог.