Шесть недель в качестве студента буткемпа по программированию в школе Flatiron, я могу честно сказать, что учился (и понимаю, потому что эти две вещи могут быть очень разными) больше, чем целый год в университете. Отчасти это потому, что я люблю эту тему, но многое можно отнести и к окружающей среде. Здесь, в школе Flatiron, они действительно подчеркивают тот факт, что есть более чем один способ сделать что-то. Это научило меня быть подозрительным, и каждый раз, когда я сталкиваюсь с проблемой, я думаю про себя «есть ли лучший способ сделать это» и не успокаиваюсь, пока не нахожу около 4 способов что-то решить.
Недавно я прочитал статью, в которой говорилось, что основное различие между выпускниками буткемпа и специалистами по компьютерным наукам заключается не в том, что последние намного лучше программируются, а в том, что они лучше понимают и улучшают алгоритмы. В результате я решил узнать об алгоритмах как можно больше, пока я учусь на буткемпе.
Так что же такое алгоритм?
Алгоритм — это процесс или набор правил, которым необходимо следовать при вычислениях или других операциях по решению задач, особенно с помощью компьютера. По сути, вы получаете проблему и каждый раз выполняете набор шагов для ее решения. Простой пример (который вы, вероятно, делаете, не осознавая) — вычисление числа, кратного 3, которое меньше 20. Вы, вероятно, знаете, что это 6, ныряя 20 на 3 и округляя в меньшую сторону. Технический способ решить эту проблему состоит в том, чтобы сосчитать числа от 1 до 19 и посмотреть, делится ли каждое число на 3. Это гораздо менее эффективно и займет гораздо больше времени, если вы делаете это с потолком, скажем, в 1000. Вместо этого, наша голова создает алгоритм решения такой проблемы, не делая явным образом того, чего от вас ожидает задача. В коде это изображается так:
def explicit_way
number_of_multiples_of_three = 0
(1..20).each do |number|
if number % 3 == 0
number_of_multiples_of_three += 1
end
end
end
def algorithm_way
(20 / 3).round
end
Никто не любит математику…
…Кроме меня. Признаюсь, я помешан на математике. Я люблю все, что связано с цифрами. Считая их, вычисляя их, используя их в сложных формулах для решения задач. Так что решение задач Эйлера в проекте, наверное, моя любимая вещь в коде. Он сочетает в себе оба моих интереса к математике и программированию. Это также помогает мне практиковаться в создании алгоритмов для решения проблем, а не просто перебирать их, когда языки кодирования выполняют всю работу. Возьмем, к примеру, эту проблему
Палиндромное число одинаково читается в обоих случаях. Например,
101является палиндромом, как и91,519и1,111.
Например, самый большой палиндром, составленный из произведения двух двузначных чисел, равен 9009:
Ваша цель — найти самый большой палиндром, составленный из произведения двух трехзначных чисел.
Вы могли бы использовать грубую силу, как это
def largest_palindrome_product
a = 999
b = 999
max_palindrome = 1
while a > 0
b = 999
while b > 0
product = a * b
if product.to_s == product.to_s.reverse
max_palindrome = product if product > max_palindrome
end
b -= 1
end
a -= 1
end
max_palindrome
end
который, вероятно, является первым мыслительным процессом каждого в том, как его решить. Когда я увидел эту задачу, этот способ определенно всплыл в моей голове, но я не удосужился попробовать решить ее таким образом. Я знал, что должен быть лучший способ, более быстрый способ и способ, который можно обобщить для работы с более чем трехзначными числами. Я придумал:
def largest_palindrome(digits)
number = 10 ** digits.to_i
[lap_nine(number), lap_three(number), lap_seven(number)].max
end
def lap_nine(number)
first_palindrome(number - 1, number - 9)
end
def lap_three(number)
first_palindrome(number - 7, number - 7)
end
def lap_seven(number)
first_palindrome(number - 3, number - 3)
end
def first_palindrome(number_one, number_two)
answer = 0
while answer < 1
counter = 0
while counter < 10 && answer < 1
product = number_one * (number_two - (counter*10))
counter += 1
answer = product if product == product.to_s.reverse.to_i
end
number_one -= 10
end
answer
end
Это не чистый алгоритм, он по-прежнему полагается на Ruby для выполнения некоторых проверок условий, но он пытается ограничить большую часть посторонней активности. Таким образом, вы можете ввести, сколько цифр вы хотите в двух числах, которые вы хотите умножить. Это работает с любым количеством цифр от 1 до бесконечности. Кроме того, это быстрее. Мы можем использовать модуль Benchmark (см. мой последний пост в блоге: https://medium.com/@jkhoang313/ruby-how-fast-is-your-method-4fd82356360c) для сравнения. Я назвал свой метод, чтобы выяснить ответы для 2-х, 3-х, 4-х, 5-ти и 6-значных чисел и обозначил его как количество цифр, и я назвал метод грубой силы Дэйв (без причины), и вы можете сравнить.
Benchmark.bm(10) do |x|
x.report("2") {print largest_palindrome(2)}
x.report("3") {print largest_palindrome(3)}
x.report("Dave") {print largest_palindrome_product}
x.report("4") {print largest_palindrome(4)}
x.report("5") {print largest_palindrome(5)}
x.report("6") {print largest_palindrome(6)}
end
и вы получаете…
user system total real 2 9009 0.000000 0.000000 0.000000 ( 0.000063) 3 906609 0.000000 0.000000 0.000000 ( 0.001722) Dave 906609 0.470000 0.000000 0.470000 ( 0.471083) 4 99000099 0.000000 0.000000 0.000000 ( 0.000680) 5 9893443989 0.050000 0.000000 0.050000 ( 0.049227) 6 991080080199 0.060000 0.000000 0.060000 ( 0.065631)
Вы можете видеть, что алгоритм занимает все больше времени, чем больше цифр вы хотите найти, но даже до 6 цифр он намного быстрее, чем метод грубой силы с поиском только 3 цифр.
