В этой публикации началось рассмотрение интересной задачки — отношения соседних чисел в обобщенном ряду Фибоначчи (в котором каждый следующий член оказывается равен сумме $inline$k$inline$ предыдущих.
К сожалению, задачка не была доведена до логического окончания, и брошена при неполном ответе для случаев 3 и 4.
Просто чтобы закрыть тему, рассмотрим ряд, образованный рекуррентным соотношением
$$display$$f_n= sum_{i=n-k-1}^{n-1}f_i$$display$$
«Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много предметов, что могло бы оказаться затруднительным, мы собираем их вместе, и тогда нам нужно нести лишь один предмет — мешок».
Д. Пойа
Математика делится на два мира — дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций — мостика ведущего из дискретного мира в непрерывный, и наоборот.
Идея производящих функций достаточно проста: сопоставим некоторой последовательности <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.
Читать полностью »
Перед прочтением статьи, решил попробовать придумать свой алгоритм. Времени понадобилось не очень много. Ниже описание идеи и пример на С++.
Читать полностью »
Читая статью об устройстве на работу в ABBYY, встретил в ней упоминание задачи:
быстро – за O( log N ) арифметических операций над числами – найти N-е число Фибоначчи
Я задумался над ней и понял, что сходу в голову приходят только решения, работающие за время O(N). Однако позже решение было найдено.
Читать полностью »
На хабе появилось несколько топиков об «однострочниках» на разных языках, которые решали простые задачи. Я решил опубликовать несколько алгоритмов на языке С++.
Итак, поехали!
Читать полностью »
