Рубрика «числа фибоначчи»

Всем привет! Это мой первый пост на Хабре, потому я представлюсь: меня зовут Костя, я разработчик C++, немного музыкант, начинающий ML инженер и любитель математики. Как не сложно догадаться этот пост будет о моём математическом хобби.

Читать полностью »

Навеяно комментарием под постом Фибоначчи на собеседовании. Пользователь pavellyzhin упомянул следующую задачу на собеседовании (комментарий):

Больше года назад откликнулся на вакансию «php-программист», прислали ТЗ и там было задание с Фибоначчи: выбрать все четные числа Фибоначчи в диапазоне от 1 до 10000. Решил с помощью цикла(for). Еще там нужно было SQL-запрос составить на выборку ближайших дней рождений пользователей, что-то сверстать, точно не помню и какую-то функцию написать. Все сделал, отправил. Прислали ответ: «по итогам тестового задания Вы не приняты». Что конкретно им не понравилось так и не написали. Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел… :)

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

Вычисление ряда Фибоначчи — это классическая алгоритмическая задача, потому её нередко дают на собеседованиях, когда хотят проверить, что кандидат в принципе хоть как-то умеет в алгоритмы. Предположим, вы тот самый кандидат. Вам дали задание: на языке JavaScript написать функцию fib(n), возвращающую энное число Фибоначчи. Считаем, что нулевое число Фибоначчи — это нуль. Проверка корректности аргумента не требуется. Какие у вас есть варианты?

image
Читать полностью »

Джеймс Тэнтон разбрасывается задачками по теории чисел с той же щедростью, с которой Джон Д. Рокфеллер раздавал десятицентовики. Я уже писал об одной из задач Тэнтона. Спустя несколько недель моё внимание привлёк этот твит о факториалах и квадратах и уже не давал мне покоя:

Tweet reads: 4!+1=25, a square number. 5!+1=121, a square number. Another example? Two more examples?

«4!+1 = 25, квадрат числа. 5!+1 = 121, тоже квадрат числа. Можете привести ещё один пример? Ещё два примера?»

С помощью ручки и бумаги легко показать, что $6!$ не подходит. Факториал $6!$ — это $1 times 2 times 3 times 4 times 5 times 6=720$; прибавив $1$, получим число $721$, которое не является квадратом. (Оно раскладывается на множители как $7 times 103$.) С другой стороны, $7!$ равно $5040$, а прибавив $1$, мы получим $5041$, что равно $71^2$. Это даёт нам очень милое уравнение:
Читать полностью »

Некоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.

Под катом — подробная текстовая расшифровка и большинство слайдов.
Читать полностью »

«Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много предметов, что могло бы оказаться затруднительным, мы собираем их вместе, и тогда нам нужно нести лишь один предмет — мешок».
                                                                                                                                                               Д. Пойа

Введение

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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, ..., gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа, который как мы все знаем очень большой.

Вышесказанное можно записать с помощью математических формул следующим образом: <g0, g1, g2, ..., gn> <=> g0 + g1z + g2z2 +… + gnzn +…. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.
Читать полностью »

Фракталы в простых числах

Я обнаружил этот фрактал, когда разглядывал интерференцию волн на поверхности речки. Волна движется к берегу, отражается и накладывается сама на себя. Есть ли порядок в тех узорах, которые создаются волнами? Попробуем найти его. Рассмотрим не всю волну, а только вектор ее движения. «Берега» сделаем гладкими, для простоты эксперимента.

Эксперимент можно провести на обычном листке в клеточку из школьной тетради.
Читать полностью »

Мое хобби – преподавание математики и информатики школьникам. В этом процессе очень важным является вопрос мотивации, поэтому приходится очень тщательно подходить к качеству подачи материала. После перебора различных методов чтения материала, родилась идея проекта «Одна задача», в котором на примере решения всего одной задачи читается лекция с подачей разнообразного нового материала. Итак, демонстрирую первый материал данного проекта.

Задача: имеются плитки размером 1х1 и 1х2 метра. Сколько существует способов замощения этими плитками прямоугольника 1х15 метров?
Читать полностью »

В комментариях к статьям N-е число Фибоначчи за O(log N) и Еще один алгоритм вычисления чисел Фибоначчи указывалось на тот факт, что уже 100-е число Фибоначчи не помещается в 4 байта, а в «длинной» арифметике скорость выполнения умножения резко просядет. Более того, были предположения, что примитивное сложение может оказаться быстрее. Я решил сравнить 2 алгоритма — простое сложение и алгоритм с логарифмическим количеством операций — и написал тестовую программу на С. Для «длинной» арифметики использовал библиотеку GMP.
Читать полностью »

Перед прочтением статьи, решил попробовать придумать свой алгоритм. Времени понадобилось не очень много. Ниже описание идеи и пример на С++.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js