Създадох метод, който ми позволява да намеряGCF / GCD от два числа и въпреки че имам работещ код, не знам как или защо работи. Разбирам алгоритъма на Euclid, но не съм сигурен как го използва следният фрагмент.
private int gcd(int a, int b)
{
if (b == 0)
return a;
else if(a ==0)
return b;
else
return gcd(b, a % b);
}
Особено съм объркан от това, което се връща, защото защо се връщат две стойности? И какво прави% b? Как се използва този алгоритъм на Евклид?
Отговори:
0 за отговор № 1"най-големият общ делител на две числа не се променя, ако по-голямото число се заменя от разликата му с по-малкото число. "
(уикипедия - евклидов алгоритъм)
И така, модул:
Модуло връща остатъка от целочисленото деление между две цели числа. Целочисленото деление е разделение без дроби или плаващи точки. Нека "обозначим целочисленото деление като m / n.
m / n = o;
m % n = p;
o * n + p = m;
Като пример,
29 / 3 = 9; (3 goes - whole - into 29 9 times)
29 % 3 = 2; (the integer division of 29 into 3 has a remainder of 2)
9 * 3 + 2 = 29; (9 goes into 29 3 times (and 3 goes into 29 9 times), with a remainder of 2)
Имайте предвид, че ако m е по - малка от n (Т.е. m < n), тогава n отива в m 0 пъти (m / n = 0), така че остатъкът от целочисленото деление ще бъде m (m % n = m, защото o * n + p = m и така (0*n) + p = 0 + p = p = m);
И така, как функционира функцията? нека опитаме да го използвате.
1 - gcd (m, n), m <n
Така че, ако започнем gcd(m, n) с m това е по-малко от n, единственото нещо, което се случва при следващото вложено повикване към gcd, е, че редът на аргументите се променя: gcd(n, m % n) = gcd(n, m);
2 - gcd (n, m), m <n
Добре, така че сега първият аргумент по-голям от втория.
Според алгоритъма на euclid, ние искаме да направим нещо на по-голямото от двете числа. Искаме да го заменим с разликата между него и по-малкото число. Бихме могли да направим m - n куп пъти. Но какво m % n прави е същото като изваждането n от m колкото е възможно повече пъти преди това ще доведе до отрицателно число. Извършването на изваждане би изглеждало така (((m - n) - n) - n) - n) и така нататък. Но ако го разширим, получаваме:
m - (n * o), защото o * n + p = m, можем да видим това m - (n * o) = p и p = m % n, И така, многократно изваждане на по-малкото от по-голямото е същото като правенето на модул на по-голямото с по-малкото.
В следващата стъпка вторият аргумент може да бъде 0 (ако n беше делител на m). В този случай функцията връща n. това е правилно, защото n е делител на себе си и също така, както видяхме, делител на m.
Или вторият аргумент може да е по-малък от n, Това е така, защото остатъкът от делението на цялото число на m в n трябва да бъде по - малък от n - това е така, ако останалата част от поделението беше по-голяма от n, тогава n можеше да се впише в m още веднъж, което не го направи, това е абсурден резултат. Ако приемем, че n не е 0, тогава вторият аргумент (нека го наречем p) е по-малък от n.
И така, сега се обаждаме gcd(n, p), където p < n.
3 - gcd (n, p), p <n
Какво се случва сега? добре, че сме точно на същото място, както бяхме в предишния параграф. Сега просто повтаряме тази стъпка, т.е. ще продължим да се обаждаме gcd(a, b), до по-малкото от двете числа, които се предават gcd(a ,b) е делител на по-голямото от двете числа, (което означава, че a % b = 0) в този случай просто връщате по-малкото от двете числа.
0 за отговор № 2
1) Какво прави% b?
% е операторът за модул или остатък в Java. Операторът% връща остатъка от две числа. Например 8% 3 е 2, тъй като 8 разделени на 3 оставят остатък от 2.
2) Евклидовият алгоритъм се основава напринцип, че най-големият общ делител на две числа не се променя, ако по-голямото число бъде заменено от разликата му с по-малкото число. Всъщност вашата gcd функция се използва по-ефективна версия на евклидовия алгоритъм. Тази версия вместо това заменя по-голямото от двете числа с остатъка му, когато е разделено на по-малкото от двете (при тази версия алгоритъмът спира, когато достигне нула остатък). Това е доказано от Габриел Ламе през 1844 г. (https://en.wikipedia.org/wiki/Euclidean_algorithm)
3) Функцията ви gcd „не връща две стойности,това е рекурсивна функция. Рекурсивната функция е функция, която или се извиква сама, или е в потенциален цикъл от функционални обаждания. В случай на вашата gcd функция, тя ще се повтаря, докато един от два параметъра не стане нула и gcd стойността е остава параметър.
Можете да научите повече за рекурсивната функция на този линк.
http://pages.cs.wisc.edu/~calvin/cs110/RECURSION.html
0 за отговор № 3
Имайки предвид, че въпросът ви има няколко компонента,Ще обсъдя еволюцията на класическия алгоритъм на Евклид в рекурсивния метод, който представихте. Моля, обърнете внимание, че методите, представени тук, предполагат това a >= b
Методът по-долу най-вероятно реализира алгоритъма, който сте запознати, който многократно изважда b (по-малкият брой) от a (по-голямото число), докато тя вече не е по-голяма или равна на b, ако a == 0, няма остатък, давайки b като GCD. В противен случай стойностите на a и b се разменят и многократното изваждане продължава.
public int classic_gcd(int a, int b) {
while (true) {
while (a >= b)
a = a - b;
if (a == 0)
return b;
int c = b;
b = a;
a = c;
}
}
Тъй като вътрешната, докато цикъл, по същество изчислява напомнянето на a разделена на b, може да бъде заменен с оператора на модул. Това значително подобрява степента на конвергенция на алгоритъма, замествайки потенциално голям брой изваждания с един модул операция. Помислете за намирането на GCD от 12 288 и 6, което би довело до над 2000 изваждане. Това подобрение е показано в модифицирания метод по-долу.
public int mod_gcd(int a, int b) {
while (true) {
int c = a % b;
if (c == 0)
return b;
a = b;
b = c;
}
}
И накрая, модифицираният алгоритъм може да се изрази като рекурсивен алгоритъм, тоест той призовава себе си, както следва:
public int recurse_gcd(int a, int b) {
if (b == 0)
return a;
else
return recurse_gcd(b, a % b);
}
Този метод постига същото като преди. Въпреки това, вместо да циклирате, методът извиква себе си (което, ако не е отметнато, също е безкраен цикъл). Подмяна на стойности се осъществява чрез промяна на реда на аргументите, предадени на метода.
Имайте предвид, че горепосочените методи са само за демонстрация и не трябва да се използват в производствения код.