Меню

Базовые алгоритмы на JS

08.05.2018 - Алгоритмы
Базовые алгоритмы на JS

Базовые алгоритмы и структуры данных

Фибоначчи

function recursive(n) {
    if(n <= 2) {
        return 1;
    } else {
        return recursive(n-1) + recursive(n-2);
    }
}

Фибоначчи 2

function fib(n) {
    return n <= 1 ? n : fib(n-1) + fib(n-2);
}

Фибоначчи 3

function fib(n) {
    var a = 1, b = 1;
    for(var i = 3; i <= n; i++) {
        var c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Фибоначчи 4 с мемоизацией

let memo = [];
let fib = function(n) {
    if(memo[n]) return memo[n];
    let current = 0;
    let next = 1;
    for(let i = 0; i < n; i++) {
        memo[i] = current;
        [current, next] = [next, current + next];
    }
    return current;
}

Факториал

function computeFactorial(num) {
    let result = 1;
    for(let i = 2; i <- num; i++) {
        result *= i
    }
    return result;
}

Факториал рекурсией

function computeFactorial(num) {
    if(num === 1) {
        return 1;
    } else {
        return num * computeFactorial(num - 1);
    }
}

Перевод между системами счисления

let toBinary = function (decNum) {
    return parseInt(decNum, 10).toString(2);
}

let toDecimal = function(binary) {
    return parseInt(binary, 2).toString(10);
}

Перевод в двоичную систему

function decToBinary(decNumber) {
    let stack = [];
    let binString = "";
    while(decNumber > 0) {
        let rem = decnumber % 2;
        stack.push(rem);
        decNumber = Math.floor(decNumber / 2);
    }
}

Перевод в двоичную систему через рекурсию

function decToBin(number) {
    let result = [];
    process(number);
    function process(number) {
        if(number !== 1) {
            process(Math.floor(number / 2));
        }
        result.push(number%2);
        return result;
    }
    return result.join("");
}

Поиск простого числа в массиве

function isPrime(element, index, array) {
  var start = 2;
  while (start <= Math.sqrt(element)) {
    if (element % start++ < 1) {
      return false;
    }
  }
  return element > 1;
}
console.log([4, 6, 8, 12].find(isPrime)); //undefined, не найдено
console.log([4, 5, 8, 12].find(isPrime)); //5

Сортировка

Bubble Sort

function bubbleSort(arr) {
    let wall = arr.length;
    while(wall) {
        for(let i = 0; i < arr.length; i++) {
            if(arr[i] > arr[i + 1]) {
                [arr[i], arr[i+1]] = [arr[i+1], arr[i]];
            }
        }
        wall--;
    }
    return arr;
}

QuickSort

function QuickSort(arr) {
    if(arr.length === 0) return [];
    let a = [], b = [], pivot = arr[0];
    for(let i = 1; i < arr.length; i++) {
        if(arr[i] < pivot) a.push[arr[i]];
        else b.push(arr[i]);
    }
    return QuickSort(a).concat(pivot, QuickSort(b));
}

Структуры данных

LinkedList

function Node(data) {
    this.data = data;
    this.next = null;
}

function LinkedList() {
    this.head = null;
    this.tail = null;
    this.count = 0;
}

LinkedList.prototype.length = function() {
    return this.count;
}

LinkedList.prototype.add = function(data) {
    let node = new Node(data);
    if(!this.head) {
        this.head = node;
        this.tail = node;
    } else {
        this.tail.next = node;
        this.tail = node;
    }
    this.count++;
}

LinkedList.prototype.remove = function(data) {
    let previous = this.head;
    let current = this.head;

    while(current) {
        if(current.data === data) {
            if(current === this.head) {
                this.head = this.head.next;
            }
            if(current === this.tail) {
                this.tail = previous;
            }
            previous.next = current.next;
            this.count--;
        } else {
            previous = current;
        }
        current = current.next;
    }
}
Метки: , , , , ,

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *