<section id="description">
<p>Вероятно, вы знакомы со стопкой книг на своем столе. Вероятно, вы использовали функцию отмены текстового редактора. Вы также, вероятно, используете для нажатия кнопки «Назад» на своем телефоне, чтобы вернуться к предыдущему виду в приложении. Вы знаете, что у них общего? Все они хранят данные таким образом, чтобы вы могли перемещаться назад. Самая верхняя книга в стеке была той, которая была помещена последней. Если вы удалите эту книгу из верхней части стека, вы откроете книгу, которая была помещена туда до последней книги, и так далее. Если вы думаете об этом, во всех приведенных выше примерах вы получаете тип обслуживания <dfn>Last-In-First-Out</dfn> . Мы постараемся имитировать это с помощью нашего кода. Эта схема хранения данных называется <dfn>стеком</dfn> . В частности, нам пришлось бы реализовать метод <code>push()</code> который толкает объекты JavaScript вверху стека; и <code>pop()</code> , который удаляет объект JavaScript, который находится в верхней части стека в текущий момент.</p></section>

Learn how a Stack Works

<section id="description">
<p>В последнем разделе мы говорили о том, что такое стек и как мы можем использовать массив для представления стека. В этом разделе мы создадим собственный класс стека. Хотя вы можете использовать массивы для создания стеков, иногда лучше ограничивать количество контроля, которое у нас есть с нашими стопами. Помимо метода <code>push</code> и <code>pop</code> , у стеков есть и другие полезные методы. Давайте добавим <code>peek</code> , <code>isEmpty</code> и <code>clear</code> метод в наш класс стека. Инструкции Напишите метод <code>push</code> который подталкивает элемент к вершине стека, метод <code>pop</code> который удаляет элемент в верхней части стека, метод <code>peek</code> который смотрит на первый элемент в стеке, метод <code>isEmpty</code> который проверяет, стек пуст и <code>clear</code> метод, который удаляет все элементы из стека. Обычно у стеков это не так, но мы добавили метод вспомогательной <code>print</code> котором консоль регистрирует коллекцию.</p></section>

Create a Stack Class

<section id="description">
<p>Как и стеки, очереди представляют собой набор элементов. Но, в отличие от стеков, очереди следуют принципу FIFO (First-In First-Out). Элементы, добавленные в очередь, помещаются в хвост или конец очереди, и только элемент в передней части очереди разрешен для удаления. Мы могли бы использовать массив для представления очереди, но точно так же, как стеки, мы хотим ограничить количество контроля над нашими очередями. Двумя основными методами класса очереди являются метод enqueue и dequeue. Метод enqueue подталкивает элемент к хвосту очереди, а метод dequeue удаляет и возвращает элемент в передней части очереди. Другими полезными методами являются методы front, size и isEmpty. Инструкции. Напишите метод enqueue, который подталкивает элемент к хвосту очереди, метод dequeue, который удаляет и возвращает передний элемент, передний метод, который позволяет нам видеть передний элемент, метод размера, который показывает длину, и метод isEmpty чтобы проверить, пуста ли очередь.</p></section>

Create a Queue Class

<section id="description">
<p>Другой общей структурой данных, с которой вы столкнетесь в информатике, является <dfn>связанный список</dfn> . Связанный список представляет собой линейный набор элементов данных, называемый «узлами», каждый из которых указывает на следующий. Каждый <dfn>узел</dfn> в связанном списке содержит две ключевые части информации: сам <code>element</code> и ссылку на следующий <code>node</code> . Представьте, что вы находитесь в линии конги. У вас есть руки на следующем человеке в очереди, и человек, стоящий за вами, держит вас в руках. Вы можете видеть человека прямо перед собой, но они блокируют взгляд других людей в очереди. Узел точно так же, как человек в линии конги: они знают, кто они, и они могут видеть только следующего человека в очереди, но они не знают других людей впереди или позади них.</p></section>

Work with Nodes in a Linked List

<section id="description">
<p>Let's create a <code>linked list</code> class. Every linked list should start out with a few basic properties: a <code>head</code> (the first item in your list) and a <code>length</code> (number of items in your list). Sometimes you'll see implementations of linked lists that incorporate a <code>tail</code> for the last element of the list, but for now we'll just stick with these two. Whenever we add an element to the linked list, our <code>length</code> property should be incremented by one.</p>
<p>We'll want to have a way to add items to our linked list, so the first method we'll want to create is the <code>add</code> method.</p>
<p>If our list is empty, adding an element to our linked list is straightforward enough: we just wrap that element in a <code>Node</code> class, and we assign that node to the <code>head</code> of our linked list.</p>
<p>But what if our list already has one or more members? How do we add an element to the list? Recall that each node in a linked list has a <code>next</code> property. To add a node to the list, find the last node in the list, and point that last node's <code>next</code> property at our new node. (Hint: you know you've reached the end of a linked list when a node's <code>next</code> property is <code>null</code>.)</p></section>

Create a Linked List Class

<section id="description">
<p>Следующим важным методом, который потребуется для любой реализации связанного списка, является метод <code>remove</code> . Этот метод должен взять элемент, который мы хотим удалить в качестве аргумента, а затем выполнить поиск в списке, чтобы найти и удалить узел, содержащий этот элемент. Всякий раз, когда мы удаляем узел из связанного списка, важно, чтобы мы не случайно оставили все остальное в списке. Напомним, что <code>next</code> свойство <code>next</code> узла указывает на узел, который следует за ним в списке. Если мы удалим средний элемент, скажем, мы хотим убедиться , что у нас есть связь с предыдущим узлом этого элемента <code>next</code> имущества к середине элемента <code>next</code> имуществу (который является следующим узлом в списке!) Это может показаться действительно запутанный, так что давайте вернемся к примеру линии conga, чтобы у нас была хорошая концептуальная модель. Представьте себя в линии конги, и человек прямо перед вами покинет линию. Лицо, которое только что покинуло линию, больше не имеет руки на кого-либо в очереди - и у вас больше нет рук на лице, которое осталось. Вы шагнете вперед и положите руки на следующего человека, которого видите. Если элемент мы хотим , чтобы удалить это <code>head</code> элемент, мы переназначить <code>head</code> на второй узел связанного списка.</p></section>

Remove Elements from a Linked List

<section id="description">
<p>Давайте добавим еще несколько полезных методов в наш связанный класс списка. Не было бы полезно, если бы мы могли сказать, был ли наш список пустым или нет, как в наших классах <code>Stack</code> и <code>Queue</code> ? Мы также должны иметь возможность находить определенные элементы в нашем связанном списке. Прохождение через структуры данных - это то, с чем вы захотите получить много практики! Давайте создадим метод <code>indexOf</code> который принимает <code>element</code> в качестве аргумента и возвращает <code>index</code> этого элемента в связанном списке. Если элемент не найден в связанном списке, верните <code>-1</code> . Давайте также реализуем метод, который делает обратное: метод <code>elementAt</code> который принимает <code>index</code> в качестве аргумента и возвращает <code>element</code> в указанном <code>index</code> . Если ни один <code>element</code> не найден, возвращайте <code>undefined</code> .</p></section>

Search within a Linked List

<section id="description">
<p>Прежде чем перейти к другой структуре данных, давайте получим пару последних бит практики со связанными списками. Давайте напишем <code>removeAt</code> который удаляет <code>element</code> по заданному <code>index</code> . Метод следует называть <code>removeAt(index)</code> . Чтобы удалить <code>element</code> с определенным <code>index</code> , нам нужно сохранить количество запусков каждого узла при перемещении по связанному списку. Обычный метод, используемый для итерации через элементы связанного списка, включает в себя <dfn>«бегун»</dfn> или дозорный, который «указывает» на узлы, которые сравнивает ваш код. В нашем случае, начиная с <code>head</code> нашего списка, мы начинаем с переменной <code>currentIndex</code> которая начинается с <code>0</code> . <code>currentIndex</code> должен увеличиваться на единицу для каждого проходящего узла. Так же, как наш метод <code>remove(element)</code> , мы должны быть осторожны, чтобы не осилить остальную часть нашего списка, когда мы удаляем узел в нашем методе removeAt (index). Мы держим наши узлы смежными, убедившись, что узел, имеющий ссылку на удаленный узел, имеет ссылку на следующий узел.</p></section>

Remove Elements from a Linked List by Index

<section id="description">
<p>Давайте создадим метод addAt (index, element), который добавит элемент в данный индекс. Точно так же, как мы удаляем элементы с заданным индексом, нам нужно отслеживать currentIndex, когда мы пересекаем связанный список. Когда currentIndex соответствует указанному индексу, нам нужно переназначить следующее свойство предыдущего узла для ссылки на новый добавленный узел. И новый узел должен ссылаться на следующий узел в currentIndex. Возвращаясь к примеру линии conga, новый человек хочет присоединиться к линии, но он хочет присоединиться к середине. Вы находитесь в середине линии, поэтому вы отнимаете руки у человека впереди вас. Новый человек ходит и кладет руки на человека, которого вы когда-то держали, и теперь у вас есть руки на нового человека. Инструкции Создайте метод addAt (index, element), который добавляет элемент в данный индекс. Возвращает false, если элемент не может быть добавлен. Примечание. Не забудьте проверить, является ли данный индекс отрицательным или длиннее длины связанного списка.</p></section>

Add Elements at a Specific Index in a Linked List

<section id="description">
<p>Массивы - это объекты JavaScript, которые могут содержать множество разных элементов. <code>var complexArr = [1, 5, "2", "Word", {"name": "James"}];</code> В основном, что происходит в фоновом режиме, так это то, что ваш браузер автоматически предоставит необходимый объем памяти для этого массива. Он также будет изменяться по мере необходимости, если вы добавите или удалите данные. Тем не менее, в мире высокой производительности и разных типов элементов иногда требуется более конкретная информация о том, сколько памяти передано массиву. Ответы на эту проблему вызывают <dfn>типизированные массивы</dfn> . Теперь вы можете сказать, сколько памяти вы хотите дать массиву. Ниже представлен базовый обзор различных типов доступных массивов и размер в байтах для каждого элемента в этом массиве. <table class="table table-striped"><tbody><tr><th> Тип </th><th> Размер каждого элемента в байтах </th></tr><tr><td> <code>Int8Array</code> </td> <td> 1 </td></tr><tr><td> <code>Uint8Array</code> </td> <td> 1 </td></tr><tr><td> <code>Uint8ClampedArray</code> </td> <td> 1 </td></tr><tr><td> <code>Int16Array</code> </td> <td> 2 </td></tr><tr><td> <code>Uint16Array</code> </td> <td> 2 </td></tr><tr><td> <code>Int32Array</code> </td> <td> 4 </td></tr><tr><td> <code>Uint32Array</code> </td> <td> 4 </td></tr><tr><td> <code>Float32Array</code> </td> <td> 4 </td></tr><tr><td> <code>Float64Array</code> </td> <td> 8 </td></tr></tbody></table> Существует два способа создания таких массивов. Один из способов - создать его напрямую. Ниже <code>Int16Array</code> как создать <code>Int16Array</code> длиной 3 длины. <blockquote> var i8 = новый Int16Array (3); <br> console.log (i8); <br> // Возвращает [0, 0, 0] </blockquote> Вы также можете создать <dfn>буфер,</dfn> чтобы указать, сколько данных (в байтах) требуется массиву. <strong>Заметка</strong> <br> Чтобы создать типизированные массивы с использованием буферов, вам необходимо назначить количество байтов кратным байтам, перечисленным выше. <blockquote> // Создаем такой же массив Int16Array по-разному <br> var byteSize = 6; // Требуется быть кратным 2 <br> var buffer = new ArrayBuffer (byteSize); <br> var i8View = новый Int16Array (буфер); <br> buffer.byteLength; // Возвращает 6 <br> i8View.byteLength; // Возвращает 6 <br> console.log (i8View); // Возвращает [0, 0, 0] </blockquote> <dfn>Буферы</dfn> представляют собой объекты общего назначения, которые просто переносят данные. Вы не можете получить к ним доступ в обычном режиме. Чтобы получить к ним доступ, вам нужно сначала создать <dfn>представление</dfn> . <blockquote> i8View [0] = 42; <br> console.log (i8View); // Возвращает [42, 0, 0] </blockquote> <strong>Заметка</strong> <br> Типизированные массивы не имеют некоторых методов, которые имеют традиционные массивы, такие как <code>.pop()</code> или <code>.push()</code> . В типизированных массивах также отсутствует <code>Array.isArray()</code> который проверяет, что-то есть массив. Хотя это проще, это может быть преимуществом для менее сложных JavaScript-движков для их реализации.</p></section>

Typed Arrays

<section id="description">
<p>В этих упражнениях мы собираемся создать функцию удаления для нашего набора. Функция должна быть названа <code>this.remove</code> . Эта функция должна принимать значение и проверять, существует ли он в наборе. Если это так, удалите это значение из набора и верните true. В противном случае верните false.</p></section>

Remove from a Set

<section id="description">
<p>В этом упражнении мы собираемся выполнить объединение на двух наборах данных. Мы создадим метод в нашей структуре данных <code>Set</code> называемый <code>union</code> . Этот метод должен принимать другой <code>Set</code> в качестве аргумента и возвращать <code>union</code> двух наборов, исключая любые повторяющиеся значения. Например, если <code>setA = ['a','b','c']</code> и <code>setB = ['a','b','d','e']</code> , то объединение множества A и setB: <code>setA.union(setB) = ['a', 'b', 'c', 'd', 'e']</code> .</p></section>

Perform a Union on Two Sets

<section id="description">
<p>В этом упражнении мы собираемся выполнить пересечение на 2 набора данных. Мы создадим метод на наших <code>Set</code> структуры данных называется <code>intersection</code> . Пересечение множеств представляет все значения, которые являются общими для двух или более наборов. Этот метод должен принимать другой <code>Set</code> в качестве аргумента и возвращать <code>intersection</code> двух наборов. Например, если <code>setA = ['a','b','c']</code> и <code>setB = ['a','b','d','e']</code> , то пересечение множества A и множества B: <code>setA.intersection(setB) = ['a', 'b']</code> .</p></section>

Perform an Intersection on Two Sets of Data

<section id="description">
<p>В этом упражнении мы собираемся выполнить разницу на 2 набора данных. Мы создадим метод на нашем <code>Set</code> структуры данных называется <code>difference</code> . Разница множеств должна сравнивать два набора и возвращать элементы, присутствующие в первом наборе, отсутствующие во втором. Этот метод должен принять другой <code>Set</code> в качестве аргумента и вернуть <code>difference</code> двух наборов. Например, если <code>setA = ['a','b','c']</code> и <code>setB = ['a','b','d','e']</code> , то разность setA и setB равна: <code>setA.difference(setB) = ['c']</code> .</p></section>

Perform a Difference on Two Sets of Data

<section id="description">
<p>В этом упражнении мы собираемся выполнить тест подмножества на 2 набора данных. Мы создадим метод на нашем <code>Set</code> структуры данных называется <code>subset</code> . Это будет сравнивать первый набор, второй и если первый набор полностью содержится внутри второго, тогда он вернет true. Например, если <code>setA = ['a','b']</code> и <code>setB = ['a','b','c','d']</code> , то подмножество setA и setB будет: <code>setA.subset(setB)</code> должно быть <code>true</code> .</p></section>

Perform a Subset Check on Two Sets of Data

<section id="description">
<p>Теперь, когда вы работали с ES5, вы собираетесь выполнить что-то подобное в ES6. Это будет значительно проще. ES6 содержит встроенную структуру данных. <code>Set</code> операций, которые вы написали вручную, теперь включены для вас. Давайте посмотрим: Чтобы создать новый пустой набор: <code>var set = new Set();</code> Вы можете создать набор со значением: <code>var set = new Set(1);</code> Вы можете создать набор с массивом: <code>var set = new Set([1, 2, 3]);</code> Когда вы создали набор, вы можете добавить нужные значения с помощью метода <code>add</code> : <blockquote> var set = new Set ([1, 2, 3]); <br> set.add ([4, 5, 6]); </blockquote> Напомним, что набор представляет собой структуру данных, которая не может содержать повторяющиеся значения: <blockquote> var set = new Set ([1, 2, 3, 1, 2, 3]); <br> // set содержит только [1, 2, 3] </blockquote></p>
</section>

Create and Add to Sets in ES6

<section id="description">
<p>Давайте практикуем элементы removeimg из набора ES6, используя метод <code>delete</code> . Сначала создайте набор ES6 <code>var set = new Set([1,2,3]);</code> Теперь удалите элемент из вашего набора с помощью метода <code>delete</code> . <blockquote> set.delete (1); <br> console.log ([... set]) // должен возвращать [2, 3] <blockquote></blockquote></blockquote></p>
</section>

Remove items from a set in ES6

<section id="description">
<p>Давайте посмотрим на методы .has и .size, доступные на объекте Set ES6. Сначала создайте набор ES6 <code>var set = new Set([1,2,3]);</code> Метод .has проверяет, содержится ли это значение в наборе. <code>var hasTwo = set.has(2);</code> Метод .size возвращает целое число, представляющее размер Set <code>var howBig = set.size;</code></p>
</section>

Use .has and .size on an ES6 Set

<section id="description">
<p>Вы помните оператор распространения ES6 <code>...</code> ? <code>...</code> может принимать истребимые объекты в ES6 и превращать их в массивы. Давайте создадим Set и проверим функцию спреда. <blockquote> var set = new Set ([1,2,3]); <br> var setToArr = [... set] <br> console.log (setToArr) // возвращает [1, 2, 3] </blockquote></p>
</section>

Use Spread and Notes for ES5 Set() Integration

<section id="description">
<p>В этом вызове вы создадите очередь приоритетов. Приоритетная очередь - это особый тип очереди, в которой элементы могут иметь дополнительную информацию, которая определяет их приоритет. Это может быть просто представлено целым числом. Приоритет элемента переопределяет порядок размещения при определении элементов последовательности. Если элемент с более высоким приоритетом помещается в очередь после элементов с более низким приоритетом, элемент с более высоким приоритетом будет удален до всех остальных. Например, предположим, что у нас есть очередь приоритетов с тремя элементами: <code>[['kitten', 2], ['dog', 2], ['rabbit', 2]]</code> Здесь второе значение (целое число) представляет приоритет элемента , Если мы ставим в очередь <code>['human', 1]</code> с приоритетом <code>1</code> (при условии, что более низкие приоритеты заданы приоритетом), тогда это будет первый элемент, который будет удален. Коллекция понравится: <code>[['human', 1], ['kitten', 2], ['dog', 2], ['rabbit', 2]]</code> . Мы начали писать <code>PriorityQueue</code> в редакторе кода. Вам нужно будет добавить метод <code>enqueue</code> для добавления элементов с приоритетом, метод <code>dequeue</code> для удаления элементов, метод <code>size</code> для возврата количества элементов в очереди, <code>front</code> метод для возврата элемента в передней части очереди и наконец, метод <code>isEmpty</code> , который вернет <code>true</code> если очередь пуста или <code>false</code> если это не так. <code>enqueue</code> должна принимать элементы с форматом, указанным выше ( <code>['human', 1]</code> ), где <code>1</code> представляет приоритет. <code>dequeue</code> должен возвращать только текущий элемент, а не его приоритет.</p></section>

Create a Priority Queue Class

<section id="description">
<p>В этом вызове вы создадите круговую очередность. Круговая очередь - это в основном очередь, которая записывает в конец коллекции, а затем начинает записывать себя в начале коллекции. Это тип структуры данных имеет некоторые полезные приложения в определенных ситуациях. Например, круговая очередь может использоваться для потоковой передачи. Как только очередь заполнена, новые мультимедийные данные просто начинают перезаписывать старые данные. Хорошим способом проиллюстрировать эту концепцию является массив: <blockquote> [1, 2, 3, 4, 5] <br> ^ Читать @ 0 <br> ^ Написать @ 0 </blockquote> Здесь чтение и запись находятся в положении <code>0</code> . Теперь очередь получает 3 новые записи <code>a</code> , <code>b</code> и <code>c</code> . Теперь наша очередь выглядит так: <blockquote> [a, b, c, 4, 5] <br> ^ Читать @ 0 <br> ^ Написать @ 3 </blockquote> Как читает читатель, он может удалить значения или сохранить их: <blockquote> [null, null, null, 4, 5] <br> ^ Читать @ 3 <br> ^ Написать @ 3 </blockquote> Когда запись достигает конца массива, он возвращается к началу: <blockquote> [f, null, null, d, e] <br> ^ Читать @ 3 <br> ^ Пишите @ 1 </blockquote> Этот подход требует постоянного объема памяти, но позволяет обрабатывать файлы большего размера. Инструкции: В этой задаче мы реализуем круговую очередь. Круговая очередь должна обеспечивать <code>enqueue</code> и <code>dequeue</code> методы , которые позволяют считывать и записывать данные в очередь. Сам класс должен также принять целое число, которое вы можете использовать, чтобы указать размер очереди при ее создании. Мы написали стартовую версию этого класса для вас в редакторе кода. Когда вы ставите объекты в очередь, указатель записи должен продвигаться вперед и возвращаться к началу, как только он достигнет конца очереди. Аналогично, указатель чтения должен продвигаться вперед при удалении элементов. Указателю записи не следует пропускать указатель чтения (наш класс не позволит вам перезаписывать данные, которые вы еще не читали), и указатель чтения не должен продвигать прошлые данные, которые вы написали. Кроме того, метод <code>enqueue</code> должен возвращать элемент, который вы указали, если он успешно и в противном случае возвращает <code>null</code> . Аналогичным образом, когда вы удаляете элемент, он должен быть возвращен, и если вы не можете удалить из очереди, вы должны вернуть <code>null</code> .</p></section>

Create a Circular Queue

<section id="description">
<p>Графы могут быть представлены по-разному. Здесь мы описываем один способ, который называется <dfn>списком смежности</dfn> . Список смежности по существу представляет собой маркированный список, в котором левой стороной является узел, а правая сторона - список всех других узлов, к которым он подключен. Ниже приведен список смежности. <blockquote> Node1: Node2, Node3 <br> Node2: Node1 <br> Node3: Node1 </blockquote> Выше - неориентированный граф, потому что <code>Node1</code> подключен к <code>Node2</code> и <code>Node3</code> , и эта информация соответствует соединениям <code>Node2</code> и <code>Node3</code> . Список смежности для ориентированного графа будет означать, что каждая строка списка показывает направление. Если выше было указано, то <code>Node2: Node1</code> будет означать, что направленный край указывает от <code>Node2</code> на <code>Node1</code> . Мы можем представить неориентированный граф выше как список смежности, помещая его в объект JavaScript. <blockquote> var undirectedG = { <br> Node1: ["Node2", "Node3"], <br> Node2: ["Node1"], <br> Node3: ["Node1"] <br> }; </blockquote> Это также можно более просто представить в виде массива, где узлы имеют только цифры, а не строковые метки. <blockquote> var unirectedGArr = [ <br> [1, 2], # Node1 <br> [0], # Node2 <br> [0] # Node3 <br> ]; </blockquote></p>
</section>

Adjacency List

<section id="description">
<p>Другим способом представления графика является его размещение в <dfn>матрице смежности</dfn> . Матрица <dfn>смежности</dfn> представляет собой двумерный (2D) массив, где каждый вложенный массив имеет такое же количество элементов, что и внешний массив. Другими словами, это матрица или сетка чисел, где числа представляют собой ребра. Нули означают, что нет границ или отношений. <blockquote> 1 2 3 <br> ------ <br> 1 | 0 1 1 <br> 2 | 1 0 0 <br> 3 | 1 0 0 </blockquote> Выше - очень простой, неориентированный граф, где у вас есть три узла, где первый узел подключен ко второму и третьему узлам. <strong>Примечание</strong> . Числа в верхней и левой частях матрицы являются только метками для узлов. Ниже приведена реализация JavaScript того же самого. <blockquote> var adjMat = [ <br> [0, 1, 1], <br> [1, 0, 0], <br> [1, 0, 0] <br> ]; </blockquote> В отличие от списка смежности, каждая «строка» матрицы должна иметь такое же количество элементов, что и узлы в графике. Здесь у нас есть три-три матрицы, что означает, что мы имеем три узла в нашем графике. Ориентированный граф будет похож. Ниже приведен график, в котором первый узел имеет ребро, указывающее на второй узел, а затем второй узел имеет ребро, указывающее на третий узел. <blockquote> var adjMatDirected = [ <br> [0, 1, 0], <br> [0, 0, 1], <br> [0, 0, 0] <br> ]; </blockquote> Графики также могут иметь <dfn>веса</dfn> по краям. До сих пор у нас есть <dfn>невзвешенные</dfn> края, где только наличие и отсутствие ребра двоично ( <code>0</code> или <code>1</code> ). Вы можете иметь разные веса в зависимости от вашего приложения.</p></section>

Adjacency Matrix

<section id="description">
<p>Еще один способ представить график - положить его в <dfn>матрицу инцидентности.</dfn> Матрица <dfn>инцидентности</dfn> представляет собой двумерный (2D) массив. Вообще говоря, матрица инцидентов связывает два разных класса объектов между двумя его измерениями. Такая матрица подобна матрице смежности. Тем не менее, строки и столбцы означают что-то еще здесь. В графах мы имеем ребра и узлы. Это будут наши «два разных класса объектов». Эта матрица будет содержать строки, в которых узлы и столбцы будут ребрами. Это означает, что мы можем иметь нечетное количество строк и столбцов. Каждый столбец будет представлять собой уникальный ребро. Кроме того, каждое ребро соединяет два узла. Чтобы показать, что существует ребро между двумя узлами, вы поместите 1 в две строки определенного столбца. Ниже приведен граф из 3 узлов с одним ребром между узлом 1 и узлом 3. <blockquote> 1 <br> --- <br> 1 | 1 <br> 2 | 0 <br> 3 | 1 </blockquote> Ниже приведен пример <code>incidence matrix</code> с 4 ребрами и 4 узлами. Помните, что столбцы - это ребра, а строки - сами узлы. <blockquote> 1 2 3 4 <br> -------- <br> 1 | 0 1 1 1 <br> 2 | 1 1 0 0 <br> 3 | 1 0 0 1 <br> 4 | 0 0 1 0 </blockquote> Ниже приведена реализация JavaScript того же самого. <blockquote> var incMat = [ <br> [0, 1, 1, 1], <br> [1, 1, 0, 0], <br> [1, 0, 0, 1], <br> [0, 0, 1, 0] <br> ]; </blockquote> Чтобы создать ориентированный граф, используйте <code>-1</code> для края, оставляющего определенный узел, и <code>1</code> для края, входящего в узел. <blockquote> var incMatDirected = [ <br> [0, -1, 1, -1], <br> [-1, 1, 0, 0], <br> [1, 0, 0, 1], <br> [0, 0, -1, 0] <br> ]; </blockquote> Графики также могут иметь <dfn>веса</dfn> по краям. До сих пор у нас есть <dfn>невзвешенные</dfn> края, где только наличие и отсутствие ребра двоично ( <code>0</code> или <code>1</code> ). Вы можете иметь разные веса в зависимости от вашего приложения. Другой вес представлен как числа больше 1.</p></section>

Incidence Matrix

<section id="description">
<p>Эта серия проблем приведет к созданию структуры данных дерева. Деревья - важная и универсальная структура данных в информатике. Конечно, их имя исходит из того факта, что при визуализации они очень похожи на деревья, с которыми мы знакомы в естественном мире. Структура данных дерева начинается с одного узла, обычно называемого корнем, и отсюда разветвляется на дополнительные узлы, каждый из которых может иметь больше дочерних узлов и т. Д. И т. Д. Структура данных обычно визуализируется с корневым узлом вверху; вы можете думать об этом, как естественное дерево перевернулось вверх дном. Сначала давайте опишем некоторую общую терминологию, с которой мы столкнемся с деревьями. Корневой узел - это вершина дерева. Точки данных в дереве называются узлами. Узлы с ветвями, ведущими к другим узлам, называются родителями узла, к которому ведет ветвь (дочерний элемент). Другие более сложные семейные термины применяются, как и следовало ожидать. Поддерево относится ко всем потомкам конкретного узла, ветви могут упоминаться как ребра, а листовые узлы - узлы в конце дерева, у которых нет детей. Наконец, обратите внимание, что деревья являются по своей природе рекурсивными структурами данных. То есть, любые дочерние узлы являются родителями собственного поддерева и так далее. Рекурсивный характер деревьев важен для понимания при разработке алгоритмов для общих операций дерева. Для начала обсудим конкретный тип дерева - двоичное дерево. Фактически, мы фактически обсудим конкретное двоичное дерево, двоичное дерево поиска. Давайте опишем, что это значит. Хотя структура данных дерева может иметь любое количество ветвей в одном узле, двоичное дерево может иметь только две ветви для каждого узла. Кроме того, двоичное дерево поиска упорядочено относительно дочерних поддеревьев, так что значение каждого узла в левом поддереве меньше или равно значению родительского узла, а значение каждого узла в правом поддереве равно больше или равно значению родительского узла. Очень полезно визуализировать эти отношения, чтобы лучше понять это: <div style="width: 100%; display: flex; justify-content: center; align-items: center;"><img style="width: 100%; max-width: 350px;" src="https://user-images.githubusercontent.com/18563015/32136009-1e665d98-bbd6-11e7-9133-63184f9f9182.png"></div> Теперь это упорядоченное отношение очень легко увидеть. Обратите внимание, что каждое значение слева от корневого узла 8 меньше 8, а каждое значение справа больше 8. Также обратите внимание, что это отношение относится и к каждому из поддеревьев. Например, первый левый дочерний элемент является поддеревом. 3 является родительским узлом и имеет ровно два дочерних узла - по правилам, определяющим деревья двоичного поиска, мы знаем, даже не глядя, что левый ребенок этого узла (и любого его дочернего элемента) будет меньше 3, а правый child (и любой из его дочерних элементов) будет больше 3 (но также меньше корневого значения структуры) и т. д. Двоичные деревья поиска - очень распространенные и полезные структуры данных, поскольку они обеспечивают логарифмическое время в среднем случае для нескольких общих операций, таких как поиск, вставка и удаление. Инструкции: Мы начнем просто. Мы определили скелет структуры двоичного дерева поиска здесь в дополнение к функции для создания узлов для нашего дерева. Обратите внимание, что каждый узел может иметь левое и правое значение. Они будут назначены дочерние поддеревья, если они существуют. В нашем двоичном дереве поиска определите два метода: <code>findMin</code> и <code>findMax</code> . Эти методы должны возвращать минимальное и максимальное значение, хранящиеся в двоичном дереве поиска (не беспокойтесь о добавлении значений в дерево на данный момент, мы добавили некоторые в фоновом режиме). Если вы застряли, подумайте об инварианте, который должен быть истинным для двоичных деревьев поиска: каждое левое поддерево меньше или равно его родительскому элементу, и каждое правое поддерево больше или равно его родительскому. Давайте также скажем, что наше дерево может хранить только целочисленные значения. Если дерево пустое, любой метод должен возвращать значение <code>null</code> .</p></section>

Find the Minimum and Maximum Value in a Binary Search Tree

<section id="description">
<p>Теперь, когда у нас есть идея об основах, давайте напишем более сложный метод. В этой задаче мы создадим метод добавления новых значений в наше дерево двоичного поиска. Метод следует называть <code>add</code> и он должен принимать целочисленное значение для добавления в дерево. Позаботьтесь о сохранении инварианта двоичного дерева поиска: значение в каждом левом ребне должно быть меньше или равно родительскому значению, а значение в каждом правом дочернем случае должно быть больше или равно родительскому значению. Здесь давайте сделаем так, чтобы наше дерево не могло хранить повторяющиеся значения. Если мы попытаемся добавить значение, которое уже существует, метод должен вернуть значение <code>null</code> . В противном случае, если добавление будет успешным, <code>undefined</code> должен быть возвращен. Подсказка: деревья - это, естественно, рекурсивные структуры данных!</p></section>

Add a New Element to a Binary Search Tree

<section id="description">
<p>Теперь, когда у нас есть общее представление о том, какое бинарное дерево поиска давайте поговорим об этом чуть подробнее. Двоичные деревья поиска предоставляют логарифмическое время для общих операций поиска, вставки и удаления в среднем случае и линейного времени в худшем случае. Почему так? Каждая из этих основных операций требует от нас найти элемент в дереве (или в случае вставки, чтобы найти, куда он должен идти), и из-за древовидной структуры каждого родительского узла мы разветвляемся влево или вправо и фактически исключаем половину размера оставшегося дерева. Это делает поиск пропорциональным логарифму числа узлов в дереве, что создает логарифмическое время для этих операций в среднем случае. Хорошо, но как насчет худшего случая? Ну, подумайте о построении дерева из следующих значений, добавив их слева направо: <code>10</code> , <code>12</code> , <code>17</code> , <code>25</code> . Следуя нашим правилам для двоичного дерева поиска, мы добавим <code>12</code> справа от <code>10</code> , <code>17</code> справа от него и <code>25</code> справа от него. Теперь наше дерево напоминает связанный список и, пройдя его, чтобы найти <code>25</code> , потребовало бы, чтобы мы проходили все элементы линейным способом. Следовательно, линейное время в худшем случае. Проблема здесь в том, что дерево неуравновешено. Мы рассмотрим немного больше, что это означает в следующих задачах. Инструкции: В этой задаче мы создадим утилиту для нашего дерева. Напишите метод <code>isPresent</code> который принимает целочисленное значение в качестве входных данных и возвращает логическое значение для наличия или отсутствия этого значения в двоичном дереве поиска.</p></section>

Check if an Element is Present in a Binary Search Tree

<section id="description">
<p>В последнем вызове мы описали сценарий, в котором дерево может стать неуравновешенным. Чтобы понять концепцию баланса, давайте посмотрим на другое свойство дерева: height. Высота в дереве представляет собой расстояние от корневого узла до любого заданного листового узла. Различные пути в сильно разветвленной структуре дерева могут иметь разную высоту, но для данного дерева будет минимальная и максимальная высота. Если дерево сбалансировано, эти значения будут отличаться не более чем на один. Это означает, что в сбалансированном дереве все листовые узлы существуют на одном уровне, или если они не находятся на одном уровне, они не более одного уровня друг от друга. Свойство баланса важно для деревьев, потому что именно это определяет эффективность древовидных операций. Как мы объяснили в последнем задаче, мы сталкиваемся с худшей временной сложностью для сильно неуравновешенных деревьев. Самобалансирующиеся деревья обычно используются для учета этой проблемы в деревьях с динамическими наборами данных. К общим примерам относятся деревья AVL, красно-черные деревья и B-деревья. Эти деревья содержат дополнительную внутреннюю логику, которая перебалансирует дерево, когда вставки или удаления создают состояние дисбаланса. Примечание. Аналогичным свойством высоты является глубина, которая относится к тому, насколько далеко данный узел находится от корневого узла. Инструкции: Напишите два метода для нашего двоичного дерева: <code>findMinHeight</code> и <code>findMaxHeight</code> . Эти методы должны возвращать целочисленное значение для минимальной и максимальной высоты в заданном двоичном дереве, соответственно. Если узел пуст, назначим ему высоту <code>-1</code> (это базовый случай). Наконец, добавьте третий метод <code>isBalanced</code> который возвращает <code>true</code> или <code>false</code> зависимости от того, сбалансировано ли дерево или нет. Вы можете использовать первые два метода, которые вы только что написали, чтобы определить это.</p></section>

Find the Minimum and Maximum Height of a Binary Search Tree

<section id="description">
<p>Мы знаем, как искать двоичное дерево поиска для определенного значения. Но что, если мы просто хотим исследовать все дерево? Или что, если у нас нет упорядоченного дерева, и нам нужно просто искать значение? Здесь мы представим некоторые методы обхода дерева, которые можно использовать для изучения структур древовидных данных. Сначала - поиск по глубине. При поиске по глубине, заданное поддерево рассматривается как можно глубже, прежде чем поиск продолжит переход к другому поддереву. Это можно сделать тремя способами: In-order: Начать поиск на самом левом узле и завершить на самом правом узле. Предварительный порядок: исследуйте все корни перед листьями. Post-order: Исследуйте все листья перед корнями. Как вы можете догадаться, вы можете выбрать различные методы поиска в зависимости от того, какие данные хранят ваше дерево и что вы ищете. Для двоичного дерева поиска обход ордера возвращает узлы в отсортированном порядке. Инструкции: Здесь мы создадим эти три метода поиска в нашем двоичном дереве поиска. Поиск по глубине - это неотъемлемая рекурсивная операция, которая продолжает исследовать дальнейшие поддеревья, пока присутствуют дочерние узлы. Как только вы поймете эту базовую концепцию, вы можете просто изменить порядок, в котором вы исследуете узлы и поддеревья, чтобы произвести любой из трех поисков выше. Например, в post-order search мы хотели бы перечислить весь путь до листового узла, прежде чем мы начнем возвращать любой из самих узлов, тогда как в предварительном поиске мы хотели бы сначала вернуть узлы, а затем продолжить рекурсию вниз по дереву. Определение <code>inorder</code> , <code>preorder</code> , и <code>postorder</code> метода на нашем дереве. Каждый из этих методов должен возвращать массив элементов, которые представляют обход дерева. Обязательно верните целые значения в каждом узле массива, а не сами узлы. Наконец, возвращаем значение <code>null</code> если дерево пусто.</p></section>

Use Depth First Search in a Binary Search Tree

<section id="description">
<p>Здесь мы представим другой метод обхода дерева: поиск по ширине. В отличие от методов поиска по глубине из последней задачи, поиск по ширине исследует все узлы на заданном уровне внутри дерева, а затем переходит на следующий уровень. Как правило, очереди используются в качестве вспомогательных структур данных при разработке алгоритмов поиска по ширине. В этом методе мы начинаем с добавления корневого узла в очередь. Затем мы начинаем цикл, в котором мы деактивируем первый элемент в очереди, добавим его в новый массив и затем проверим оба его дочерних поддерева. Если его дочерние элементы не равны нулю, все они помещаются в очередь. Этот процесс продолжается до тех пор, пока очередь не будет пустой. Инструкции. Давайте создадим метод поиска ширины в нашем дереве, называемый <code>levelOrder</code> . Этот метод должен возвращать массив, содержащий значения всех узлов дерева, исследованных в широком смысле. Обязательно верните значения в массиве, а не сами узлы. Уровень должен пересекаться слева направо. Далее, давайте напишем аналогичный метод <code>reverseLevelOrder</code> который выполняет тот же поиск, но в обратном направлении (справа налево) на каждом уровне.</p></section>

Use Breadth First Search in a Binary Search Tree

<section id="description">
<p>Это первая из трех задач, когда мы будем выполнять более сложную операцию в двоичных деревьях поиска: удаление. Удаление затруднено, поскольку удаление узлов ломает ссылки в дереве. Эти ссылки должны быть тщательно восстановлены для обеспечения сохранения структуры двоичного дерева. Для некоторых исключений это означает, что дерево должно быть перестроено. В общем случае вы столкнетесь с одним из трех случаев, когда пытаетесь удалить узел: Leaf Node: цель для удаления имеет ноль детей. Один ребенок: у цели для удаления только один ребенок. Двое детей: цель для удаления имеет два дочерних узла. Удаление листового узла легко, мы просто удалим его. Удаление узла одним ребенком также относительно просто, мы просто удалим его и связаем его родительский с дочерним узлом удаляемого узла. Однако удалить узел с двумя детьми сложнее, поскольку это создает два дочерних узла, которые необходимо переподключить к родительскому дереву. Мы посмотрим, как справиться с этим делом в третьем вызове. Кроме того, вы должны помнить о некоторых случаях при обработке удаления. Что делать, если дерево пустое? Что делать, если удаляемый узел является корневым узлом? Что делать, если в дереве есть только два элемента? Теперь давайте рассмотрим первый случай, когда мы удаляем листовой узел. Инструкции: Создайте метод на нашем двоичном дереве, который называется <code>remove</code> . Здесь мы построим логику для операции удаления. Во-первых, вам нужно создать функцию в удалении, которая находит узел, который мы пытаемся удалить в текущем дереве. Если узел отсутствует в дереве, <code>remove</code> должен вернуть значение <code>null</code> . Теперь, если целевой узел является листовым узлом без детей, то родительская ссылка на него должна быть установлена ​​в <code>null</code> . Это эффективно удаляет узел из дерева. Для этого вам нужно будет отслеживать родительский узел узла, который мы также пытаемся удалить. Также будет полезно создать способ отслеживания числа дочерних узлов целевого узла, так как это определит, к какому случаю относится наше удаление. Мы рассмотрим второй и третий случаи в следующих задачах. Удачи!</p></section>

Delete a Leaf Node in a Binary Search Tree

<section id="description">
<p>Now that we can delete leaf nodes let's move on to the second case: deleting a node with one child. For this case, say we have a tree with the following nodes 1 — 2 — 3 where 1 is the root. To delete 2, we simply need to make the right reference in 1 point to 3. More generally to delete a node with only one child, we make that node's parent reference the next node in the tree.</p></section>

Delete a Node with One Child in a Binary Search Tree

<section id="description">
<p>Удаление узлов, имеющих двух детей, является самым сложным для реализации. Удаление такого узла приводит к двум поддеревьям, которые больше не связаны с исходной древовидной структурой. Как мы можем их восстановить? Один из методов заключается в том, чтобы найти наименьшее значение в правом поддереве целевого узла и заменить целевой узел на это значение. Выбор замены таким образом гарантирует, что он больше, чем каждый узел в левом поддереве, он становится новым родителем, но также меньше, чем каждый узел в правом поддереве, он становится новым родителем. После этой замены узел замены должен быть удален из правого поддерева. Даже эта операция сложна, потому что замена может быть листом, или она сама может быть родителем правильного поддерева. Если это лист, мы должны удалить ссылку на родителя. В противном случае это должен быть правильный ребенок цели. В этом случае мы должны заменить целевое значение значением замены и сделать целевую ссылку правильным ребенком замены. Инструкции: Закончим наш метод <code>remove</code> , обработав третий случай. Мы снова предоставили код для первых двух случаев. Добавьте код для обработки целевых узлов двумя детьми. Любые случаи краев, о которых нужно знать? Что, если дерево имеет только три узла? По завершении этого будет завершена операция удаления двоичных деревьев поиска. Хорошая работа, это довольно сложная проблема!</p></section>

Delete a Node with Two Children in a Binary Search Tree

<section id="description">
<p>Здесь мы создадим функцию инвертирования двоичного дерева. Учитывая двоичное дерево, мы хотим создать новое дерево, эквивалентное зеркальному изображению этого дерева. Выполнение обхода порядка на инвертированном дереве будет исследовать узлы в обратном порядке по сравнению с обходным порядком исходного дерева. Напишите метод для этого, который называется <code>invert</code> на нашем двоичном дереве. Вызов этого метода должен инвертировать текущую древовидную структуру. В идеале мы хотели бы сделать это на месте в линейном времени. То есть мы только посещаем каждый узел один раз, и мы изменяем существующую древовидную структуру, когда мы идем, без использования дополнительной памяти. Удачи!</p></section>

Invert a Binary Tree

<section id="description">
<p>Здесь мы перейдем от двоичных деревьев поиска и рассмотрим другой тип древовидной структуры, называемый trie. Trie - это упорядоченное дерево поиска, обычно используемое для хранения строк или более общих ассоциативных массивов или динамических наборов данных, в которых ключи являются строками. Они очень хороши в хранении наборов данных, когда многие ключи имеют перекрывающиеся префиксы, например, все слова в словаре. В отличие от двоичного дерева, узлы не связаны с фактическими значениями. Вместо этого путь к узлу представляет собой конкретный ключ. Например, если бы мы хотели сохранить строковый код в trie, у нас было бы четыре узла, по одному для каждой буквы: c - o - d - e. После этого пути через все эти узлы затем создадут код как строку - этот путь является ключом, который мы сохранили. Затем, если бы мы хотели добавить строковое кодирование, он разделил бы первые три узла кода, прежде чем разветвиться после d. Таким образом, большие наборы данных могут храниться очень компактно. Кроме того, поиск может быть очень быстрым, поскольку он фактически ограничен длиной строки, которую вы храните. Кроме того, в отличие от двоичных деревьев узел может хранить любое количество дочерних узлов. Как вы могли догадаться из приведенного выше примера, некоторые метаданные обычно хранятся в узлах, которые содержат конец ключа, так что на последующих обходах этот ключ все еще может быть восстановлен. Например, если мы добавили коды в наш пример выше, нам понадобится некоторый способ узнать, что e в коде представляет собой конец ключа, который был ранее введен. В противном случае эта информация будет эффективно потеряна при добавлении кодов. Инструкции: создадим три для хранения слов. Он будет принимать слова через метод добавления и хранить их в структуре данных trie. Это также позволит нам запросить, является ли данная строка словом с методом isWord и извлекает все слова, введенные в trie с помощью метода печати. isWord должен возвращать логическое значение, и print должен возвращать массив всех этих слов в виде строковых значений. Чтобы мы убедились, что эта структура данных реализована правильно, мы предоставили структуру узла для каждого узла в дереве. Каждый узел будет объектом с свойством keys, являющимся объектом JavaScript Map. Это будет содержать отдельные буквы, которые являются действительными ключами каждого узла. Мы также создали свойство конца на узлах, которое может быть установлено в true, если узел представляет собой завершение слова.</p></section>

Create a Trie Search Tree

<section id="description">
<p>Здесь мы будем применять сортировку выбором. Сортировка выбором работает, выбирая минимальное значение в списке и меняя его с первым значением в списке. Затем он начинается со второй позиции, выбирает наименьшее значение в оставшемся списке и свопирует его со вторым элементом. Он продолжает итерирование по списку и свопинг элементов до тех пор, пока он не достигнет конца списка. Теперь список отсортирован. Сортировка выбора имеет квадратичную временную сложность во всех случаях. <strong>Инструкции</strong> : Напишите функцию <code>selectionSort</code> которая принимает массив целых чисел в качестве входных данных и возвращает массив этих целых чисел в отсортированном порядке от наименьшего к наибольшему. <strong>Заметка:</strong> <br> Мы вызываем эту функцию из-за кулис; тестовый массив, который мы используем, закомментирован в редакторе. Попробуйте logging <code>array</code> чтобы увидеть ваш алгоритм сортировки в действии!</p></section>

Implement Selection Sort

<section id="description">
<p>Следующий метод сортировки, на который мы будем смотреть - это сортировка вставками. Этот метод работает, создавая сортированный массив в начале списка. Он создает сортированный массив с первым элементом. Затем он проверяет следующий элемент и свопирует его обратно в отсортированный массив до тех пор, пока он не будет отсортирован. Он продолжает итерирование по списку и сворачивание новых элементов назад в отсортированную часть до тех пор, пока она не достигнет конца. Этот алгоритм имеет квадратичную временную сложность в среднем и худшем случае. <strong>Инструкции:</strong> Напишите функцию <code>insertionSort</code> которая принимает массив целых чисел в качестве входных данных и возвращает массив этих целых чисел в отсортированном порядке от наименьшего к наибольшему. <strong>Заметка:</strong> <br> Мы вызываем эту функцию из-за кулис; тестовый массив, который мы используем, закомментирован в редакторе. Попробуйте logging <code>array</code> чтобы увидеть ваш алгоритм сортировки в действии!</p></section>

Implement Insertion Sort

<section id="description">
<p>Все связанные списки, которые мы создали до сих пор, представляют собой отдельные списки. Здесь мы создадим <dfn>двусвязный список</dfn> . Как следует из названия, узлы в двусвязном списке имеют ссылки на следующий и предыдущий узел в списке. Это позволяет нам перемещаться по списку в обоих направлениях, но для этого требуется больше памяти, потому что каждый узел должен содержать дополнительную ссылку на предыдущий узел в списке.</p></section>

Create a Doubly Linked List

<section id="description">
<p>Давайте создадим еще один метод для нашего дважды связанного списка, который называется reverse, который меняет список на месте. Как только метод выполняется, голова должна указывать на предыдущий хвост, а хвост должен указывать на предыдущую голову. Теперь, если мы пересекаем список от головы до хвоста, мы должны встретить узлы в обратном порядке по сравнению с исходным списком. Попытка изменить пустой список должна вернуть значение null.</p></section>

Reverse a Doubly Linked List

<section id="description">
<p>Здесь мы перейдем к промежуточному алгоритму сортировки: быстрая сортировка. Быстрая сортировка - это эффективный, рекурсивный подход к сортировке массива. В этом методе в исходном массиве выбирается значение поворота. Массив затем разбивается на два подмассивов значений меньше и больше, чем значение поворота. Затем мы комбинируем результат рекурсивного вызова алгоритма быстрой сортировки на обоих подмассивах. Это продолжается до тех пор, пока не будет достигнут базовый случай для пустого или одного элемента массива, который мы вернем. Откат рекурсивных вызовов возвращает нам отсортированный массив. Быстрый сортировка - очень эффективный метод сортировки, обеспечивающий производительность <i>O (nlog (n))</i> в среднем. Это также относительно легко реализовать. Эти атрибуты делают его популярным и полезным методом сортировки. <strong>Инструкции:</strong> Напишите функцию <code>quickSort</code> которая принимает массив целых чисел в качестве входных данных и возвращает массив этих целых чисел в отсортированном порядке от наименьшего к наибольшему. В то время как выбор значения поворота важен, любой стержень будет делать для наших целей здесь. Для простоты можно использовать первый или последний элемент. <strong>Заметка:</strong> <br> Мы вызываем эту функцию из-за кулис; тестовый массив, который мы используем, закомментирован в редакторе. Попробуйте logging <code>array</code> чтобы увидеть ваш алгоритм сортировки в действии!</p></section>

Implement Quick Sort

<section id="description">
<p>Теперь мы перейдем к другой структуре данных дерева, двоичной куче. Бинарная куча - частично упорядоченное двоичное дерево, которое удовлетворяет свойству кучи. Свойство heap указывает связь между родительским и дочерним узлами. У вас может быть максимальная куча, в которой все родительские узлы больше или равны их дочерним узлам или минимальная куча, в которой верно обратное. Двоичные кучи также являются полными бинарными деревьями. Это означает, что все уровни дерева полностью заполнены, и если последний уровень частично заполнен, он заполняется слева направо. Хотя двоичные кучи могут быть реализованы как древовидные структуры с узлами, которые содержат левую и правую ссылки, частичный порядок в соответствии с свойством кучи позволяет нам представлять кучу с массивом. Отношения родитель-дети - это то, что нас интересует, и с простой арифметикой мы можем вычислить дочерние элементы любого родителя и родителя любого дочернего узла. Например, рассмотрим это представление массива двоичной мини-кучи: <code>[ 6, 22, 30, 37, 63, 48, 42, 76 ]</code> Корневой узел - это первый элемент, 6. Его дети - 22 и 30. Если мы посмотрим при взаимосвязи между индексами массива этих значений для индекса i дети равны 2 * i + 1 и 2 * i + 2. Аналогично, элемент с индексом 0 является родителем этих двух детей по индексам 1 и 2. Подробнее Как правило, мы можем найти родительский узел узла в любом индексе со следующим: (i - 1) / 2. Эти шаблоны будут выполняться, поскольку бинарное дерево растет до любого размера. Наконец, мы можем сделать небольшую корректировку, чтобы сделать эту арифметику еще проще, пропустив первый элемент в массиве. Для этого создается следующее отношение для любого элемента в указанном индексе i: Пример Array: <code>[ null, 6, 22, 30, 37, 63, 48, 42, 76 ]</code> Левый дочерний элемент: i * 2 Правильный дочерний элемент : i * 2 + 1 Родитель элемента: i / 2 После того, как вы обернете свою голову вокруг математики, использование представления массива очень полезно, потому что расположение узлов можно быстро определить с помощью этой арифметики, а использование памяти уменьшилось, потому что вам не нужно для поддержки ссылок на дочерние узлы. Инструкции: Здесь мы создадим максимальную кучу. Начните с создания метода insert, который добавляет элементы в нашу кучу. При вставке важно всегда сохранять свойство кучи. Для максимальной кучи это означает, что корневой элемент всегда должен иметь наибольшее значение в дереве, а все родительские узлы должны быть больше, чем их дети. Для реализации массива кучи это правило выполняется в три этапа: добавьте новый элемент в конец массива. Если элемент больше, чем его родители, переключите их. Продолжайте переключение до тех пор, пока новый элемент не станет меньше его родителя или вы не достигнете корня дерева. Наконец, добавьте метод печати, который возвращает массив всех элементов, которые были добавлены в кучу.</p></section>

Insert an Element into a Max Heap

<section id="description">
<p>Теперь, когда мы можем добавить элементы в нашу кучу, посмотрим, как мы можем удалить элементы. Для снятия и вставки элементов требуется аналогичная логика. В максимальной куче вы обычно хотите удалить наибольшую ценность, поэтому это требует просто извлечь ее из корня нашего дерева. Это разрушит свойство кучи нашего дерева, поэтому мы должны каким-то образом восстановить его. Как правило, для максимальной кучи это делается следующим образом: переместите последний элемент в куче в корневую позицию. Если любой корень корня больше, чем он, замените корень с дочерним значением большего значения. Продолжайте замену, пока родитель больше, чем оба ребенка, или вы достигнете последнего уровня в дереве. Инструкции: добавьте метод в нашу максимальную кучу, называемую remove. Этот метод должен вернуть наибольшее значение, которое было добавлено в нашу максимальную кучу и удалить его из кучи. Он также должен изменить порядок кучи, чтобы сохранить свойство кучи. После удаления элемента следующий главный элемент, оставшийся в куче, должен стать корнем. Здесь также добавьте свой метод вставки.</p></section>

Remove an Element from a Max Heap

<section id="description">
<p>Теперь, когда мы можем добавлять и удалять элементы, давайте посмотрим, как можно использовать некоторые кучи приложений. Кучи обычно используются для реализации очередей приоритетов, поскольку они всегда хранят элемент наибольшего или наименьшего значения в первой позиции. Кроме того, они используются для реализации алгоритма сортировки, называемого сортировкой кучи. Посмотрим, как это сделать. Сортировка кучи использует минимальную кучу, обратную к максимальной куче. Минимальная куча всегда сохраняет элемент наименьшего значения в корневой позиции. Heap sort работает, беря несортированный массив, добавляя каждый элемент в массив в кучу минут, а затем извлекает каждый элемент из кучи min в новый массив. Структура минимальной кучи гарантирует, что новый массив будет содержать исходные элементы по крайней мере до наибольшего порядка. Это один из наиболее эффективных алгоритмов сортировки со средней и наихудшей производительностью O (nlog (n)). Инструкции: Давайте реализуем кучу сортировки с минимальной кучей. Не стесняйтесь адаптировать свой максимальный код кучи. Создайте объект MinHeap с помощью методов вставки, удаления и сортировки. Метод sort должен возвращать массив из всех элементов в куче минимальной сортировки от минимального до самого большого.</p></section>

Implement Heap Sort with a Min Heap

<section id="description">
<p>The new version of JavaScript provides us with a built-in Map object which provides much of the functionality we wrote by hand in the last challenge. This Map object, although similar to regular JavaScript objects, provides some useful functionality that normal objects lack. For example, an ES6 Map tracks the insertion order of items that are added to it. Here is a more complete overview of its methods:</p><p><code>.has(key)</code> returns true or false based on the presence of a key</p><p><code>.get(key)</code> returns the value associated with a key</p><p><code>.set(key, value)</code> sets a new key, value pair</p><p><code>.delete(key)</code> removes a key, value pair</p><p><code>.clear()</code> removes all key, value pairs</p><p><code>.entries()</code> returns an array of all the keys in insertion order</p><p><code>.values()</code> returns an array of all the values in insertion order</p></section>

Create an ES6 JavaScript Map

<section id="description">
<p>В этой задаче мы узнаем о хэш-таблицах. Хэш-таблица используется для реализации ассоциативных массивов или сопоставлений пар ключ-значение, таких как объекты и Карты, которые мы только что изучали. Например, объект JavaScript может быть реализован как хэш-таблица (его фактическая реализация будет зависеть от среды, в которой он работает). Способ работы хеш-таблицы состоит в том, что он принимает ключевой ввод и делит этот ключ на некоторое числовое значение. Это числовое значение затем используется как фактический ключ, связанное значение сохраняется. Затем, если вы снова попытаетесь получить доступ к тому же ключу, хеширующая функция обработает ключ, вернет тот же числовой результат, который затем будет использоваться для поиска связанного значения. Это обеспечивает очень эффективное время поиска O (n) в среднем. Хэш-таблицы могут быть реализованы как массивы с хеш-функциями, производящими индексы массивов в заданном диапазоне. В этом методе выбор размера массива важен, как и функция хэширования. Например, что, если функция хэширования дает одно и то же значение для двух разных ключей? Это называется столкновением. Один из способов обработки коллизий - просто сохранить обе пары ключ-значение в этом индексе. Затем, после поиска либо, вам придется перебирать ведро предметов, чтобы найти ключ, который вы ищете. Хорошая функция хэширования минимизирует столкновения для поддержания эффективного времени поиска. Здесь мы не будем беспокоиться о деталях хэширования или реализации хеш-таблицы, мы просто попытаемся получить общее представление о том, как они работают. Инструкции: Давайте создадим базовую функциональность хеш-таблицы. Мы создали наивную функцию хэширования для вас. Вы можете передать строковое значение в хэш функции, и оно вернет хешированное значение, которое вы можете использовать в качестве ключа для хранения. Храните элементы на основе этого хешированного значения в объекте this.collection. Создайте эти три метода: добавьте, удалите и найдите. Первый должен принять пару значений ключа для добавления в хеш-таблицу. Второй должен удалить пару ключ-значение при передаче ключа. Третий должен принять ключ и вернуть связанное значение или null, если ключ отсутствует. Обязательно напишите свой код для учета конфликтов!</p></section>

Create a Hash Table

<section id="description">
<p>Другим промежуточным алгоритмом сортировки, который очень распространен, является сортировка слияния. Подобно быстрой сортировке, сортировка слиянием также использует метод рекурсивного анализа для разделения массива. Сортировка использует тот факт, что легче сортировать два массива меньшего размера, нежели один большего. <br>В качестве входных данных начнем с неотсортированного массива. Как мы можем перейти к двум отсортированным массивам? Мы можем рекурсивно разделить исходный ввод на два, пока не достигнем базового случая массива с одним элементом. Массив из одного элемента естественно сортируется, поэтому мы можем начать комбинировать. Эта комбинация будет раскручивать рекурсивные вызовы, разделяющие исходный массив, в конечном итоге создавая окончательный отсортированный массив всех элементов. </p>
<p>  Затем выполняются шаги сортировки слияния: </p>
<p>  <br><strong>1)</strong> Рекурсивно разделить входной массив пополам, пока не будет создан массив только с одним элементом.       <br><strong>2)</strong> Объединтить каждый отсортированный подмассив вместе, чтобы получить окончательный отсортированный массив. </p>
<p>  Сортировка Merge - это эффективный метод сортировки со алгоритмически-оптимальной сложностью <i>O (nlog (n))</i> . Этот алгоритм популярен, потому что он прост в реализации. <br>Это будет последний эффективный алгоритм сортировки, который мы рассмотрим здесь. Однако позже в разделе о структурах древовидных данных мы опишем сортировку кучи (HeapSort), еще один эффективный метод сортировки, который требует реализацию бинарной кучи. </p>
<p>  <strong>Инструкции:</strong> Напишите функцию <code>mergeSort</code> которая принимает массив целых чисел в качестве входных данных и возвращает массив этих целых чисел в отсортированном порядке от наименьшего к наибольшему. Хороший способ реализовать это - написать одну функцию, например <code>merge</code> , которая отвечает за объединение двух отсортированных массивов и другую функцию, например, <code>mergeSort</code> , которая отвечает за слияние. Удачи! </p>
<p>  <strong>Заметка:</strong> <br> Мы вызываем эту функцию из-за кулис; тестовый массив, который мы используем, закомментирован в редакторе. Попробуйте logging <code>array</code> чтобы увидеть ваш алгоритм сортировки в действии!</p></section>

Implement Merge Sort

<section id="description">
<p>До сих пор мы изучили разные способы создания представлений графиков. Что теперь? Один естественный вопрос - какие расстояния между любыми двумя узлами графика? Введите <dfn>алгоритмы обхода графа</dfn> . <dfn>Алгоритмы</dfn> траверса - это алгоритмы для перемещения или посещения узлов в графе. Одним типом алгоритма обхода является алгоритм поиска ширины. Этот алгоритм начинается с одного узла, сначала посещает всех его соседей, которые находятся на одном крае, а затем переходит к каждому из своих соседей. Визуально это то, что делает алгоритм. <img class="img-responsive" src="https://camo.githubusercontent.com/2f57e6239884a1a03402912f13c49555dec76d06/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f342f34362f416e696d617465645f4246532e676966"> Чтобы реализовать этот алгоритм, вам нужно будет ввести структуру графика и узел, с которого вы хотите начать. Во-первых, вы хотите знать расстояния от стартового узла. Это вы хотите сначала начать все свои расстояния на некоторое количество, например <code>Infinity</code> . Это дает ссылку на случай, когда узел может быть недоступен из вашего стартового узла. Затем вы захотите перейти от стартового узла к своим соседям. Эти соседи находятся на одном крае, и в этот момент вы должны добавить одну единицу расстояния до расстояний, которые вы отслеживаете. Наконец, важной структурой данных, которая поможет реализовать алгоритм поиска по ширине, является очередь. Это массив, в котором вы можете добавлять элементы в один конец и удалять элементы с другого конца. Это также известно как структура данных <dfn>FIFO</dfn> или <dfn>First-In-First-Out</dfn> .</p></section>

