В этой статье описывается алгоритм Java для решения величайшего общего делителя двух неотрицательных целых чисел. Поделитесь этим для вашей ссылки, следующим образом:
Кодовые функции:
1. Реализация Java (полный исходный код с тестовыми случаями);
2. Решите наибольший общий делитель двух неотрицательных целых чисел P и Q (P> = Q);
3. Два решения: метод цикла и рекурсивный метод;
Полный исходный код:
/ * GCD: Greatest Common Divisor */public Class GCD {public static void main (String args []) {/ * Тестовый случай */int p = 32; int q = 24; System.out.println («Величайший делитель«+p+»и«+q+»is /n»+»[gcd1]:"+gcd1 (p, q)+" /n"+"[gcd2]:"+gcd2 (p, q)); } // (q % gcd == 0 и p % gcd == 0 [gcd от q до 1]) public int int gcd1 (int p, int q) {int gcd = 1; int d = q; while (d> 0) {d--; if (q%d == 0 && p%d == 0) {gcd = d; перерыв; }} return gcd; } // gcd (p, q) = gcd (q, p%q) [if q = 0, gcd = p] public static int gcd2 (int p, int q) {if (q == 0) return p; int r = p%q; //System.out.println("("+Q+","+r+ ")") "); вернуть gcd2 (q, r); }}Скриншот работает:
Код объяснение:
Круглый метод GCD1 (P, Q)
Описание естественного языка: метод цикла решает наибольший общий делитель двух неотрицательных целых чисел P, Q (P> = Q), то есть решает максимальное значение общего делителя Q, который P. Пусть D (разделенное) уменьшение от p (шаг уменьшения = 1) D всегда «максимальное значение состояния, которое должно быть удовлетворено». Когда D соответствует условию (оно может быть разделено на P и делится на P), D является общим делителем P и Q, а D является наибольшим распространенным делителем P и Q;
Рекурсивный метод GCD2 (P, Q)
Описание естественного языка: рекурсивный метод решает наибольший общий делитель двух неотрицательных целых чисел P, Q (P> = Q). Когда Q равен 0, наибольшим распространенным делителем является P; В противном случае возьмите оставшуюся часть P и Q, чтобы получить R = P%Q, а наибольший общий делитель P и Q является наибольшим распространенным делителем Q и R;
Кодовый опыт:
Что касается метода петли, вначале я думал, что написал метод для решения общих делителей, использовать целочисленный массив для хранения всех общих делителей неотрицательного целого числа, а затем сравнить и выяснить самый большой общий делитель, общий в P и Q, который является наибольшим распространенным делителем двух чисел. Позже я подумал, так как он должен найти максимум, разве не будет легче напрямую уменьшить с задней части фронта? Снижение от спины к фронту может гарантировать, что это число всегда является самым большим в настоящее время, потому что люди, которые больше, чем он не соответствует условиям (может быть разделена на P и Q одновременно), одновременно устраняются, что позволяет избежать проблемы с находом максимального изначально. Хотя есть много способов найти максимум, если у вас есть или не нужно было доказать и искать, ха -ха, почему вы немного относитесь к философии?
Что касается рекурсии, то, что я могу полностью понять, основываясь на моей интуиции, является единственным предложением, что наибольший общий делитель P и Q является наибольшим распространенным делителем Q и R (R = P%Q), который является началом кольца, но я все еще не совсем понимаю, что конечное условие кольца составляет 0, и возврат P;
Хотя это очень простое решение для наибольшего алгоритма распространенного делителя, я должен написать его двумя способами, в основном, чтобы почувствовать метод рекурсии, с которым я не очень знаком. В прошлом я видел четкую формулу алгоритма рекурсии для решения цифр Ганновер и Фибоначчи, которые там освещались, и я вздыхал, что это полностью математика! Чувство, которое я узнал сегодня, было еще более шокирующим, чем в это время. Я задавался вопросом, что случилось, и решило это странно. В то время меня не заботилось о памяти, эффективности и других показателях. Я просто думал, что ребята, которые могли бы думать об этом, были действительно умными. Для них, будь то компьютер или язык программирования, это был просто инструмент для решения проблемы. Некоторые люди говорят, что рекурсия - это алгоритм, который позволяет мозгу думать о компьютерах, чтобы рассчитывать, и это действительно уместно.
Ссылки
Серия программирования Тьюринга: Алгоритмы (4 -е издание) Роберт Седжвик (автор), Кевин Уэйн (автор), Се Луюн (переводчик)
Для получения дополнительной информации об алгоритмах Java, читатели, которые заинтересованы в этом сайте, могут просмотреть темы: «Учебное пособие по структуре данных Java и алгоритм», «Сводка операции Java Dom Node», «Сводка Java File и каталог
Я надеюсь, что эта статья будет полезна для всех Java Programming.