Цель
Мы хотим находить 
где:
И хочется это делать очень быстро, абсолютно точно и со всеми знаками.
Простой алгоритм
Заметим, чтобы найти число Читать полностью »
Рубрика «числа фибоначчи»
Вычисляем миллиардное число Фибоначчи менее чем за 7 секунд
2024-08-14 в 9:16, admin, рубрики: Алгоритмы, КодоБред, математика, оптимизация, оптимизация программ, числа фибоначчиНовый класс простых чисел, который я открыл случайно
2021-05-03 в 9:22, admin, рубрики: full reptend prime, математика, простые числа, системы счисления, теория чисел, циклические числа, числа фибоначчиВсем привет! Это мой первый пост на Хабре, потому я представлюсь: меня зовут Костя, я разработчик C++, немного музыкант, начинающий ML инженер и любитель математики. Как не сложно догадаться этот пост будет о моём математическом хобби.
Чётные числа Фибоначчи
2019-05-05 в 12:54, admin, рубрики: php, Алгоритмы, комментарии на хабре, математика, собеседование, числа фибоначчиНавеяно комментарием под постом Фибоначчи на собеседовании. Пользователь pavellyzhin упомянул следующую задачу на собеседовании (комментарий):
Больше года назад откликнулся на вакансию «php-программист», прислали ТЗ и там было задание с Фибоначчи: выбрать все четные числа Фибоначчи в диапазоне от 1 до 10000. Решил с помощью цикла(for). Еще там нужно было SQL-запрос составить на выборку ближайших дней рождений пользователей, что-то сверстать, точно не помню и какую-то функцию написать. Все сделал, отправил. Прислали ответ: «по итогам тестового задания Вы не приняты». Что конкретно им не понравилось так и не написали. Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел… :)
В данном посте я собираюсь показать как можно было решить эту задачу эффектно, а может даже и эффективно, но это не точно. Заодно продемонстрирую парочку из тысяч доказанных про числа Фибоначчи фактов.
Читать полностью »
Фибоначчи на собеседовании
2019-04-26 в 7:57, admin, рубрики: javascript, Алгоритмы, собеседование, числа фибоначчиВычисление ряда Фибоначчи — это классическая алгоритмическая задача, потому её нередко дают на собеседованиях, когда хотят проверить, что кандидат в принципе хоть как-то умеет в алгоритмы. Предположим, вы тот самый кандидат. Вам дали задание: на языке JavaScript написать функцию fib(n), возвращающую энное число Фибоначчи. Считаем, что нулевое число Фибоначчи — это нуль. Проверка корректности аргумента не требуется. Какие у вас есть варианты?
Короткое плечо совпадения
2017-12-08 в 7:01, admin, рубрики: математика, математические загадки, теория вероятностей, треугольные числа, факториал, числа каталана, числа фибоначчиДжеймс Тэнтон разбрасывается задачками по теории чисел с той же щедростью, с которой Джон Д. Рокфеллер раздавал десятицентовики. Я уже писал об одной из задач Тэнтона. Спустя несколько недель моё внимание привлёк этот твит о факториалах и квадратах и уже не давал мне покоя:
«4!+1 = 25, квадрат числа. 5!+1 = 121, тоже квадрат числа. Можете привести ещё один пример? Ещё два примера?»
С помощью ручки и бумаги легко показать, что 
не подходит. Факториал 
— это 
; прибавив 
, получим число 
, которое не является квадратом. (Оно раскладывается на множители как 
.) С другой стороны, 
равно 
, а прибавив 
, мы получим 
, что равно 
. Это даёт нам очень милое уравнение:
Читать полностью »
Как посчитать перестановки. Лекция в Яндексе
2016-10-01 в 11:09, admin, рубрики: Алгоритмы, Блог компании Яндекс, вычислительная математика, гипотезы, комбинаторика, математика, ненормальное программирование, перестановки, последовательности, сложные матзадачи, числа каталана, числа фибоначчиНекоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.
Под катом — подробная текстовая расшифровка и большинство слайдов.
Читать полностью »
Производящие функции — туда и обратно
2013-11-30 в 20:00, admin, рубрики: Алгоритмы, комбинаторика, математика, числа фибоначчи, метки: Алгоритмы, комбинаторика, математика, числа фибоначчи «Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много предметов, что могло бы оказаться затруднительным, мы собираем их вместе, и тогда нам нужно нести лишь один предмет — мешок».
Д. Пойа
Введение
Математика делится на два мира — дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций — мостика ведущего из дискретного мира в непрерывный, и наоборот.
Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, ..., gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа, который как мы все знаем очень большой.
Вышесказанное можно записать с помощью математических формул следующим образом: <g0, g1, g2, ..., gn> <=> g0 + g1z + g2z2 +… + gnzn +…. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.
Читать полностью »
Фракталы в простых числах
2013-09-22 в 20:03, admin, рубрики: Алгоритмы, интерференция, математика, ненормальное программирование, Теория Хаоса, фракталы, числа фибоначчи, метки: интерференция, Теория Хаоса, фракталы, числа фибоначчи 
Я обнаружил этот фрактал, когда разглядывал интерференцию волн на поверхности речки. Волна движется к берегу, отражается и накладывается сама на себя. Есть ли порядок в тех узорах, которые создаются волнами? Попробуем найти его. Рассмотрим не всю волну, а только вектор ее движения. «Берега» сделаем гладкими, для простоты эксперимента.
Эксперимент можно провести на обычном листке в клеточку из школьной тетради.
Читать полностью »
Числа в себе
2013-06-12 в 10:39, admin, рубрики: математика, Песочница, числа фибоначчи, метки: числа фибоначчиМое хобби – преподавание математики и информатики школьникам. В этом процессе очень важным является вопрос мотивации, поэтому приходится очень тщательно подходить к качеству подачи материала. После перебора различных методов чтения материала, родилась идея проекта «Одна задача», в котором на примере решения всего одной задачи читается лекция с подачей разнообразного нового материала. Итак, демонстрирую первый материал данного проекта.
Задача: имеются плитки размером 1х1 и 1х2 метра. Сколько существует способов замощения этими плитками прямоугольника 1х15 метров?
Читать полностью »
Сравнение алгоритмов вычисления чисел Фибоначчи
2012-07-29 в 8:28, admin, рубрики: Алгоритмы, числа фибоначчи, метки: числа фибоначчи В комментариях к статьям N-е число Фибоначчи за O(log N) и Еще один алгоритм вычисления чисел Фибоначчи указывалось на тот факт, что уже 100-е число Фибоначчи не помещается в 4 байта, а в «длинной» арифметике скорость выполнения умножения резко просядет. Более того, были предположения, что примитивное сложение может оказаться быстрее. Я решил сравнить 2 алгоритма — простое сложение и алгоритм с логарифмическим количеством операций — и написал тестовую программу на С. Для «длинной» арифметики использовал библиотеку GMP.
Читать полностью »