Курс 1 - Алгоритмический инструментарий. Часть 1. Введение

Я работаю на полную ставку, начинаю работать уже 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]

Ссылки:

[DPV]Санджой Дасгупта, Христос Пападимитриу и Умеш Вазирани. Алгоритмы (1-е издание). Макгроу-Хилл Высшее образование. 2008.

[CLRS]Томас Х. Кормен, Чарльз Лейзерсон, Рональд Л. Ривест, Клиффорд Стейн. Введение в алгоритмы (3-е издание). MIT Press и McGraw-Hill. 2009.

Оригинальная статья