Алгоритмы

Условие

Дано число \(N\). Найти все пифагоровы тройки такие что \(a + b + c = N\). Пифагоровы тройки удовлетворяют условиям \(a^2 + b^2 = c^2\) и \(a \lt b \lt c\).

Решение

Простейшее решение перебором даёт сложность \(O(n^2)\):

for a in range(n):
  for b in range(a + 1, n):
    c = N - a - b
    if is_triplet(a, b, c):
      add_result(a, b, c)

for a in range(n):

for b in range(a + 1, n):

c = N - a - b

if is_triplet(a, b, c):

add_result(a, b, c)

Оптимизации на сокращение перебора в случае когда он дальше не имеет смысла не влияют на порядок роста.

Эту же задачу можно решить за \(O(n)\). Из условий задачи следуют два уравнения:

\(a + b + c = N\)
\(a^2 + b^2 = c^2\)

\(N\) является константой. Примем так же за константу \(a\). Остаётся система из двух уравнений с двумя неизвестными. Последовательно решаем её.

\(c = N - a - b\) (1)
\(c^2 - b^2 = a^2\)
\((c - b)(c + b) = a^2\) (2)
\((n - a - b - b)(n - a - b + b) = a^2\) (подставляем 1 в 2)
\((n - a - 2b)(n - a) = a^2\)
\(n^2 - an - 2nb - an + a^2 + 2ab = a^2\)
\(n^2 - 2an - 2nb + 2ab = 0\)
\((2a - 2n)b = 2an - n^2\)
\(b = \frac{2an - n^2}{2a - 2n}\)
\(c = N - a - b\)

Используя формулы для вычисления \(b\) и \(c\) в цикле по \(a\) находим все пифагоровы тройки.

def triplets_with_sum(number):
    res = []
    n = number
    for a in range(1, number):
        b = (2 * a * n - n ** 2) / (2 * a - 2 * n)
        c = n - b - a

        if round(b) == b and a < b < c:
            res.append([a, b, c])

    return res

def triplets_with_sum(number):

res = []

n = number

for a in range(1, number):

b = (2 * a * n - n ** 2) / (2 * a - 2 * n)

c = n - b - a

if round(b) == b and a < b < c:

res.append([a, b, c])

return res

В задаче Bitwise AND дано множество чисел \(S = \{1, 2, 3, ..., N\}\), нужно найти два числа \(A\) и \(B\) такие что значение \(A \& B\) (побитовый оператор И) наибольшее, но меньше заданного \(K\). Вывести наибольшее возможное \(A \& B\).

Ограничения:

\(2 \leq N \leq 10^3\)
\(2 \leq K \leq N\)

Решение

Решение с перебором рабочее, но не проходит по скорости: всего пар \(N * (N - 1)\), сложность получается \(O(n^2)\).

У этой задачи есть решение за константное время. Предположим число \(K\) нечётное. Это значит что в побитовой записи справа у него находится единица:

\(11_{10} = 1011_2\)

Рассмотрим \(K-1\), в двоичной записи все его цифры совпадают с \(K\) кроме последней в которой находится 0:

\(10_{10} = 1010_2\)

Читать далее Задача Bitwise AND

Наибольший общий делитель двух чисел Фибоначчи

Задача

Найти последнюю цифру наибольшего общего делителя двух чисел Фибоначчи.

Решение

Сразу отклоняем вычисление чисел Фибоначчи и нахождение их НОД, так как числа могу быть очень большие.

Воспользуемся свойством чисел Фибоначчи:

Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов.

\(НОД(F_n, F_m) = F_{НОД(n, m)}\)

Учитвая это вычисляем индекс числа Фибоначчи который одновременно является и нужным НОД, а затем находим его последнее число при помощи периода Пизано.

Сложность

Сложность алгоритма равна сложности нахождения наибольшего общего делителя. Так как вычисления периода Пизано при заданном модуле ограничено сверху, то его можно взять за константу.

Код

На вход подаются два индекса чисел Фибоначчи.

def fib_mod(n, m):
    seq_pisano = find_pisano(m)
    return seq_pisano[n % len(seq_pisano)]

def find_pisano(m):
    pisano = [0, 1]
    n0 = 0
    n1 = 1

    for _ in range(m * 6):
        n0, n1 = n1, (n0 + n1) % m
        pisano.append(n1)

        if pisano[-1] == 1 and pisano[-2] == 0:
            break

    return pisano[:-2]

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

n, m = (int(x) for x in input().split())
f = gcd(n, m)
r = fib_mod(f, 10)
print(r)

def fib_mod(n, m):

seq_pisano = find_pisano(m)

return seq_pisano[n % len(seq_pisano)]

def find_pisano(m):

pisano = [0, 1]

n0 = 0

n1 = 1

for _ in range(m * 6):

n0, n1 = n1, (n0 + n1) % m

pisano.append(n1)

if pisano[-1] == 1 and pisano[-2] == 0:

break

return pisano[:-2]

def gcd(a, b):

while a != 0:

a, b = b % a, a

return b

n, m = (int(x) for x in input().split())

f = gcd(n, m)

r = fib_mod(f, 10)

print(r)

Triangle Quest

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

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

333

4444

а во второй:

121

12321

1234321

123454321

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

for i in range(1,int(input())):
    print # можно менять только эту строку

1 2	for i in range(1,int(input())): print # можно менять только эту строку

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

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

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

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

[1, 2, 3, 4, 5]

1	[1, 2, 3, 4, 5]

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

10101 = [1, 3, 5]
00011 = [4, 5]
00000 = []

10101 = [1, 3, 5]

00011 = [4, 5]

00000 = []

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

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

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

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

результат = множество содержащие в себе пустое множество
Для каждого элемента x из исходного множества 
  копия_результата = копировать результат

  # в каждый элемент копии добавляем элемент исходного множества
  Для каждого элемента y из копия_результата
    y = y + x

  # Объединяем результат и копию
  результат = результат + копия_результата

результат = множество содержащие в себе пустое множество

Для каждого элемента x из исходного множества

копия_результата = копировать результат

# в каждый элемент копии добавляем элемент исходного множества

Для каждого элемента y из копия_результата

y = y + x

# Объединяем результат и копию

результат = результат + копия_результата

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

Пример на Python:

import copy

main_set = [1, 2, 3]
print(main_set)

def get_subsets(main):
    result = [[]]

    for main_element in main:
        new_set = copy.deepcopy(result)
        for item in new_set:
            item.append(main_element)
        result += new_set

    return result

print(get_subsets(main_set))

import copy

main_set = [1, 2, 3]

print(main_set)

def get_subsets(main):

result = [[]]

for main_element in main:

new_set = copy.deepcopy(result)

for item in new_set:

item.append(main_element)

result += new_set

return result

print(get_subsets(main_set))

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

Вместо

if first_condition:
  if second_condition:
    first_operator
  else:
    second_operator
else:
  if second_condition:
    second_operator
  else: 
    first_operator

if first_condition:

if second_condition:

first_operator

else:

second_operator

else:

if second_condition:

second_operator

else:

first_operator

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

if first_condition ^ second_condition: # ^ - оператор xor 
  second_operator
else
  first_operator

if first_condition ^ second_condition: # ^ - оператор xor

second_operator

else

first_operator

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

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

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

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

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

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

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

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

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

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

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

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

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

Пн	Вт	Ср	Чт	Пт	Сб	Вс
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28

Рубрика: Алгоритмы

Задача Pythagorean Triplet

Условие

Решение

Задача Bitwise AND

Решение

Наибольший общий делитель двух чисел Фибоначчи

Задача

Решение

Сложность

Код

Triangle Quest

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

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

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

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

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

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