Задачи по алгоритмам: ищем непростые числа

Я не математик, но люблю решать задачи. Я люблю трудные задачи, которые не знаешь, как решать, а если и знаешь, трудно написать код верно.

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

Говорят «У человека феноменальная память — он помнит все». Он записывает. Не помните, что делали три дня назад? Ведите дневник, а не покупайте «таблетки для памяти».

Задача

Дан массив положительных целых чисел. Сделать так, чтобы каждые два соседних числа оказались взаимно просты. Заменить два соседних числа a и b на наименьшее общее кратное lcm(a, b), когда a и b- взаимно не просты.

Два числа a и b взаимно просты, когда наибольший общий делитель чисел gcd(a, b) равен 1.

Наибольший общий делитель

b — делитель a, когда a делится на b. Пример: 6 делится на 6, 3, 2 и 1, поэтому 6, 3, 2 и 1 — делители 6.

c — общий делитель чисел a и b, когда a делится на c и b делится на c.

Примеры:

12 = 6 * 2 = 3 * 4 = 3 * 2 * 2 18 = 9 * 2 = 3 * 3 * 2 45 = 9 * 5 = 3 * 3 * 5 3 — общий делитель чисел 18, 45. 9 — общий и наибольший делитель чисел 18, 45. 3 — общий и наибольший делитель чисел 12, 18, 45.

Часто говорят «множители числа» вместо «делители».

Поиск наибольшего общего делителя: разложение числа на множители

Разложить число a на множители значит подобрать делители числа a и записать

Число p — простое, когда p делится только на 1 и p.

Разложить число a на простые множители значит записать

где — простые числа, а степени — положительные целые. При этом — простые числа не повторяются.

Найдем наибольший общий делитель чисел a и b, когда разложим числа на простые множители.

Поиск наибольшего общего делителя: алгоритм Евклида

Большие числа раскладывать на множители утомительно. Алгоритм Евклида поможет найти наибольший общий делитель проще.

| a, когда b = 0 gcd(a, b) = | | gcd(b, a mod b), когда b != 0 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

Алгоритм Евклида работает за время O(log n), где n = min(a, b).

Наименьшее общее кратное

Наименьшее общее кратное чисел a и b — наименьшее целое число c, которое делится на a и делится на b. Обозначают lcm(a, b).

Решение задачи

Движемся по массиву слева направо, ищем два смежных числа, которые взаимно не просты — 1 < gcd(c, d).

Пусть в массиве [a, b, c, d, e, f] взаимно просты a, b и взаимно просты b, c, а c, d — нет. Заменим числа c и d на c1 = lcm(c, d). Теперь придется снова проверить взаимную простоту c1 и b. Продолжим движение вправо, но запомним, что должны сходить влево. Заменяем числа nums[i], nums[i + 1], пока они взаимно не просты.

Теперь сходим влево — заменяем числа nums[i — 1], nums[i], пока они взаимно не просты.

Порядок замен не важен — это можно доказать.

Теперь проверим числа nums[i], nums[i + 1] снова, если заменили nums[i — 1], nums[i] хотя бы раз. Повторяем замены вправо и влево, чтобы nums[i] оказался взаимно прост с обоими соседями — слева nums[i — 1] и справа nums[i + 1].

Затем переходим к следующему числу i = i + 1 и снова объединяем с непростыми соседями. Продолжаем, пока не дойдем до конца массива.

Код на C++

Напишем и проверим код на leetcode.com.

Задача предлагает массив vector<int> nums, но мы хотим удалять числа посреди массива, а vector справляется с этим плохо, потому что хранит числа в памяти непрерывно. Вот так работает метод vector::erase():

• Способ 1 — запросить новый блок памяти, копировать элементы, кроме удаленного:

  

• Способ 2 — сдвинуть элементы после удаленного влево на один:

  

Превратим массив в двусвязный список — он удаляет элементы из середины быстрее.

using NumsList = list<int>; using NumsVector = vector<int>; NumsVector replaceNonCoprimes(NumsVector &vec) { NumsList nums{vec.begin(), vec.end()}; // … }

Теперь шагаем по списку слева направо: берем следующее число и объединяем с «непростыми» соседями справа и слева. Функция mergeRight объединяет число с соседом справа, а mergeLeft — слева.

NumsVector replaceNonCoprimes(NumsVector &vec) { // … auto iter = nums.begin(); while (nums.end() != iter) { bool replaced = mergeRight(nums, iter); if (replaced) { do { replaced = mergeRight(nums, iter); } while(replaced); do { replaced = mergeLeft(nums, iter); } while(replaced); } else { ++iter; } } //… }

Затем копируем числа из списка в массив и возвращаем:

using NumsList = list<int>; using NumsVector = vector<int>; NumsVector replaceNonCoprimes(NumsVector &vec) { // … vec = {nums.begin(), nums.end()}; return vec; }

Отправляем на проверку — программа работает.

LeetCode говорит, что программа жрет больше времени и памяти, чем другие.

Простой, но медленный и прожорливый кодusing NumsList = list<int>; bool nonCoprimes(int a, int b) { return 1 < std::gcd(a, b); } bool mergeRight(NumsList &nums, NumsList::iterator &iter) { bool merged = false; if (!nums.empty() && nums.end() != iter) { auto right = next(iter); if (nums.end() != right && nonCoprimes(*iter, *right)) { *iter = std::lcm(*iter, *right); nums.erase(right); merged = true; } } return merged; } bool mergeLeft(NumsList &nums, NumsList::iterator &iter) { bool merged = false; if (!nums.empty() && nums.end() != iter && nums.begin() != iter) { auto left = prev(iter); if (nonCoprimes(*left, *iter)) { *iter = std::lcm(*left, *iter); nums.erase(left); merged = true; } } return merged; } vector<int> replaceNonCoprimes(vector<int>& vec) { NumsList nums{vec.begin(), vec.end()}; auto iter = nums.begin(); while (nums.end() != iter) { bool replaced = mergeRight(nums, iter); if (replaced) { do { replaced = mergeRight(nums, iter); } while(replaced); do { replaced = mergeLeft(nums, iter); } while(replaced); } else { ++iter; } } vec = {nums.begin(), nums.end()}; return vec; }

Оптимизация

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

Не удаляем элементы массива, но стираем — пишем 0. Так мы не используем метод vector::erase(), но теперь массив содержит нули между соседними числами.

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

Индекс right подскажет функции mergeRight, где ближайший сосед справа. Массив не содержит нулей правее right — туда программа еще не добралась.

Уберем нули из массива, прежде чем отдать массив на проверку. Два способа:

• Копируем числа в новый массив, кроме нулей

NumsVector result; for (const auto &n: nums) { if (0 < n) { result.push_back(n); } }

Пусть программа знает, сколько чисел стерла, тогда знает, сколько памяти нужно:

NumsVector result{nums.size() — merged_count}; int w = 0; for (const auto &n: nums) { if (0 < n) { result[w++] = n; } }

• Сожмем исходный массив так, что нули окажутся в хвосте, а хвост отстрижем

int w = 0; for (int r = 0; r < nums.size(); ++r) { if (0 < nums[r]) { nums[w++] = nums[r]; } } nums.resize(w);

Экономим еще немного памяти, если используем vector вместо stack:

using SlicesStack = vector<int>;

Скромный и неприхотливый кодusing NumsVector = vector<int>; using SlicesStack = vector<int>; NumsVector replaceNonCoprimes(NumsVector &nums) { int merged_count = 0; int i = 0; SlicesStack slices; int right = i + 1; while (i < nums.size() && right < nums.size()) { bool merged = mergeRight(nums, i, right, merged_count); if (merged) { mergeLeft(nums, i, slices, merged_count); } else { if (1 < right — i) { slices.push_back(i); } i = right; right = i + 1; } } if (0 < merged_count) { int w = 0; for (int r = 0; r < nums.size(); ++r) { if (0 < nums[r]) { nums[w++] = nums[r]; } } nums.resize(nums.size() — merged_count); } return nums; } bool coprimes(int a, int b) { return 1 == std::gcd(a, b); } bool mergeRight(NumsVector &nums, int i, int &right, int &merged_count) { bool merged = false; while (right < nums.size() && !coprimes(nums[i], nums[right])) { nums[i] = std::lcm(nums[i], nums[right]); nums[right] = 0; ++right; merged = true; ++merged_count; } return merged; } void mergeLeft(NumsVector &nums, int i, SlicesStack &slices, int &merged_count) { int p = i — 1; while (0 <= p) { if (0 == nums[p]) { if (slices.empty()) { return; } p = slices.back(); } if (!coprimes(nums[p], nums[i])) { if (i — 1 == p) { slices.push_back(p); } nums[i] = std::lcm(nums[p], nums[i]); nums[p] = 0; ++merged_count; p = —slices.back(); if (p < 0 || 0 <= p && 0 == nums[p]) { slices.pop_back(); p = !slices.empty() ? slices.back() : -1; } } else { break; } } }

Пишите в комментариях, как бы вы еще сэкономили память или ускорили код, или предлагайте другие решения.

Источник: habr.com