Накануне выпускного класса Сяо Хуэй из Школы компьютерных наук снова столкнулся с палящим солнцем.
Отправляйтесь в ИТ-компанию на собеседование на должность инженера по исследованиям и разработкам...
Через полчаса в переговорной компании начинается собеседование...
Сяохуэй написал быстро, через пять минут...
Идея Сяо Хуэя очень проста. Он использует метод перебора грубой силы, чтобы попытаться найти подходящее целое число i и посмотреть, может ли это целое число делиться на два целочисленных параметра numberA и numberB одновременно.
Целое число i начинается с 2 и накапливается в цикле, пока не будет накоплена половина меньших параметров в числах A и B. После завершения цикла наибольшее значение i, которое может делиться на два найденных в последний раз числа, является наибольшим общим делителем этих двух чисел.
После этого удрученный Сяо Хуэй отправился за советом к коллеге-ученому Да Хуану...
Алгоритм Евклида, также известный как алгоритм Евклида, используется для нахождения наибольшего общего делителя двух натуральных чисел. Это старейший из известных алгоритмов, датируемый 300 г. до н.э.
Этот алгоритм основан на теореме:Два натуральных числа a и b (a>b) имеют наибольший общий делитель, равный наибольшему общему делителю между c и b, остатку от деления a на b.Например, 10 и 25, 25 разделить на 10 в частном 2 дает 5, тогда наибольший общий делитель 10 и 25 равен наибольшему общему делителю 10 и 5.
С помощью этой теоремы найти наибольший общий делитель несложно. Мы можем использовать рекурсию, чтобы шаг за шагом упростить задачу.
Сначала мы вычисляем остаток c при делении a на b и преобразуем задачу в поиск наибольшего общего делителя b и c, затем вычисляем остаток d при делении b на c и превращаем задачу в поиск максимального общего делителя c и d, затем вычислите остаток e от деления c на d и преобразуйте задачу в поиск наибольшего общего делителя d и e...
И так далее, постепенно упрощая операцию между двумя большими целыми числами в операцию между двумя целыми числами меньшего размера, пока число не станет делиться на два или число, которое не уменьшится до 1.
Пять минут спустя Сяо Хуэй изменил код...
Более вычитательный метод из древнекитайских «Девяти глав арифметики» также является алгоритмом нахождения наибольшего общего делителя.
Его принцип еще проще:Два натуральных числа a и b (a>b), наибольший общий делитель которых равен разности c чисел a-b и наибольшему общему делителю меньшего числа b..Например, 10 и 25, разница между 25 минус 10 равна 15, тогда наибольший общий делитель 10 и 25 равен наибольшему общему делителю 10 и 15.
Исходя из этого, мы также можем упростить задачу с помощью рекурсии. Во-первых, мы сначала вычисляем разность c между a и b (при условии, что a>b) и преобразуем задачу в поиск наибольшего общего делителя b и c; затем вычисляем разницу d между c и b (при условии, что c>b), преобразовать задачу в поиск наибольшего общего делителя b и d, затем вычислить разницу e между b и d (при условии, что b > d) и преобразовать задачу в поиск наибольшего общего делителя d и e.... ..
По аналогии операция между двумя большими целыми числами постепенно сводится к операции между двумя меньшими целыми числами до тех пор, пока два числа не станут равными, а наибольший общий делитель - это два числа, которые в конечном итоге равны.
Пять минут спустя Сяо Хуэй переписал код...
Хорошо известно, что выполнение сменных операций очень быстрое. Для заданных натуральных чисел a и b нетрудно получить следующие выводы. Где gcb(a,b) означает функцию наибольшего общего делителя a,b:
Когда и a, и b четные, gcb(a,b) = 2*gcb(a/2, b/2) = 2*gcb(a>>1, b>>1)
Когда a четно, а b нечетно, gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)
Когда a нечетно, а b четно, gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)
Когда a и b являются нечетными числами, используя метод вычисления убывания, gcb (a, b) = gcb (b, a-b), в этом случае должно быть четное число a-b, и операция сдвига может быть продолжена.
Например, шаги для вычисления наибольшего общего делителя 10 и 25 таковы:
Целое число 10 можно преобразовать в наибольший общий делитель 5 и 25 сдвигом
Используя более вычитательный метод, вычислите 25-5=20, преобразуйте его в наибольший общий делитель 5 и 20.
Целое число 20 можно преобразовать в наибольший общий делитель 5 и 10 сдвигом
Целое число 10 можно преобразовать в наибольший общий делитель 5 и 5 сдвигом
Используя более вычитательный метод, поскольку два числа равны, наибольший общий делитель равен 5.
Когда два числа относительно малы, преимущество количества вычислений временно не видно.Когда два числа больше, экономия количества вычислений более очевидна.
Подводя итоги все время сложности вышеуказанного решения:
1.перебор грубой силы: временная сложность O(min(a, b)))
2.бросание и деление: Временная сложность не очень хороша для расчета, ее можно аппроксимировать как O(log(max(a, b))), но производительность операции по модулю плохая.
3.более субтрактивный: операции по модулю избегают, но производительность алгоритма нестабильна, а наихудшая временная сложность равна O(max(a, b)))
4.Больше фазовое вычитание в сочетании с транспозицией: Не только избегает операции по модулю, но также имеет стабильный производительность алгоритма, а сложность времени является O (журнал (MAX (A, B))))
В этой статье изначально было написано только о методе подбрасывания и деления, а потом пользователи сети указали, что есть более оптимизированные решения.Похоже, я еще неопытен.Спасибо большое за указание на проблему. Кроме того, параметры метода по умолчанию должны быть целыми положительными числами, поэтому в коде отсутствует проверка правильности.
Более субтрактивная техника, описанная в тексте, представляет собой упрощенный подход. В исходном тексте девятой главы по арифметике есть еще одна проверка: если оба числа четные, то перед вычислением разницы оба числа будут разделены пополам, так что количество вычислений будет меньше. Этот метод достиг частичной оптимизации, но древние, похоже, не думали, что можно оптимизировать одну нечетную и одну четную ситуацию.
Из-за ограничений по объему в этой статье опущены принципы и доказательства принципа метода подбрасывания и отклонения и вычитания. На самом деле процесс доказательства не сложен, и внимательные студенты могут попробовать изучить его самостоятельно. Спасибо всем, что заглянули!
----КОНЕЦ----
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента