Вчера нашел хорошую задачу на codewars.com. для тех из вас, кто не знает, кодеры — это платформа для тренировки ваших навыков программирования, решения проблем программирования с использованием какого-то другого языка программирования. Это хорошее упражнение для тех из вас, кто мечтал стать инженером-программистом.

Ладно, вернемся к нашему основному разговору. Найденный мною кодовый вызов (кодовые войны называют его «ката») называется «Ряд нечетного треугольника».



Ряд нечетного треугольника
Codewars — это место, где разработчики достигают мастерства в написании кода, преодолевая трудности. Тренируйтесь ката в додзё и достигните своих высот…www.codewars.com



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

Задача состоит в том, что нас просят узнать строку треугольника, если известен индекс (в этой задаче индекс треугольника начинается с 1, а не с 0). предположим, что нам дан индекс = 1. тогда мы должны произвести вывод [1]. если нам дан index = 2, то мы должны произвести вывод [3, 5] и т. д. (пожалуйста, прочитайте инструкции к вопросу более подробно по ссылке выше). примерно так работает наш код:

odd_row(1)  ==  [1]
odd_row(2)  ==  [3, 5]
odd_row(3)  ==  [7, 9, 11]

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

Если вы внимательно посмотрите, то заметите, что длина строки в треугольнике равна индексу этой строки. например, длина 3-й строки равна 3, как и остальных строк. количество элементов 7-й строки равно 7, количество элементов 8-й строки равно 8, количество элементов 9-й строки равно 9 и так далее.

Давайте сначала сохраним эту информацию. что нам нужно сделать сейчас, так это сгенерировать нечетные числа, которые будут помещены в треугольник выше. Как генерировать нечетные числа? это легко. если мы начнем считать последовательно с единицы и добавим к ней 2, то каждое полученное число будет нечетным. таким образом мы можем произвести числа 1, 3, 5, 7, 9,… и так далее. Другой факт заключается в том, что разница между последним элементом в n-й строке и первым элементом (n+1)-й строки равна 2. например, разница между последним элементом во 2-й строке и первым элементом 3 ряд 2.

отсюда мы можем получить 2 важные части информации:

  1. расстояние между ближайшими элементами в одной строке равно 2.
  2. расстояние между последним элементом строки и первым элементом следующей строки равно 2. Другими словами, расстояние между последним элементом n-й строки и первым элементом строки n+1 равно 2.

Итак, если мы хотим сгенерировать список/массив, содержащий нечетные числа, нам просто нужно несколько раз выполнить операцию сложения между числами 1 и 2. Если мы хотим сгенерировать первые 3 нечетных числа, то это реализация алгоритма с использованием python:

row = []
a = 1
for i range(3):
   row = row + [a]
   a = a + 2
print(row)

Теперь вопрос в том, как нам сделать треугольник, подобный задаче, описанной выше?

процесс, который нам нужно сделать, аналогичен процессу выше. нам нужно создать список/массив, содержащий нечетные числа, и мы применяем этот процесс ко всем строкам в треугольнике, используя цикл for. разница в том, что в этом случае мы должны снова установить значение row_temp в пустой список/массив каждый раз, когда процесс генерации нечетных чисел завершается в строке. это нужно сделать, чтобы значение в предыдущей строке не было в текущей строке. если мы этого не сделаем, то треугольник, который мы создадим, будет таким:

[1]
[[1], [3], [5]]
[[1], [3], [5], [7], [9], [11], [13]]

в этом процессе мы используем 2 раза циклический процесс с использованием for loop . в первом процессе мы зацикливаем столько значений, сколько задано задачей индекса (назовем его n), поэтому мы можем записать его как for i in range(n+1). тогда как во втором процессе мы зацикливаемся i раз, где i указывает, в какой строке мы находимся. Проще говоря, в этом алгоритме мы хотим указать, что для i-й строки длина строки также должна быть i . Мы делаем этот шаг в соответствии с информацией, которую мы получили в начале этой статьи. Если мы применим вышеуказанный алгоритм с использованием python, мы найдем следующее решение:

row = []
row_temp = []

a = 1
for i in range(n+1): # n is the index of row
    row_temp = []
    for j in range(i):
        row_temp = row_temp + [a]
        a = a + 2
    print(row_temp)
    row = row + [row_temp]
print(row)

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

Те из вас, кто хорошо знаком с алгоритмами и структурами данных, могут быть знакомы с термином нотация big-O. Это обозначение показывает временную сложность алгоритма. с точки зрения временной сложности нотация Big-O показывает, насколько сильно размер входных данных влияет на скорость нашего алгоритма. Обозначение Big-O для алгоритма, которое я написал выше, равно O (n²). то есть по мере увеличения размера входных данных время, необходимое для этого алгоритма, увеличивается квадратично. это эффект вложенного цикла, который мы делаем в приведенном выше алгоритме (возможно, я подробно расскажу об этом в следующей статье).

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

Лучшее решение

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

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

Чтобы решить эту проблему, все, что нам нужно сделать, это найти способ подсчитать первый элемент в каждой строке треугольника. почему нам нужен только первый элемент? зная первый элемент в строке, мы можем узнать остальные элементы, прибавив число 2. например, мы знаем, что первый элемент в третьей строке равен 7. из предыдущего описания мы также знаем, что элементов много в третьей строке — 3. Следовательно, элементы в третьей строке — 7, 7+2, 7+2+2 или 7, 9, 11. Другой пример — 5-й ряд. первый элемент 5-й строки равен 21. поскольку в 5-й строке 5 элементов, то все элементы 5-й строки равны 21, 21+2, 21+2+2, 21+2+2+2, 21+ 2+2+2+2 или 21, 23, 25, 27, 29 . Итак, если мы уже знаем первый элемент ряда треугольников, то нам нетрудно узнать и остальные элементы этого ряда. просто, правда?

Вывод формулы

Давайте взглянем на иллюстрацию ниже:

Основываясь на приведенной выше иллюстрации, мы поймем следующее:

  1. в первой строке только 1 элемент, который равен 1.
  2. первый элемент во 2-й строке равен 1+2 = 3 (к последнему элементу первой строки добавляется 2)
  3. первый элемент 3-й строки равен 5+2 = 7 (последний элемент 2-й строки — это 5 — плюс 2)
  4. первый элемент 4-й строки равен 13+2 = 15 (последний элемент 3-й строки — это 13 — плюс 2)

если мы представим первый элемент n-й строки как a_n и последний элемент n-й строки как z_n, то, следуя приведенному выше шаблону, мы можем найти, что:

поскольку каждое расстояние между ближайшими элементами в строке равно 2, а длина n-й строки равна n, тогда:

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

применяя те же правила, мы можем получить следующую формулу:

это как рекурсивная функция. это легко, не так ли?

Теперь нам нужно расположить приведенную выше формулу так, чтобы она образовывала функцию a_n, которая зависит только от независимой переменной n.

из старших классов вы знаете, что 1+2+3+4+…+n равно n*(n+1)/2. тогда в этом случае сумма указанных выше членов равна n*(n-1)/2.

Хорошо, это последняя формула, которая у нас есть. с помощью этой формулы мы можем найти первый элемент каждой строки в треугольнике. например, первый элемент первой строки (a_1) равен 1+1*(1–1) = 1. первый элемент второй строки равен 1+2*(2–1) = 3. первый элемент третья строка 1 + 3 * (3–1) = 7 и так далее.

Определите другой элемент строки

как я упоминал ранее, с помощью приведенной выше формулы мы также можем узнать другие элементы в связанной строке. Но как? ну а вы еще помните картинку ниже?

На картинке выше показано, что расстояние между двумя ближайшими элементами в ряду равно 2. Поскольку мы знаем первый элемент, с помощью этой концепции мы также можем определить второй, третий и так далее. предположим, что первым элементом строки является b, затем вторым элементом является b+2, третьим элементом является b+2+2, четвертым элементом является b+2+2+2 и так далее. Итак, в целом мы можем заключить, что каждый элемент строки в приведенном выше треугольнике может быть выражен как:

однако, поскольку система индексации в большинстве языков программирования (включая java и python) начинается с 0, приведенную выше формулу необходимо изменить на:

Теперь все будет легко!

поверьте, единственная трудность в этой задаче - найти формулу выше. если вы нашли формулу выше, вы должны быть счастливы, потому что эта проблема будет намного проще.

Java-реализация

когда вы открываете эту проблемную страницу в codewars и выбираете Java в качестве своего языка, вам будет предоставлен следующий шаблон кода:

public class UserSolution {
  public static long[] oddRow(int n) {
  
    return ;
  }
}

теперь мы можем реализовать формулу раньше. как я упоминал в начале, n-я строка содержит n элементов. мы можем создать массив, представляющий эту строку, набрав long[] result = new long[n]; . Затем мы можем присвоить правильные значения каждому элементу в этой строке, используя приведенную выше формулу. вот реализация:

public class UserSolution {
  public static long[] oddRow(int n) {
    long[] result = new long[n];
    for (int i=0;i<n;i++) {
      result[i] = (long) n*n-n+1 + 2*i;
    }
    return result;
  }
}

видите, даже при использовании языка Java, известного своим сложным синтаксисом, нам нужно добавить всего 3 строки кода. Этот метод намного эффективнее предыдущего. более эффективным с точки зрения синтаксиса, а также более эффективным с точки зрения временной сложности.

Реализация Python

когда вы откроете эту проблемную страницу в codewars и выберете python в качестве языка, вы увидите следующий шаблон кода:

def odd_row(n):
    return

мы можем реализовать тот же метод, используя язык python, но с немного другим синтаксисом. Поскольку мы используем python, известный своей простотой синтаксиса, мы можем представить строки в треугольнике как массив (список python), набрав result = [] . затем мы можем использовать приведенную выше формулу для обработки присвоения каждому элементу в результирующем массиве. Вот реализация:

def odd_row(n):
    result = []
    for i in range(0,n):
        result.append(n*n-n+1 + 2*i)
    return result

на самом деле, если вы посмотрите на решения других участников, вы найдете еще более блестящие решения:

odd_row = lambda n:list(range(n*(n-1)+1,n*(n+1),2))

да, всего 1 строчка кода! Используя математику, мы можем сэкономить несколько строк кода и повысить эффективность программы. Говоря об эффективности, как насчет временной сложности приведенного выше алгоритма? поскольку мы делаем for loop только один раз, временная сложность вышеуказанного алгоритма составляет O (n). намного лучше правда?