Разбираю очередную задачу на канале с задачами:
Задача
2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10.
Какое самое маленькое число делится нацело на все числа от 1 до 20?
Решение
У автора есть наивное и оптимизированное решения. Наивное рассматривать не будем в силу его наивности (полный перебор).
Для оптимизированного автор предлагает следующую стратегию:
Будем исходить из факта, что если число делится на какие-то числа, значит оно является их произведением. В таком случае, перемножив все числа от 2 до 20, мы получим число, которое содержит все эти числа внутри себя как множители и значит делится на любое из них.
Проблема только в том, что это число не будем минимальным. Чтобы уменьшить его, нужно выкинуть из него те множители, которые повторяются несколько раз. Например: множитель 16 не нужен, потому что уже есть множители 2 и 8. Множитель 20 не нужен, потому что есть 4 и 5, и т.д.
Автор кеширует множители в массиве, куда может попасть только число, которое нельзя получить из множителей, уже имеющихся в массиве.
А я сделал всё буквально шиворот-навыворот. Вероятно, получилось хуже, но как альтернатива сойдёт.
У меня при добавлении в массив множитель не делится на те, которые есть, а наоборот умножается на них. И эти новые произведения также добавляются в массив (если их там ещё нет).
Вот пример. В массиве лежат множители 2, 3, 4, и добавляется 5. Значит, получаются новые комбинации: 2*5, 3*5, 4*5, 2*3*5, 2*4*5, 3*4*5.
Нетрудно заметить, что чем больше элементов в массиве, тем утомительнее этот перебор.
Поэтому я храню их в развёрнутом виде. Когда после 2 добавляется 3, я также добавляю 2*3, то есть 6. Когда добавляется 4, я также добавляю 2*4=8, 3*4=12 и 6*4=24. Таким образом, всевозможные предыдущие комбинации уже посчитаны и лежат друг за другом линейно, их нужно просто брать по очереди.
По поводу числа 24, и всех чисел больше 20. Это не легитимные множители, поэтому они разлагаются на мелкие. Если при разложении получились новые легитимные множители, они идут в зачёт, иначе просто игнорируются.
Отбор множителя для финального произведения происходит в тот момент, когда он успешно добавился в массив, либо какие-то его комбинации с предыдущими множителями добавились в массив. Это определяется путём сравнения старой и новой позиции списка.
Структура данных
В одном массиве хранятся множители и есть отдельная переменная для обозначения позиции в нём, а в другом я сделал псевдо-хеш-таблицу для быстрого поиска элемента по значению (значение является индексом). Чтобы это всё было вместе, я сделал структуру:
Функция, которая добавляет элемент в массив и хеш-таблицу (если его ещё нет, это важно):
Функция разложения на множители действует перебором и пытается добавить любой найденный множитель:
Ссылка на онлайн-компилятор языка C с тестом программы:
https://onlinegdb.com/pbhwqzUQF
В программе присутствовали некоторые оптимизации вроде кеша произведений и разложения на множители только тогда, когда число больше 20. Но я их убрал ради краткости. Код отрабатывает за 0 миллисекунд, даже если увеличить N до 50. Поэтому оптимизации пока не нужны.
Вся подборка задач: