Triangle Quest

Разберём две математические задачи с Hackerrank: Triangle Quest и Triangle Quest 2.

Дано число от 1 до 9 и нужно вывести треугольники из чисел заданного вида. Для числа 4 в первой задаче:

а во второй:

Для вывода допустимо использовать только один цикл, процедуру print и математические операции:

Читать далее Triangle Quest

Генерация всех подмножеств с помощью двоичного представления числа

Другой варианта алгоритма генерации всех подмножеств. Сначала пример.

Дано множество из 5 элементов.

Возьмём пятизначное двоичное число и поставим в соответствие каждой цифре этого числа один из элементов исходного множества. Таким способом мы можем задавать подмножества исходного пятиэелементного множества.

Читать далее Генерация всех подмножеств с помощью двоичного представления числа

Алгоритм генерации всех подмножеств

Алгоритм взят из книги Теоретический минимум по Computer Science (Лабиринт, ЛитРес). Алгоритм итеративный и очень простой для понимания.

На изображении пример работы алгоритма для множества [1, 2, 3].

Генерация всех подмножеств

Каждый элемент исходного множества увеличивает результирующее множества в 2 раза. В итоге множество всех подмножеств будет содержать \(2^n\) элементов, где n — количество элементов исходного множества.

Пример на Python:

Оптимизация условий с помощью оператора xor

Вместо

можно записать

Перебор соседних клеток на двухмерном поле

Рассмотрим задачу похожую на игру Сапёр

Дано прямоугольное поле размером n на m. В поле каждая клетка обозначена либо символом точки ('.') точкой либо звёздочки ('*'). Точка означает пустое поле поле, звёздочка мину. Вывести на экран поле такого же размера где вместо точек указанна цифра - количество мин рядом с этой клеткой.

Далее описан способ перебора соседних клеток у определённой клетки для решения этой задачи. В двух вариантах: когда поле ограниченно, и когда неограниченно - клетка справа поля граничит с клеткой слева, клетки сверху граничат с клетками снизу. Похожий способ можно применять для сходных случаев перебора, например при переборе клеток шахматной доски куда может сходить конь.

Читать далее Перебор соседних клеток на двухмерном поле

Группировка и подсчёт элементов в списке Python

Рассмотрим задачу

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

Для хранения количества букв будем использовать словарь. Рассмотрим самый простой вариант подсчёта. Пройтись по всем буквам, если текущей буквы ещё нет в словаре, то это первое вхождение - устанавливаем кол-во равным одному, если буква уже есть то увеличиваем кол-во на 1.

Читать далее Группировка и подсчёт элементов в списке Python

Поиск периода Пизано

Даны целые числа \(1 \leq n \leq 10^{18}\) и \(2 \leq m \leq 10^5\), необходимо найти остаток от деления n-го числа Фибоначчи на m.

Читать далее Поиск периода Пизано

Особенности операций целочисленного деления и взятия остатка при работе с отрицательными числами

Когда речь идёт о положительных числах то с операциями целочисленного деления и взятия остатка все довольно просто. Результат всегда положителен и удовлетворяет уравнению

\(div\) - целочисленное деление
\(mod\) - остаток от деления
\(r = (r\ div\ d) * d + (r\ mod\ d)\)

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

Читать далее Особенности операций целочисленного деления и взятия остатка при работе с отрицательными числами