КОДЕКС
Практика алгоритмов с математическими головоломками, часть 2
Здравствуйте, я объясню два алгоритма, чтобы найти k-е четное и k-е нечетное числа в ряду Фибоначчи.
Если вы не слышали об этом, ряд Фибоначчи таков:
Его четные элементы - 2, 8, 34 и так далее. Первый способ, который приходит на ум, - это сгенерировать серию с помощью цикла for и отслеживать четные числа по мере продвижения, и как только мы дойдем до k-го четного числа, мы выйдем и вернем его.
Но если вы обратите внимание на четные числа рядов Фибоначчи и немного поиграете с ними, вы заметите, что есть формула для их генерации:
Таким образом, нам не нужны все предыдущие числа ряда Фибоначчи до того момента, когда мы хотим найти n-е четное число. Следующая функция следует за изображением 2 и возвращает то, что мы хотим.
В строке 3 «elif» эквивалентно «else if» в Python.
Мы отслеживаем два предыдущих элемента, обновляя переменные a и b и используя их для генерации следующего значения в серии на изображении 2.
Теперь давайте посмотрим, как эффективно найти k-е нечетное число в ряду Фибоначчи. Этот сложнее и круче. Если мы вычеркнем эти нечетные числа и обратим внимание, мы обнаружим закономерность. На следующем изображении показан этот процесс. Порядок означает их относительный порядок относительно друг друга и равен k, поэтому порядок 3 на изображении 3 означает третье нечетное число (k = 3) в ряду Фибоначчи. Формулы те же, но стартовые пары разные.
При нахождении k-го нечетного числа ряда Фибоначчи, если k нечетное, мы рассматриваем оранжевый и должны найти число с индексом (k // 2) в оранжевом серия. Если k четное, мы рассматриваем зеленый и должны найти число с индексом ((k / 2) -1) в зеленой серии. Таким образом, нам просто нужны зеленые или оранжевые числа ряда Фибоначчи до этой точки, и это значительно сокращает время выполнения, когда заданное k велико.
Вот его код:
В строке 2 функция вызывает ошибку, если ввод не является целым числом.
Спасибо за прочтение.
Это ссылка на предыдущую часть:
