Created
May 25, 2020 14:35
-
-
Save laerllik/4b4b4c2428e89f5fde55b48f4aad2c23 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const fs = require('fs'); | |
| const buildStepCounter = (step = 1) => () => step++ | |
| list = [9,10,14,15,17,19,24,24,26,28,29,31,33,33,42,42,47,47,58,59,61] | |
| node = 47 | |
| let result = '' | |
| const linearSearch = (node, list) => { | |
| let resultIndex; | |
| for (index=0; index < list.length; index++){ | |
| result += `${stepCounter()}) Устанавливаем значение индекса равным ${index}\n` | |
| result += `${stepCounter()}) Сравниваем элемент массив[индекс] и искомое значение\n` | |
| if (list[index] == node) { | |
| result += `${stepCounter()}) Запоминаем значение индекса\n` | |
| resultIndex = index | |
| } | |
| result += `${stepCounter()}) Возвращаемся в начало цикла\n` | |
| } | |
| result += `${stepCounter()}) Выводим последнее запомненое значение индекса равное ${resultIndex}\n` | |
| }; | |
| const binarySearch = (node, list, start, end) => { | |
| const middle = Math.floor((start + (end - start)/2)); | |
| result += `${stepCounter()}) Проверяем массив от ${start} до ${end}. Средний индекс ${middle}\n` | |
| result += `${stepCounter()}) Проверяем условие конечный индекс == начальный индекс < 2\n` | |
| if (end == start) { | |
| result += `${stepCounter()}) Так как условие выполнено, рекурсия окончена - выводим начальный индекс равный ${start}\n` | |
| return start | |
| } else { | |
| result += `${stepCounter()}) Так как условие не выполнено, проверяем условие массив[срединый индекс] > искомый элемент\n` | |
| if (list[middle] > node) { | |
| result += `${stepCounter()}) Так как условие выполнено, вызовем поиск(искомый элемент, массив, середина+1, конец)\n` | |
| return binarySearch(node, list, middle + 1, end) | |
| } else { | |
| result += `${stepCounter()}) Так как условие выполнено, вызовем поиск(искомый элемент, массив, начало, середина)\n` | |
| return binarySearch(node, list, start, middle) | |
| } | |
| } | |
| } | |
| const fibSearch = (node, list) => { | |
| const fib = n => { | |
| return n <= 1 ? n : fib(n - 1) + fib(n - 2); | |
| } | |
| let currentFibNumber = 2 | |
| while (true) { | |
| result += `${stepCounter()}) Число Фибоначчи = ${fib(currentFibNumber)}\n` | |
| let end | |
| result += `${stepCounter()}) Сравниваем число Фибоначчи и длину массива\n` | |
| if (fib(currentFibNumber) < list.length -1) { | |
| end = fib(currentFibNumber) | |
| } else { | |
| end = list.length - 1 | |
| result += `${stepCounter()}) Так как длина массива больше чем число Фибоначчи, то вместо числа Фибонначи возьмем длину массива ${end}\n` | |
| } | |
| result += `${stepCounter()}) Сравниваем элемент под номером ${end} и искомый элемент\n` | |
| if (list[end] > node) { | |
| let res; | |
| result += `${stepCounter()}) Проводим перебор с ${fib(currentFibNumber - 1)} до ${end}\n` | |
| for (i = fib(currentFibNumber - 1); i <= list[end]; i++) { | |
| if (list[i] == node) { | |
| res = i; | |
| } | |
| } | |
| result += `${stepCounter()}) Выводим индекс найденного элемента ${res}\n` | |
| return res; | |
| } | |
| result += `${stepCounter()}) Возвращаемся в начало цикла\n` | |
| currentFibNumber++ | |
| } | |
| } | |
| let stepCounter = buildStepCounter() | |
| linearSearch(node, list) | |
| fs.writeFileSync("linear.txt", result) | |
| result = '' | |
| stepCounter = buildStepCounter() | |
| binarySearch(node, list, 0, list.length-1) | |
| fs.writeFileSync("binary.txt", result) | |
| result = '' | |
| stepCounter = buildStepCounter() | |
| fibSearch(node, list) | |
| fs.writeFileSync("fib.txt", result) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment