Дата публикации Mar 27, 2017
Я работаю на полную ставку, начинаю работать уже 5 лет. Очень удачно присоединиться к миру разработки программного обеспечения. У меня есть шансы изучать новые вещи каждый день. Я создал много работающих приложений (раньше я в основном разработчик для iOS), многие рабочие коды RoR, React, Elixir работают. Кажется, все в порядке. Но однажды я просто глубоко осознал, что что-то упустил, чтобы поднять свою работу на новый уровень. Поэтому я оглядываюсь назад на основы и вижу термины «Алгоритмы и структуры данных», которые повторяются. Изучив свои знания, я решил не спеша изучать алгоритмы и структуры данных.
К счастью, мир полон открытых возможностей для ученика.Courseraприносит удивительные лекции от ведущих университетов мира для людей, желающих учиться. Конечно, «Структуры данных и алгоритмыСпециализация 6 курсов Университета Калифорнии, Сан-Диего, Высшая школа экономики выделяется из толпы. Мой друг в середине курсов и очень рекомендую мне.
Эта серия блогов - лекционные заметки, в том числе мои мысли и практики, основанные на материалах этих курсов. Он также содержит некоторые подсказки о проблемах, которые я решил. Если у вас есть какие-либо вопросы или комментарии, не стесняйтесь оставлять их здесь илиGitHub, Я готов учиться вместе. Я делаю эти заметки, чтобы помочь мне пересмотреть. Я надеюсь, что это тоже поможет вам, поэтому я делаю это публично. Давай прыгнем в бассейн!
Проблема 1: Максимальный парный продукт.
Решение:
Нам просто нужно умножить 2 самых больших числа.
Проблема 2: Великий общий разработчик (GCD)
Наибольший общий делитель GCD (a, b) двух неотрицательных целых чисел a и b (которые не равны 0) - это наибольшее целое число d, которое делит и a, и b.
Ваша цель в этой задаче - реализовать евклидов алгоритм для вычисления наибольшего общего делителя. Эффективный алгоритм вычисления наибольшего общего делителя является важным базовым примитивом широко используемых криптографических алгоритмов, таких как RSA.
Решение:
Проблема 3: наименьшее общее кратное
Наименьшее общее кратное двух положительных целых чисел a и b является наименьшим положительным целым числом m, которое делится на a и b.
Решение:
Если вы знаете LCM (a, b). GCD (a, b) = ab, алгоритм для этой задачи будет легко написать, если использовать последний алгоритм GCD.
Примечание:используйте // в python, чтобы получить правильное разделение на большое число в Python3.
Задача 4: число Фибоначчи
Определение последовательности Фибоначчи:
Решение:
Легко реализовать наивный рекурсивный алгоритм для вычисления чисел Фибоначчи.
Но время выполнения не хорошо. Вы можете попытаться вычислитьF40, это займет заметное время.
Нам нужно ускорить способ вычисления фибоначчи.
Упражнение 1:Используйте индукцию, чтобы доказать, что Fn ≥ 2 ^ (0.5n) при n ≥ 6.
Доказательство:
Упражнение 2:Найдите постоянную c <1 такую, что Fn ≤ 2 ^ cn для всех n ≥ 0. Покажите, что ваш ответ правильный.
Доказательство:
Задача 5: последняя цифра большого числа Фибоначчи
Найти последнюю цифру n-го числа Фибоначчи. Напомним, что числа Фибоначчи растут экспоненциально быстро. Например,
F200 = 280571172992510140037611932413038677189525.
Решение:
Поскольку он растет экспоненциально быстро, мы не можем использовать fast_fibonacci (n)% 10, чтобы дать ответ. Нам нужен другой подход к этому делу. Вместо суммирования Fn-1 + Fn-2 мы просто суммируем последнюю цифру Fn-1 и последнюю цифру Fn-2.
Усовершенствованная задача 6: Огромное число Фибоначчи по модулю m
Нахождение Fn по модулю m, где n может быть действительно огромным: до 1018. При таких значениях n алгоритм зацикливания для n итераций наверняка не поместится ни в одну секунду. Поэтому нам нужно избегать такой петли. Чтобы получить представление о том, как решить эту проблему, не пройдя все Fi для i от 0 до n, давайте посмотрим, что происходит, когда m мало, скажем, m = 2 или m = 3.
Так что можно наблюдать, что у него есть период. Режим Fn 2 имеет период 011 с длиной 3, режим 3 Fn имеет период 01120221 с длиной 8. Поэтому, чтобы вычислить, скажем, F2016 mod 3, нам просто нужно найти остаток 2016 года при делении на 8. С 2016 года = 251,8 + 8. Мы заключаем, что F2016 mod 3 = F8 mod 3 = 0.
В общем случае это верно: для любого целого числа m> = 2 последовательность Fn mod m является периодической. Период всегда начинается с 01 и известен какПизанский период,
Решение:
Исходя из этого предположения, мы обнаруживаем период Пизано, проверяя его повторение на 01 и сохраняя повторение других чисел в таблице Пизано. Итак, мы проверяем
pisano_table [half_size] == 0 и
pisano_table [half_size + 1] == 1 и
pisano_table [0: half_size] == pisano_table [half_size: size]
Алгоритм работает правильно и дает нам правильный ответ для небольшого числа При большом количестве таблица Пизано имеет очень большой размер, для вычисления и определения периода Пизано требуется время. Сократить время для вычисления, мы просто проверяем период с повторяющимися числами 01 и 10 (другое число в порядке). Это сэкономит время на обнаружение таблицы Пизано для больших вычислений Фибоначчи.
Сложная задача 7: сумма чисел Фибоначчи
Нахождение последней цифры суммы первых n чисел Фибоначчи (Найти последнюю цифру F0 + F1 +… + Fn)
Решение:
С помощью периода Пизано мы можем легко вычислить последнюю цифру любого Fi. У нас есть F0 + F1 +… + Fn = F (n + 2) - 1. Алгоритм будет легко реализовать:
Трюк плюс 10 здесь, чтобы убедиться, что мы возвращаем положительный остаток в случае, если get_fibonacci_huge (n + 2, 10) имеет последнюю цифру 0.
Расширенная задача 8: Частичная сумма чисел Фибоначчи.
Нахождение последней цифры частичной суммы чисел Фибоначчи: Fm + Fm + 1 + · · · + Fn.
Решение:
Если мы придумаем Fm + Fm + 1 +… + Fn = F (n + 2) - F (m + 1). Это будет легко реализовать решение
Примечание:Мы просто берем последнюю цифру F (n + 2) + 10 и минус последнюю цифру F (m + 1), чтобы получить цифру.
Пример: F (n + 2) = abc12, F (m + 1) = def37, поэтому чтобы получить правильную последнюю цифру, мы должны сделать: (2 + 10–7)% 10
Sidenote: Если вам нравится этот пост, вам понравится:https://www.coursera.org/learn/fibonacci/home/info, Я люблю лекции о: бамбазлемент Фибоначчи
Ресурсы:
Наибольший общий делитель: раздел 1.2.3 [DPV08], раздел 31.2 [CLRS]
Вычисление чисел Фибоначчи: раздел 0.2 из [DPV08]
Свойства чисел Фибоначчи: упражнения 0.2–0.4 в [DPV08]
Ссылки:
© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map