Математический способ решения задач программирования

Общеизвестно, что компьютер был создан, чтобы производить вычисления. Процессор - это, по сути, высокопроизводительный калькулятор, но есть кое-что, что меня сильно усложняет, когда я работаю над разработкой программного обеспечения. За свою карьеру я видел, как многим программистам не хватает математических понятий, и этот недостаток не означает, что эти программисты не очень хороши в разработке программного обеспечения. На самом деле, я не вижу себя использующим математические концепции, которые я изучил в инженерном колледже, в своей повседневной работе.

С прошлого года я начал тратить время на изучение различных алгоритмов и решение задач кода, затем я понял, что мы можем больше говорить о математике и программировании, и, возможно, мы могли бы посмотреть другими глазами на проблемы, с которыми мы сталкиваемся каждый день.

Цель этой статьи - показать несколько примеров «математического способа» решения задач и побудить больше людей говорить об этом.

Алгоритм Флойда "черепаха и заяц"

Иногда нам нужно проверить, есть ли у связного списка цикл. Хороший способ проверки - повторение связанного списка и использование HashMap для хранения узлов, когда вы достигнете узла, который уже находится в HashMap, вы знаете, что в этом связанном списке есть цикл, и если вы дойдете до конца Связанный список означает, что цикла нет.

Это будет примерно так:

function hasCycle(head) {
  if (!head || !head.next) {
    return false
  }
  let pointer = head
  const hashmap = {}
  while (pointer) {
    if (hashmap[pointer]) { // cycle point
      return true
    }
    hashmap[pointer] = pointer
    pointer = pointer.next
  }
  return false
}

Проблема с этим алгоритмом в том, что вам нужна дополнительная переменная с размером связного списка, поэтому пространственная сложность будет такой же, как временная сложность: O (n). Возможно, есть лучший способ найти цикл в связанном списке.

Алгоритм Флойда - это способ найти циклы и / или повторяющиеся записи в массиве (здесь для получения дополнительной информации) с очень хорошей производительностью. Алгоритм состоит в использовании двух переменных для перебора массива, где одна переменная будет черепахой, а другая - зайцем. Как всем известно, в реальной жизни Заяц быстрее черепахи, поэтому идея состоит в том, что Заяц повторяет в два раза больше скорости Черепахи, и они встречаются друг с другом в точке цикла.

function hasCycle(head) {
  if (!head || !head.next) {
    return false
  }
  let tortoise = head
  let hare = head.next

  while (hare && hare.next) {
    if (tortoise === hare) { // cycle point
      return true
    }
    tortoise = tortoise.next
    hare = hare.next.next // 2 times tortoise
  }
  return false
}

Алгоритм Флойда имеет временную сложность O (n), как и предыдущий код, но пространственная сложность составляет O (1). Математическое объяснение этого алгоритма состоит в том, что у нас есть две функции, которые будут иметь одинаковое значение, но в разные моменты. Взгляните ниже:

Более короткое расстояние, необходимое для прохождения до точки встречи, равно x + y, в противном случае большее расстояние будет x + y + z + y, что должно привести к тому же положению уравнение более короткого расстояния. Если вы помните математические концепции средней школы, мы знаем, что способ найти пересечение двух функций - это сопоставление друг с другом, так как Заяц будет иметь в два раза большую скорость, чем Черепаха, мы можем установить 2 (x + y ) = x + y + z + y, потому что мы знаем, что они встретятся друг с другом в точке пересечения, поэтому положение должно быть таким же.

2(x + y) = x + y + z + y
2x + 2y = x + 2y + z
x = z

Конечно, это поверхностное объяснение. Вы можете прочитать подробное и очень хорошее объяснение здесь.

Испытание кода HackerRank «Кенгуру»

Задача кенгуру заключается в том, чтобы найти двух кенгуру, которые стартовали в разных положениях (x1 и x2) и с разной скоростью (v1 и v2) когда-нибудь встретятся. Кто угодно мог решить проблему так:

if v1 == v2 and x1 != x2: # if same speed, they will never meet
    return('NO')

if x1 < x2 and v1 < v2:
    return('NO')
if x1 > x2 and v1 > v2:
    return('NO')
if x1 < x2 and v1 > v2:
    while x1 != x2:
        x1 = x1 + v1
        x2 = x2 + v2
        if x1 == x2:
            return ('YES')
        if x1 > x2:
            return ('NO')
            break
if x1 > x2 and v1 < v2:
    while x1 != x2:
        x1 = x1 + v1
        x2 = x2 + v2
        if x1 == x2:
            return ('YES')
        if x1 < x2:
            return ('NO')
            break

Это верный ответ и выполняет свою роль. По моему опыту, я попросил нескольких кандидатов, с которыми я проводил собеседование, попытаться решить эту проблему на доске, и 100% из них пытались решить, используя описанный выше способ.

Что ж, используя идею, о которой мы говорили в алгоритме черепахи и зайца Флойда, мы можем думать, что каждый кенгуру - это уравнение положения, где у нас есть положение и скорость, как в физике. Итак, думая так, мы можем написать уравнения и сопоставить друг друга, чтобы увидеть, пересекутся ли они в какой-то момент.

Например, если Kangoroo 1 имеет v1 = 1, x1 = 4, а Kangoroo 2 имеет v1 = 2, x1 = 2, мы можем написать их функции, например:

• Кангору 1 = 2x + 4
• Кангору 2 = 4x + 2

4x + 2 = 2x + 4
4x - 2x = 4 - 2
2x = 2
x = 1

И вы можете использовать значение x = 1, чтобы найти значение y

Using the Kangoroo 1 equation:
y = 2x + 4
y = 2 * 1 + 4
y = 6
Using the Kangoroo 2 equation
y = 4x + 2
y = 4 * 1 + 2
y = 6

И когда мы рисуем на графике, мы можем видеть точку пересечения в (1,6):

Итак, мы можем использовать эту идею, чтобы узнать, встретятся ли кенгуру в какой-то момент. Вместо реализации циклов, которые увеличивают временную сложность, мы можем легко использовать математику для решения проблемы и сохранить постоянную временную сложность O (1):

• Общее уравнение Кангуру будет выглядеть следующим образом: ax + y
• x1 и x2 равны y
• v1 и v2 - это a
• Уравнение Кангуру 1: x1 * x + v1
• Уравнение Кангуру 2: x2 * x + v2

x1 * x + v1 = x2 * x + v2
x ( x1 - x2 ) = v2 - v1
x = ( v2 - v1 ) / ( x1 - x2 )

По сути, нам нужно напрямую записать последнее условие, используя значение x, и проверить, действительно ли деление (это означает, что точка существует и является допустимой точкой), другими словами, результат должно быть больше 0 и % 1 должно быть 0:

const res = (x1 - x2)/(v2 - v1)
if (res >= 0 && (res)%1 === 0)
  return 'YES';
return 'NO';

Накопительный массив

Если вы недавно смотрели телевизор, вы, вероятно, уже видели кумулятивный график случаев заболевания коронавирусом, подобный приведенному ниже:

Кумулятивная функция распределения - обычное дело для профессионалов статистики. Идея состоит в том, что на каждом «шаге» вы добавляете общую сумму к совокупному графику, и график обычно имеет тенденцию расти.

Мы можем думать, что каждая запись в массиве - это «шаг». Итак, в этом случае значение записи будет накапливаться каждый раз, когда мы повторяем массив, и мы можем преобразовать массив в совокупный массив. Посмотрите на пример ниже:

const A = [3,8,1,3,2,1,8,9,0]
for (let i = 1 ; i < A.length ; i++) {
  A[i] += A[i - 1]
}
console.log(A) // [3, 11, 14, 17, 19, 20, 28, 37, 37]

Алгоритм Кадане использует этот принцип для нахождения максимальной суммы подмассива. По сути, идея состоит в том, чтобы накопить значение записей в переменной и проверить, является ли это значение самым большим.

function maximumSubArray(A) {
  let aux = 0
  let sum = 0
  
  for (let i = 0; i < A.length; i++) {
    aux = Math.max(0, aux + A[i]) // cumulative sum
    sum = Math.max(sum, aux)
  }
  return sum
}

Когда вам нужно найти максимальную сумму двух неперекрывающихся подмассивов, вы можете использовать кумулятивную функцию и просто вычесть индексы, чтобы найти сумму в определенных диапазонах.

Например, если у вас есть массив A = [0,6,5,2,2,5,1,9,4], и следующие размеры для подмассивов L = 1 и M = 2. Используя кумулятивную форму A, легко найти maxSum. Суммарное значение A будет A = [0,6,11,13,15,20,21,30,34].

Следующим шагом будет просто вычесть индексы, используя значения L и M. Например, если мы с i, мы можем просто получить A [i] - A [i + L], чтобы найти значение, соответствующее подмассиву с размером L, начиная с точки i. Если i = 5, чем i + L = 7, A [5] = 20 и A [7] = 30 , значение подмассива с размером L, начиная с точки i = 5, составляет 30–20, то есть 10. Таким образом, нам не нужно повторять итерацию более одного раза, чтобы суммировать значения и проверить, какое из них самое большое, мы можем просто использовать индексы для «сдвига» и вычитания из нашей текущей точки в основном цикле.

class Solution {
  public int maxSumTwoNoOverlap(int[] A, int L, int M) {
    // this loop will transform A into a cumulative Array
    for (int i = 1; i < A.length ; i++) {
        A[i] += A[i - 1];
    }
    int maxSum = A[L + M - 1];
    int maxLfirst = A[L - 1];
    int maxMfirst = A[M - 1];
    for (int i = L + M; i < A.length ; i++) {
        // here you can simply subtract the indexes values
        // A[i - M] is the subarray M value
        // A[i - M - L] is the subarray L value
        maxLfirst = Math.max(maxLfirst, A[i - M] - A[i - M - L]);
        // we have the same math that above, but if the M is first
        maxMfirst = Math.max(maxMfirst, A[i - L] - A[i - L - M]);
        // in the end of the iteration, we check which one is the biggest
        maxSum = Math.max(maxSum, Math.max(maxLfirst + A[i] - A[i - M], maxMfirst + A[i] - A[i - L]));
    }
    return maxSum;
  }
}

Очевидно, мы могли бы использовать рекурсивный подход и создать большой кеш для поиска максимальной суммы двух неперекрывающихся подмассивов, и, вероятно, мы найдем хороший ответ, но иногда с помощью нескольких математических методов мы иметь возможность решить проблему чистым способом и с гораздо большей производительностью.

Заключение

Цель этой статьи не в том, чтобы сказать, что мы всегда должны смотреть «математически» или что «математическое решение» будет лучше, чем обычный подход к программированию. Не поймите меня неправильно, моя цель - поговорить об этом и побудить других попробовать использовать математические концепции для решения повседневных задач. Может быть, мы поймем, что можно использовать математику для решения наших повседневных задач в гораздо большей степени, чем мы. считать.

Вот и все, ребята! Если у вас есть больше плюсов и минусов или что-то, о чем я здесь не упоминал, не стесняйтесь комментировать ниже!

Спасибо за чтение!

использованная литература

Https://leetcode.com/problems/maximum-subarray/