Breadth-First Search

<section id="description">
<p>Подобно <dfn>поиску в ширину</dfn> , здесь мы узнаем о другом алгоритме обхода графа, называемом методом поиска в <dfn>глубину</dfn> . В то время как поиск по ширине ищет инкрементные длины кромок от исходного узла, <dfn>поиск по глубине сначала</dfn> идет по пути ребер, насколько это возможно. Как только он достигнет одного конца пути, поиск вернется к последнему узлу с не посещенным краем пути и продолжит поиск. Ниже приведена визуализация того, что делает алгоритм, когда верхний узел является отправной точкой поиска. <img class="img-responsive" src="https://camo.githubusercontent.com/aaad9e39961daf34d967c616edeb50abf3bf1235/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f372f37662f44657074682d46697273742d5365617263682e676966"> Простым выходом этого алгоритма является список узлов, которые достижимы с данного узла. Поэтому при реализации этого алгоритма вам нужно будет отслеживать узлы, которые вы посещаете.</p></section>

Depth-First Search

<section id="description">
<p>Если мы перечислим все натуральные числа меньше 10, кратные 3 или 5, мы получим 3, 5, 6 и 9. Сумма этих кратных равна 23. Найдите сумму всех кратных 3 или 5 меньше значения параметра <code>number</code> .</p></section>

Problem 1: Multiples of 3 and 5

<section id="description">
<p>Каждый новый член в последовательности Фибоначчи генерируется путем сложения предыдущих двух членов. Начиная с 1 и 2, первые 10 членов будут: <div style="text-align: center;"> 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... </div> Рассматривая члены в последовательности Фибоначчи до <code>n</code> -го включительно, найдите сумму четных чисел последовательности.</p></section>

Problem 2: Even Fibonacci Numbers

<section id="description">
<p>Простыми множителями (факторами) числа 13195 являются 5, 7, 13 и 29. Каков самый большой простой множитель для данного <code>number</code> ?</p></section>

Problem 3: Largest prime factor

<section id="description">
<p>Палиндромный номер читается одинаково в обоих направлениях. Самый большой палиндром, полученный из продукта двух двузначных чисел, составляет 9009 = 91 × 99. Найдите самый большой палиндром, изготовленный из продукта двух <code>n</code> разрядных чисел.</p></section>

Problem 4: Largest palindrome product

<section id="description">
<p>2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.</p>
<p>What is the smallest positive number that is evenly divisible by all of the numbers from 1 to <code>n</code>?</p></section>

Problem 5: Smallest multiple

<section id="description">
<p>Сумма квадратов первых десяти натуральных чисел равна, <div style="text-align: center;"> 1 <sup>2</sup> + 2 <sup>2</sup> + ... + 10 <sup>2</sup> = 385 </div> Квадрат суммы первых десяти натуральных чисел есть, <div style="text-align: center;"> (1 + 2 + ... + 10) <sup>2</sup> = 55 <sup>2</sup> = 3025 </div> Следовательно, разница между суммой квадратов первых десяти натуральных чисел и квадратом суммы равна 3025 - 385 = 2640. Найдите разницу между суммой квадратов первых <code>n</code> натуральных чисел и квадратом суммы.</p></section>

Problem 6: Sum square difference

<section id="description">
<p>Перечислив первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы увидим, что 6-е число равно 13. Что такое <code>n</code> е простое число?</p></section>

Problem 7: 10001st prime

<section id="description">
<p>Четыре смежных цифры в 1000-значном числе, которые имеют наибольший продукт, составляют 9 × 9 × 8 × 9 = 5832. <div style="text-align: center;"> 73167176531330624919225119674426574742355349194934 </div><div style="text-align: center;"> 96983520312774506326239578318016984801869478851843 </div><div style="text-align: center;"> 85861560789112949495459501737958331952853208805511 </div><div style="text-align: center;"> 12540698747158523863050715693290963295227443043557 </div><div style="text-align: center;"> 66896648950445244523161731856403098711121722383113 </div><div style="text-align: center;"> 62229893423380308135336276614282806444486645238749 </div><div style="text-align: center;"> 30358907296290491560440772390713810515859307960866 </div><div style="text-align: center;"> 70172427121883998797908792274921901699720888093776 </div><div style="text-align: center;"> 65727333001053367881220235421809751254540594752243 </div><div style="text-align: center;"> 52584907711670556013604839586446706324415722155397 </div><div style="text-align: center;"> 53697817977846174064955149290862569321978468622482 </div><div style="text-align: center;"> 83972241375657056057490261407972968652414535100474 </div><div style="text-align: center;"> 82166370484403199890008895243450658541227588666881 </div><div style="text-align: center;"> 16427171479924442928230863465674813919123162824586 </div><div style="text-align: center;"> 17866458359124566529476545682848912883142607690042 </div><div style="text-align: center;"> 24219022671055626321111109370544217506941658960408 </div><div style="text-align: center;"> 07198403850962455444362981230987879927244284909188 </div><div style="text-align: center;"> 84580156166097919133875499200524063689912560717606 </div><div style="text-align: center;"> 05886116467109405077541002256983155200055935729725 </div><div style="text-align: center;"> 71636269561882670428252483600823257530420752963450 </div> Найдите <code>n</code> смежных цифр в 1000-значном номере, который имеет наибольший продукт. Какова ценность этого продукта?</p></section>

Problem 8: Largest product in a series

<section id="description">
<p>Пифагорейский триплет представляет собой набор из трех натуральных чисел <var>a</var> &#x3C; <var>b</var> &#x3C; <var>c</var> , для которых, <div style="text-align: center;"> <var>a</var> <sup>2</sup> + <var>b</var> <sup>2</sup> = <var>c</var> <sup>2</sup> </div> Например, 3 <sup>2</sup> + 4 <sup>2</sup> = 9 + 16 = 25 = 5 <sup>2</sup> . Существует ровно один пифагорейский триплет, для которого <var>a</var> + <var>b</var> + <var>c</var> = 1000. Найдите произведение <var>abc</var> такое, что <var>a</var> + <var>b</var> + <var>c</var> = <code>n</code> .</p></section>

Problem 9: Special Pythagorean triplet

<section id="description">
<p>Сумма простых чисел ниже 10 равна 2 + 3 + 5 + 7 = 17. Найдите сумму всех простых чисел ниже n.</p></section>

Problem 10: Summation of primes

<section id="description">
<p>В сетке 20 × 20 ниже четыре цифры по диагональной линии отмечены красным цветом. <div style="text-align: center;"> 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 </div><div style="text-align: center;"> 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 </div><div style="text-align: center;"> 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 </div><div style="text-align: center;"> 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 </div><div style="text-align: center;"> 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 </div><div style="text-align: center;"> 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 </div><div style="text-align: center;"> 32 98 81 28 64 23 67 10 <span style="color: red"><b>26</b></span> 38 40 67 59 54 70 66 18 38 64 70 </div><div style="text-align: center;"> 67 26 20 68 02 62 12 20 95 <span style="color: red"><b>63</b></span> 94 39 63 08 40 91 66 49 94 21 </div><div style="text-align: center;"> 24 55 58 05 66 73 99 26 97 17 <span style="color: red"><b>78</b></span> 78 96 83 14 88 34 89 63 72 </div><div style="text-align: center;"> 21 36 23 09 75 00 76 44 20 45 35 <span style="color: red"><b>14</b></span> 00 61 33 97 34 31 33 95 </div><div style="text-align: center;"> 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 </div><div style="text-align: center;"> 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 </div><div style="text-align: center;"> 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 </div><div style="text-align: center;"> 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 </div><div style="text-align: center;"> 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 </div><div style="text-align: center;"> 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 </div><div style="text-align: center;"> 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 </div><div style="text-align: center;"> 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 </div><div style="text-align: center;"> 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 </div><div style="text-align: center;"> 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 </div></p><p> Произведение этих чисел составляет 26 × 63 × 78 × 14 = 1788696. Каково наибольшее произведение четырех соседних чисел в том же направлении (вверх, вниз, влево, вправо, или по диагонали) в данном <code>arr</code> сетке? </p>
</section>

Problem 11: Largest product in a grid

<section id="description">
<p>Последовательность чисел треугольника порождается добавлением натуральных чисел. Таким образом, 7-й номер треугольника будет 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять терминов будут: <div style="text-align: center;"> 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... </div> Перечислим коэффициенты первых семи чисел треугольника: <div style="padding-left: 4em;"> <b>1:</b> 1 </div><div style="padding-left: 4em;"> <b>3:</b> 1, 3 </div><div style="padding-left: 4em;"> <b>6:</b> 1, 2, 3, 6 </div><div style="padding-left: 4em;"> <b>10:</b> 1, 2, 5, 10 </div><div style="padding-left: 4em;"> <b>15:</b> 1, 3, 5, 15 </div><div style="padding-left: 4em;"> <b>21:</b> 1, 3, 7, 21 </div><div style="padding-left: 4em;"> <b>28:</b> 1, 2, 4, 7, 14, 28 </div> Мы видим, что 28 - это первое число треугольников, состоящее из пяти делителей. Каково значение первого числа треугольников для <code>n</code> делителей?</p></section>

Problem 12: Highly divisible triangular number

<section id="description">
<p>Выработайте первые десять цифр суммы из следующих ста пятидесятизначных чисел. </p><p> 37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28112879812849979408065481931592621691275889832738 44274228917432520321923589422876796487670272189318 47451445736001306439091167216856844588711603153276 70386486105843025439939619828917593665686757934951 62176457141856560629502157223196586755079324193331 64906352462741904929101432445813822663347944758178 92575867718337217661963751590579239728245598838407 58203565325359399008402633568948830189458628227828 80181199384826282014278194139940567587151170094390 35398664372827112653829987240784473053190104293586 86515506006295864861532075273371959191420517255829 71693888707715466499115593487603532921714970056938 54370070576826684624621495650076471787294438377604 5328265410875682844319119063469 4037855217779295145 36123272525000296071075082563815656710885258350721 45876576172410976447339110607218265236877223636045 17423706905851860660448207621209813287860733969412 81142660418086830619328460811191061556940512689692 51934325451728388641918047049293215058642563049483 62467221648435076201727918039944693004732956340691 15732444386908125794514089057706229429197107928209 55037687525678773091862540744969844508330393682126 18336384825330154686196124348767681297534375946515 80386287592878490201521685554828717201219257766954 78182833757993103614740356856449095527097864797581 16726320100436897842553539920931837441497806860984 48403098129077791799088218795327364475675590848030 87086987551392711854517078544161852424320693150332 59959406895756536782107074926966537676326235447210 69793950679652694742597709739166693763042633987085 41052684708299085211399427365734116182760315001271 65378607361501080857009149939512557028198746004375 35829035317434717326932123578154982629742552737307 94953759765 105305946966067683156574377167401875275 88902802571733229619176668713819931811048770190271 25267680276078003013678680992525463401061632866526 36270218540497705585629946580636237993140746255962 24074486908231174977792365466257246923322810917141 91430288197103288597806669760892938638285025333403 34413065578016127815921815005561868836468420090470 23053081172816430487623791969842487255036638784583 11487696932154902810424020138335124462181441773470 63783299490636259666498587618221225225512486764533 67720186971698544312419572409913959008952310058822 95548255300263520781532296796249481641953868218774 76085327132285723110424803456124867697064507995236 37774242535411291684276865538926205024910326572967 23701913275725675285653248258265463092207058596522 29798860272258331913126375147341994889534765745501 18495701454879288984856827726077713721403798879715 38298203783031473527721580348144513491373226651381 34829543829199918180278916522431027392251122869539 409579530664052326325380441000596549391598 79593635 29746152185502371307642255121183693803580388584903 41698116222072977186158236678424689157993532961922 62467957194401269043877107275048102390895523597457 23189706772547915061505504953922979530901129967519 86188088225875314529584099251203829009407770775672 11306739708304724483816533873502340845647058077308 82959174767140363198008187129011875491310547126581 97623331044818386269515456334926366572897563400500 42846280183517070527831839425882145521227251250327 55121603546981200581762165212827652751691296897789 32238195734329339946437501907836945765883352399886 75506164965184775180738168837861091527357929701337 62177842752192623401942399639168044983993173312731 32924185707147349566916674687634660915035914677504 99518671430235219628894890102423325116913619626622 73267460800591547471830798392868535206946944540724 76841822524674417161514036427982273348055556214818 97142617910342598647204516893989422179826088076852 87783646182799346313767754307809363333018982642090 1084880252167467088321 5120185883543223812876952786 71329612474782464538636993009049310363619763878039 62184073572399794223406235393808339651327408011116 66627891981488087797941876876144230030984490851411 60661826293682836764744779239180335110989069790714 85786944089552990653640447425576083659976645795096 66024396409905389607120198219976047599490197230297 64913982680032973156037120041377903785566085089252 16730939319872750275468906903707539413042652315011 94809377245048795150954100921645863754710598436791 78639167021187492431995700641917969777599028300699 15368713711936614952811305876380278410754449733078 40789923115535562561142322423255033685442488917353 44889911501440648020369068063960672322193204149535 41503128880339536053299340368006977710650566631954 81234880673210146739058568557934581403627822703280 82616570773948327592232845941706525094512325230608 22918802058777319719839450180888072429661980811197 77158542502016545090413245809786882778948721859617 72107838435069186155435662884062257473692284509516 20 849603980134001723930671666823555245252804609722 53503534226472524250874054075591789781264330331690 </p>
</section>

Problem 13: Large sum

<section id="description">
<p>The following iterative sequence is defined for the set of positive integers:</p><p><div style="padding-left: 4em;"><var>n</var> → <var>n</var>/2 (<var>n</var> is even)</div></p>
<p><div style="padding-left: 4em;"><var>n</var> → 3<var>n</var> + 1 (<var>n</var> is odd)</div></p>
<p>Using the rule above and starting with 13, we generate the following sequence:</p><p><div style="text-align: center;">13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1</div></p>
<p>It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.</p>
<p>Which starting number, under the given <code>limit</code>, produces the longest chain?</p>
<p>NOTE: Once the chain starts the terms are allowed to go above one million.</p></section>

Problem 14: Longest Collatz sequence

<section id="description">
<p>Начиная в левом верхнем углу сетки 2 × 2 и только имея возможность двигаться вправо и вниз, ровно 6 маршрутов в нижний правый угол. <img class="img-responsive center-block" alt="диаграмма 6 2 на 2 сетки, показывающая все маршруты в нижний правый угол" src="https://cdn-media-1.freecodecamp.org/imgr/1Atixoj.gif"></p><p> Сколько таких маршрутов существует через заданный <code>gridSize</code> ? </p>
</section>

Problem 15: Lattice paths

<section id="description">
<p>2 <sup>15</sup> = 32768 , а сумма его цифр равна 3 + 2 + 7 + 6 + 8 = 26. Какова сумма цифр числа 2 <sup><code>exponent</code></sup> ?</p></section>

Problem 16: Power digit sum

<section id="description">
<p>Если числа от 1 до 5 записаны словами: один, два, три, четыре, пять, то есть 3 + 3 + 5 + 4 + 4 = 19 букв, используемых в общей сложности. Если все числа от 1 до заданного <code>limit</code> включительно были записаны на словах, сколько букв будет использовано? <b>ПРИМЕЧАНИЕ.</b> Не считайте пробелы или дефисы. Например, 342 (триста сорок два) содержит 23 буквы и 115 (сто пятнадцать) содержит 20 букв. Использование «и» при написании номеров соответствует британскому использованию.</p></section>

Problem 17: Number letter counts

<section id="description">
<p>Начав в верхней части треугольника внизу и перемещаясь к соседним номерам в строке ниже, максимальная сумма сверху вниз составляет 23. <span style="display: block; text-align: center;"><b style="color: red;">3</b> <br> <b style="color: red;">7</b> 4 <br> 2 <b style="color: red;">4</b> 6 <br> 8 5 <b style="color: red;">9</b> 3</span> То есть, 3 + 7 + 4 + 9 = 23. Найдите максимальную сумму сверху вниз от треугольника ниже: <span style="display: block; text-align: center;">75 <br> 95 64 <br> 17 47 82 <br> 18 35 87 10 <br> 20 04 82 47 65 <br> 19 01 23 75 03 34 <br> 88 02 77 73 07 63 67 <br> 99 65 04 28 06 16 70 92 <br> 41 41 26 56 83 40 80 70 33 <br> 41 48 72 33 47 32 37 16 94 29 <br> 53 71 44 65 25 43 91 52 97 51 14 <br> 70 11 33 28 77 73 17 78 39 68 17 57 <br> 91 71 52 38 17 14 91 43 58 50 27 29 48 <br> 63 66 04 68 89 53 67 30 73 16 69 87 40 31 <br> 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23</span> <b>ПРИМЕЧАНИЕ.</b> Поскольку существует только 16384 маршрута, можно решить эту проблему, пробовав каждый маршрут. Однако задача 67 - это та же проблема с треугольником, содержащим сто строк; она не может быть решена грубой силой и требует умного метода! ; О)</p></section>

Problem 18: Maximum path sum I

<section id="description">
<p>Вам предоставляется следующая информация, но вы можете предпочесть сделать некоторые исследования для себя. <ul><li> 1 января 1900 года был понедельник. </li><li> Тридцать дней - сентябрь, <br> Апреле, июне и ноябре. <br> Все остальные тридцать один, <br> Сохраняя только февраль, <br> Который имеет двадцать восемь, дождь или блеск. <br> И на високосные годы, двадцать девять. </li><li> Високосный год происходит в любой год, равномерно делимый на 4, но не на столетие, если он не делится на 400. </li> Сколько воскресений упало в первый месяц месяца в двадцатом веке (1 января 1901 года по 31 декабря 2000 года)? </ul></p>
</section>

Problem 19: Counting Sundays

<section id="description">
<p><var>n</var> ! означает <var>n</var> × ( <var>n</var> - 1) × ... × 3 × 2 × 1 Например, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800, <br> и сумму цифр в цифре 10! равно 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27. Найдите сумму цифр <var>n</var> !</p></section>

Problem 20: Factorial digit sum

<section id="description">
<p>Пусть d ( <var>n</var> ) определяется как сумма собственных делителей <var>n</var> (числа меньше <var>n,</var> которые равномерно делятся на <var>n</var> ). Если d ( <var>a</var> ) = <var>b</var> и d ( <var>b</var> ) = <var>a</var> , где <var>a</var> ≠ <var>b</var> , то <var>a</var> и <var>b</var> являются дружественной парой, и каждый из <var>a</var> и <var>b</var> называется дружественным числом. Например, правильные делители 220 являются 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110; поэтому d (220) = 284. Собственные делители 284 равны 1, 2, 4, 71 и 142; так что d (284) = 220. Оцените сумму всех дружественных чисел при <var>n</var> .</p></section>

Problem 21: Amicable numbers

<section id="description">
<p>Идеальное число - это число, для которого сумма его собственных делителей точно равна числу. Например, сумма правильных делителей 28 будет равна 1 + 2 + 4 + 7 + 14 = 28, что означает, что 28 - идеальное число. Число <var>n</var> называется дефицитным, если сумма его собственных делителей меньше <var>n,</var> и его называют обильным, если эта сумма превышает <var>n</var> . Поскольку 12 - наименьшее обильное число, 1 + 2 + 3 + 4 + 6 = 16, наименьшее число, которое можно записать как сумму двух обильных чисел, равно 24. По математическому анализу можно показать, что все целые числа, большие 28123 можно записать как сумму двух обильных чисел. Однако этот верхний предел еще не может быть уменьшен путем анализа, хотя известно, что наибольшее число, которое не может быть выражено как сумма двух обильных чисел, меньше этого предела. Найдите сумму всех натуральных чисел &#x3C;= <var>n,</var> которые не могут быть записаны в виде суммы двух обильных чисел.</p></section>

Problem 23: Non-abundant sums

<section id="description">
<p>Перестановка - упорядоченная компоновка объектов. Например, 3124 является одной из возможных перестановок цифр 1, 2, 3 и 4. Если все перестановки перечислены численно или в алфавитном порядке, мы называем это лексикографическим порядком. Лексикографические перестановки 0, 1 и 2: <div style="text-align: center;"> 012 021 102 120 201 210 </div> Что такое <var>n-</var> я лексикографическая перестановка цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9?</p></section>

Problem 24: Lexicographic permutations

<section id="description">
<p>Последовательность Фибоначчи определяется рекуррентным соотношением: <div style="padding-left: 4em;"> F <sub>n</sub> = F <sub>n-1</sub> + F <sub>n-2</sub> , где F <sub>1</sub> = 1 и F <sub>2</sub> = 1. </div> Следовательно, первые 12 терминов будут: <div style="padding-left: 4em; display: inline-grid; grid-template-rows: auto; row-gap: 7px;"><div> F <sub>1</sub> = 1 </div><div> F <sub>2</sub> = 1 </div><div> F <sub>3</sub> = 2 </div><div> F <sub>4</sub> = 3 </div><div> F <sub>5</sub> = 5 </div><div> F <sub>6</sub> = 8 </div><div> F <sub>7</sub> = 13 </div><div> F <sub>8</sub> = 21 </div><div> F <sub>9</sub> = 34 </div><div> F <sub>10</sub> = 55 </div><div> F <sub>11</sub> = 89 </div><div> F <sub>12</sub> = 144 </div></div> 12-й термин, F <sub>12</sub> , является первым термином, содержащим три цифры. Что такое индекс первого слагаемого в последовательности Фибоначчи, который содержит <var>n</var> цифр?</p></section>

Problem 25: 1000-digit Fibonacci number

<section id="description">
<p>Единичная доля содержит 1 в числителе. Дано десятичное представление единичных дробей с знаменателями от 2 до 10: <div style="padding-left: 4em; display: inline-grid; grid-template-rows: auto; row-gap: 7px;"><div> <sup><sub>1/2</sub></sup> = 0,5 </div><div> <sup><sub>1/3</sub></sup> = 0. (3) </div><div> На <sup><sub>1/4</sub></sup> = 0,25 </div><div> <sup><sub>1/5</sub></sup> = 0,2 </div><div> <sup><sub>1/6</sub></sup> = 0,1 (6) </div><div> <sup><sub>1/7</sub></sup> = 0. (142857) </div><div> На <sup><sub>1/8</sub></sup> = 0,125 </div><div> <sup><sub>1/9</sub></sup> = 0. (1) </div><div> <sup><sub>1/10</sub></sup> = 0,1 </div></div> Где 0,1 (6) означает 0.166666 ... и имеет повторяющийся цикл из 1 цифры. Можно видеть , что <sup><sub>1/7</sub></sup> имеет 6-значный повторяющийся цикл. Найдите значение <var>d</var> &#x3C; <var>n,</var> для которого <sup>1</sup> / <sub>d</sub> содержит самый длинный повторяющийся цикл в его десятичной дробной части.</p></section>

Problem 26: Reciprocal cycles

<section id="description">
<p>Эйлер обнаружил замечательную квадратичную формулу: $ n ^ 2 + n + 41 $ Оказывается, что формула будет давать 40 простых чисел для последовательных целочисленных значений $ 0 \ le n \ le 39 $. Однако, когда $ n = 40, 40 ^ 2 + 40 + 41 = 40 (40 + 1) + 41 $ делится на 41, и, конечно, когда $ n = 41, 41 ^ 2 + 41 + 41 $ явно делится на 41. Была обнаружена невероятная формула $ n ^ 2 - 79n + 1601 $, которая дает 80 простых чисел для последовательных значений $ 0 \ le n \ le 79 $. Произведением коэффициентов -79 и 1601 является -126479. Учитывая квадратичность вида: </p><p> $ n ^ 2 + an + b $, где $ | a | &#x3C;диапазон $ и $ | b | \ le range $, где $ | n | $ - модуль / абсолютное значение $ n $, например $ | 11 | = 11 $ и $ | -4 | = 4 $ </p><p> Найдите произведение коэффициентов $ a $ и $ b $ для квадратичного выражения, которое выражает максимальное число простых чисел для последовательных значений $ n $, начиная с $ n = 0 $. </p>
</section>

Problem 27: Quadratic primes

<section id="description">
<p>Начиная с номера 1 и перемещаясь вправо по часовой стрелке, спираль 5 на 5 формируется следующим образом: 21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 Это может быть проверено, что сумма чисел на диагоналях равна 101. Какова сумма чисел на диагоналях по а с помощью спирали, образованной таким же образом?</p></section>

Problem 28: Number spiral diagonals

<section id="description">
<p>Рассмотрим все целые комбинации ab для 2 ≤ a ≤ 5 и 2 ≤ b ≤ 5: 22 = 4, 23 = 8, 24 = 16, 25 = 32 32 = 9, 33 = 27, 34 = 81, 35 = 243 42 = 16, 43 = 64, 44 = 256, 45 = 1024 52 = 25, 53 = 125, 54 = 625, 55 = 3125. Если они затем помещаются в числовом порядке, при удалении любых повторений мы получаем следующую последовательность из 15 различные термины: 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125 Сколько различных членов в последовательности, сгенерированной ab для 2 ≤ a ≤ n и 2 ≤ b ≤ n?</p></section>

Problem 29: Distinct powers

<section id="description">
<p>Удивительно, что есть только три числа, которые могут быть записаны как сумма четвертых степеней их цифр: 1634 = 1 <sup>4</sup> + 6 <sup>4</sup> + 3 <sup>4</sup> + 4 <sup>4</sup> 8208 = 8 <sup>4</sup> + 2 <sup>4</sup> + 0 <sup>4</sup> + 8 <sup>4</sup> 9474 = 9 <sup>4</sup> + 4 <sup>4</sup> + 7 <sup>4</sup> + 4 <sup>4</sup> Поскольку 1 = 1 <sup>4</sup> не является суммой, она не включена. Сумма этих чисел равна 1634 + 8208 + 9474 = 19316. Найдите сумму всех чисел, которые могут быть записаны как сумма n степеней их цифр.</p></section>

Problem 30: Digit n powers

<section id="description">
<p>В Англии валюта состоит из фунта, фунта стерлингов и фунта стерлингов, а в общей тираж - восемь монет: 1p, 2p, 5p, 10p, 20p, 50p, £ 1 (100p) и £ 2 (200p). Можно сделать £ 2 следующим образом: 1 × £ 1 + 1 × 50p + 2 × 20p + 1 × 5p + 1 × 2p + 3 × 1p. Сколько разных способов может быть выполнено (n) с использованием любого числа монет?</p></section>

Problem 31: Coin sums

<section id="description">
<p>Мы будем говорить, что n-значное число является pandigital, если оно использует все цифры от 1 до n ровно один раз; например, 5-значное число, 15234, составляет от 1 до 5 pandigital. </p><p> Продукт 7254 необычен, так как идентичность 39 × 186 = 7254, содержащая мультипликацию, множитель и продукт от 1 до 9 pandigital. </p><p> Найдите сумму всех продуктов, чей идентификатор multipicand / multiplier / product может быть записан как от 1 до 9 pandigital. </p><p> СОВЕТ. Некоторые продукты могут быть получены более чем одним способом, поэтому обязательно включайте их только один раз в свою сумму. </p>
</section>

Problem 32: Pandigital products

<section id="description">
<p>Фракцию <sup><sub>49/98</sub></sup> любопытная фракция, как неопытная математика в попытке упростить это может ошибочно полагает , что <sup><sub>49/98</sub></sup> = <sup><sub>4/8,</sub></sup> который является правильным, получается путем погашения 9s. Мы будем рассматривать фракции нравятся, <sup><sub>30/50</sub></sup> = <sup><sub>3/5,</sub></sup> чтобы быть тривиальными примерами. Существует ровно четыре нетривиальных примера этого типа фракции, меньше единицы по значению и содержат две цифры в числителе и знаменателе. Если произведение этих четырех фракций дано в наименьших общих терминах, найдите значение знаменателя.</p></section>

Problem 33: Digit cancelling fractions

<section id="description">
<p>145 - любопытное число, как 1! + 4! + 5! = 1 + 24 + 120 = 145. Найти числа и сумму чисел, которые равны сумме факториала их цифр. Примечание: как 1! = 1 и 2! = 2 не являются суммами, которые они не включены.</p></section>

Problem 34: Digit factorials

<section id="description">
<p>Число 197, называется круговым простым, поскольку все повороты цифр: 197, 971 и 719 сами по себе являются первыми. Есть тринадцать таких простых чисел ниже 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 и 97. Сколько круговых простых чисел ниже n, тогда как 100 &#x3C;= n &#x3C; = 1000000?</p></section>

Problem 35: Circular primes

<section id="description">
<p>The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.</p>
<p>Find the sum of all numbers, less than n, whereas 1000 &#x3C;= n &#x3C;= 1000000, which are palindromic in base 10 and base 2.</p>
<p>(Please note that the palindromic number, in either base, may not include leading zeros.)</p></section>

Problem 36: Double-base palindromes

<section id="description">
<p>Число 3797 имеет интересное свойство. Будучи простым, можно непрерывно удалять цифры слева направо и оставаться первичными на каждом этапе: 3797, 797, 97 и 7. Аналогичным образом мы можем работать справа налево: 3797, 379, 37 и 3. Найдите сумму единственных n (8 &#x3C;= n &#x3C;= 11) простых чисел, которые обе усекаются слева направо и справа налево. ПРИМЕЧАНИЕ. 2, 3, 5 и 7 не считаются усеченными штрихами.</p></section>

Problem 37: Truncatable primes

<section id="description">
<p>Возьмите номер 192 и умножьте его на каждый из 1, 2 и 3: 192 × 1 = 192 192 × 2 = 384 192 × 3 = 576. Объединив каждый продукт, мы получим от 1 до 9 pandigital, 192384576. Мы позвоним 192384576 конкатенированный продукт 192 и (1, 2, 3). То же самое можно достичь, начиная с 9 и умножая на 1, 2, 3, 4 и 5, давая pandigital, 918273645, который является конкатенированным продуктом 9 и (1, 2, 3, 4, 5). Что представляет собой наибольшее от 1 до 9 pandigital 9-значное число, которое может быть сформировано как конкатенированное произведение целого числа с (1, 2, ..., <var>n</var> ), где <var>n</var> > 1?</p></section>

Problem 38: Pandigital multiples

<section id="description">
<p>Если p - периметр прямоугольного треугольника со сторонами целой длины, {a, b, c}, то существует ровно три решения для p = 120. {20,48,52}, {24,45,51}, { 30,40,50} Для какого значения p ≤ n, число решений максимизировано?</p></section>

Problem 39: Integer right triangles

<section id="description">
<p>An irrational decimal fraction is created by concatenating the positive integers:</p><p><span style="display: block; text-align: center;">0.12345678910<b style="color: red;">1</b>112131415161718192021...</span></p>
<p>It can be seen that the 12<sup>th</sup> digit of the fractional part is 1.</p>
<p>If <i>d<sub>n</sub></i> represents the <i>n</i><sup>th</sup> digit of the fractional part, find the value of the following expression.</p><p><span style="display: block; text-align: center;">d<sub>1</sub> × d<sub>10</sub> × d<sub>100</sub> × d<sub>1000</sub> × d<sub>10000</sub> × d<sub>100000</sub> × d<sub>1000000</sub></span></p>
</section>

Problem 40: Champernowne's constant

<section id="description">
<p>We shall say that an <i>n</i>-digit number is pandigital if it makes use of all the digits 1 to <i>n</i> exactly once. For example, 2143 is a 4-digit pandigital and is also prime.</p>
<p>What is the largest <i>n</i>-length digit pandigital prime that exists?</p></section>

Problem 41: Pandigital prime

<section id="description">
<p>N-й член последовательности чисел треугольника задается выражением tn = ½n (n + 1); поэтому первые десять чисел треугольника: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... путем преобразования каждой буквы в слово в число, соответствующее его алфавитному положению, и добавление этих значений мы формируем значение слова. Например, значение слова для SKY равно 19 + 11 + 25 = 55 = t10. Если значение слова является числом треугольника, мы будем называть слово треугольным словом. Используя массив слов n-длины, сколько из них являются треугольными словами?</p></section>

Problem 42: Coded triangle numbers

<section id="description">
<p>Число, 1406357289, представляет собой число от 0 до 9 pandigital, потому что оно составлено из каждой цифры от 0 до 9 в некотором порядке, но также имеет довольно интересное свойство делимости подстроки. Пусть d1 - первая цифра, d2 - вторая цифра и т. Д. Таким образом, отметим следующее: d2d3d4 = 406 делится на 2 d3d4d5 = 063 делится на 3 d4d5d6 = 635 делится на 5 d5d6d7 = 357 делится на 7 d6d7d8 = 572 делится на 11 d7d8d9 = 728 делится на 13 d8d9d10 = 289 делится на 17. Найдите числа от 0 до 9 pandigital номеров с этим свойством.</p></section>

Problem 43: Sub-string divisibility

<section id="description">
<p>Pentagonal numbers are generated by the formula, P<sub>n</sub>=<var>n</var>(3<var>n</var>−1)/2. The first ten pentagonal numbers are:</p><p><span style="display: block; text-align: center;">1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...</span></p>
<p>It can be seen that P<sub>4</sub> + P<sub>7</sub> = 22 + 70 = 92 = P<sub>8</sub>. However, their difference, 70 − 22 = 48, is not pentagonal.</p>
<p>Find the pair of pentagonal numbers, P<sub>j</sub> and P<sub>k</sub>, for which their sum and difference are pentagonal and D = |P<sub>k</sub> − P<sub>j</sub>| is minimised; what is the value of D?</p></section>

Problem 44: Pentagon numbers

<section id="description">
<p>Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:</p><p><div style="display: inline-grid; text-align: center; grid-template-columns: repeat(3, minmax(117px, 12%)); grid-template-rows: auto;"><div>Triangle</div><div>T<sub>n</sub>=<var>n</var>(<var>n</var>+1)/2</div><div>1, 3, 6, 10, 15, ...</div></div></p>
<p><div style="display: inline-grid; text-align: center; grid-template-columns: repeat(3, minmax(117px, 12%)); grid-template-rows: auto;"><div>Pentagonal</div><div>P<sub>n</sub>=<var>n</var>(3<var>n</var>−1)/2</div><div>1, 5, 12, 22, 35, ...</div></div></p>
<p><div style="display: inline-grid; text-align: center; grid-template-columns: repeat(3, minmax(117px, 12%)); grid-template-rows: auto;"><div>Hexagonal</div><div>H<sub>n</sub>=<var>n</var>(2<var>n</var>−1)</div><div>1, 6, 15, 28, 45, ...</div></div></p>
<p>It can be verified that T<sub>285</sub> = P<sub>165</sub> = H<sub>143</sub> = 40755.</p>
<p>Find the next triangle number that is also pentagonal and hexagonal.</p></section>

Problem 45: Triangular, pentagonal, and hexagonal

<section id="description">
<p>Христианом Гольдбахом было предложено, что каждое нечетное составное число может быть записано как сумма простого и дважды квадрата. 9 = 7 + 2 × 1 <sup>2</sup> 15 = 7 + 2 × 2 <sup>2</sup> 21 = 3 + 2 × 3 <sup>2</sup> 25 = 7 + 2 × 3 <sup>2</sup> 27 = 19 + 2 × 2 <sup>2</sup> 33 = 31 + 2 × 1 <sup>2</sup> что гипотеза была ложной. Каков самый маленький нечетный композит, который не может быть записан как сумма простого и дважды квадрата?</p></section>

Problem 46: Goldbach's other conjecture

<section id="description">
<p>Первые два последовательных номера имеют два разных основных фактора: <div style="padding-left: 4em;"> 14 = 2 × 7 </div><div style="padding-left: 4em;"> 15 = 3 × 5 </div> Первые три последовательных номера имеют три различных основных фактора: <div style="padding-left: 4em;"> 644 = 2 × × 7 × 23 </div><div style="padding-left: 4em;"> 645 = 3 × 5 × 43 </div><div style="padding-left: 4em;"> 646 = 2 × 17 × 19 </div> Найдите первые четыре последовательных целых числа, каждый из которых имеет четыре различных основных фактора. Каков первый из этих чисел?</p></section>

Problem 47: Distinct primes factors

<section id="description">
<p>Серия, 1 <sup>1</sup> + 2 <sup>2</sup> + 3 <sup>3</sup> + ... + 10 <sup>10</sup> = 10405071317. Найдите последние десять цифр серии, 1 <sup>1</sup> + 2 <sup>2</sup> + 3 <sup>3</sup> + ... + 1000 <sup>1000</sup> .</p></section>

Problem 48: Self powers

<section id="description">
<p>Арифметическая последовательность, 1487, 4817, 8147, в которой каждое из членов увеличивается на 3330, необычна двумя способами: (i) каждое из трех членов является простым, и (ii) каждое из 4-значных чисел перестановки друг друга. Нет арифметических последовательностей, состоящих из трех 1-, 2- или 3-значных простых чисел, обладающих этим свойством, но есть еще одна 4-значная возрастающая последовательность. Какое 12-значное число вы формируете, объединяя три термина в этой последовательности?</p></section>

Problem 49: Prime permutations

<section id="description">
<p>Первичная 41, может быть записана как сумма шести последовательных простых чисел: 41 = 2 + 3 + 5 + 7 + 11 + 13. Это самая длинная сумма последовательных простых чисел, которая добавляет к простому ниже ста сто. Самая длинная сумма последовательных простых чисел ниже одной тысячи, добавляющая к простому, содержит 21 член и равна 953. Какое простое число ниже миллиона может быть записано как сумма самых последовательных простых чисел?</p></section>

Problem 50: Consecutive prime sum

<section id="description">
<p>Заменяя 1-ю цифру 2-значного числа * 3, получается, что шесть из девяти возможных значений: 13, 23, 43, 53, 73 и 83 - все просто. Заменяя 3-ю и 4-ю цифры 56 ** 3 на одну и ту же цифру, это 5-значное число является первым примером, состоящим из семи простых чисел среди десяти сгенерированных чисел, приводящих к семейству: 56003, 56113, 56333, 56443, 56663, 56773 , и 56993. Следовательно, 56003, являясь первым членом этого семейства, является наименьшим простым с этим свойством. Найдите наименьшее число, которое, заменив часть номера (не обязательно смежные цифры) с той же цифрой, является частью восьми семейств с праймисом.</p></section>

Problem 51: Prime digit replacements

<section id="description">
<p>Можно видеть, что число 125874 и его двойное 251748 содержат точно такие же цифры, но в другом порядке. Найдите наименьшее положительное целое число x, такое, что 2x, 3x, 4x, 5x и 6x содержат одинаковые цифры.</p></section>

Problem 52: Permuted multiples

<section id="description">
<p>Существует ровно десять способов выбора трех из пяти, 12345: 123, 124, 125, 134, 135, 145, 234, 235, 245 и 345. В комбинаторике мы используем обозначение 5C3 = 10. В общем, </p><p> nCr = n! r! (n-r)! , где r ≤ n, n! = n × (n-1) × ... × 3 × 2 × 1 и 0! = 1. </p><p> Только до n = 23 значение превышает один миллион: 23C10 = 1144066. Сколько, не обязательно различных значений nCr для 1 ≤ n ≤ 100, превышает один миллион? </p>
</section>

Problem 53: Combinatoric selections

<section id="description">
<p>В покерной карточной игре рука состоит из пяти карт и оценивается от самого низкого до самого высокого, следующим образом: High Card: карта с наивысшим значением. Одна пара: две карты одинакового значения. Две пары: две разные пары. Три вида: три карты одинакового значения. Прямо: все карты являются последовательными значениями. Flush: все карты одного и того же костюма. Полный дом: три вида и пара. Четыре вида: четыре карты одинакового значения. Straight Flush: все карты являются последовательными значениями одного и того же костюма. Royal Flush: десять, Джек, королева, король, туз, в одном костюме. Карты оцениваются в порядке: 2, 3, 4, 5, 6, 7, 8, 9, 10, Джек, Королева, Король, Туз. Если два игрока имеют одинаковые ранжированные руки, тогда выигрывает звание, состоящее из наибольшего выигрыша; например, пара восьмерок бьет пару пятерок (см. пример 1 ниже). Но если, например, два ранга связаны, у обоих игроков есть пара ферзей, тогда сравниваются старшие карты в каждой руке (см. Пример 4 ниже); если старшие карты связаны, то сравниваются следующие старшие карты и так далее. Рассмотрим следующие пять рук для двух игроков: </p><p> Ручной игрок 1 Игрок 2 Победитель 1 5H 5C 6S 7S KDPair of Fives 2C 3S 8S 8D TDPair of Eights Player 2 2 5D 8C 9S JS ACHighest карта Ace 2C 5C 7D 8S QHHighest карта Queen Player 1 3 2D 9C AS AH ACThree Aces 3D 6D 7D TD QDFlush с Diamonds Player 2 4 4D 6S 9H QH QCPair QueensHighest карта Девять 3D 6D 7H QD QSPair QueensHighhest карта Семь игроков 1 5 2H 2D 4C 4D 4SFull HouseWith Three Fours 3C 3D 3S 9S 9DFull Housewith Three Threes Player 1 </p><p> Файл, poker.txt, содержит тысячу случайных раздач, раздаваемых двум игрокам. Каждая строка файла содержит десять карт (разделенных одним пробелом): первые пять - карты игрока 1, а последние пять - карты игрока 2. Вы можете предположить, что все руки действительны (нет недопустимых символов или повторных карт), рука каждого игрока не имеет определенного порядка, и в каждой руке есть явный победитель. Сколько рук выигрывает игрок 1? </p>
</section>