Возведение в целую степень

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

Приведена реализация модулярного возведения в степень на  С++  с предотвращением переполнения.

Дан краткий обзор материалов по множественному возведению в степень, описаны некоторые приложения темы в олимпиадных задачах.

Описан тест простоты Ферма и основанный на нём эффективный тест простоты для чисел, не превосходящих  [latex] {10}^{21} [/latex].

Прелюдия
Наивный алгоритм
Быстрый рекурсивный алгоритм
Бинарный алгоритм
Множественное возведение в степень
Модулярное возведение в степень
Применение в олимпиадных задачах
Тест простоты Ферма
Протокол Диффи-Хеллмана
Вустянюк Ігор Дмитрович
Вустянюк Ігор Дмитрович

Latest posts by Вустянюк Ігор Дмитрович (see all)

6 thoughts on “Возведение в целую степень

  1. Очень интересная и полезная публикация.
    Её (как Вы пишите — «вдруг») прочло довольно много людей. В том числе и я.
    — «Применение в олимпиадных задачах» и «Протокол Диффи-Хеллмана» — ошибки в записи формул.
    — Во многих разделах код на Питоне. Мотивируйте.
    — Три последних раздела без кода. Последний понятно почему. Остальные два легко можно сопроводить кодом.
    — Добавьте, пожалуйста, ключевые слова (tags), Чтобы ещё больше людей нашли и прочли Вашу работу.

    • Спасибо за замечания. Постарался всё исправить.

      Так и не понял, в чём были ошибки — вроде бы набрал точно тот же код LaTeX. Но теперь отображается нормально.

      Я с самого начала выбрал Питон для иллюстрации алгоритмов и описал причины в разделе «Прелюдия». Основные коды приведены на С++.

      Добавлены коды решений в предпоследние два раздела. Поскольку решения громоздкие, я добавил ссылки на Ideone. Решения на С++.

      Теги добавлены.

  2. Отличная идея. Вот только не видно дополнительных вкладок. Текст в них совпадает с текстом фона.
    Я попробовал погуглить, как это исправить:
    https://wordpress.org/support/topic/plugin-shortcodes-ultimate-tabtabs-function
    https://wordpress.org/support/topic/plugin-shortcodes-ultimate-can-we-style-tab-titles
    но там предлагают обратиться к настройкам, к которым у меня нет доступа

Добавить комментарий