Treść zadania:
Napisz algorytm znajdowania największego wspólnego dzielnika pary liczb.
Takie zadanie otrzymałem do wykonania. Nie bardzo wiem, jak się za nie zabrać. Ogólnie z matematyki jestem noga.
- Rejestracja:ponad 9 lat
- Ostatnio:prawie 9 lat
- Postów:225
0
int nwd(int m, int n)
{
if (m == n)
return m;
else if (m > n)
return nwd(m-n, n);
else
return nwd(n-m, m);
}
Przyspieszenie działania algorytmu (w wyniku zmniejszenia liczby rekurencyjnych wywołań funkcji) możesz uzyskać, zastępując wielokrotne odejmowanie tej samej liczby dzieleniem z resztą
int nwd(int m, int n)
{
if (m == 0)
return n;
else if (n == 0)
return m;
else if (m == n)
return m;
else if (m > n)
return nwd(m%n, n);
else
return nwd(n%m, m);
}
edytowany 1x, ostatnio: PrzemolPrzemol
- Rejestracja:około 9 lat
- Ostatnio:około 8 lat
- Postów:8
0
Chyba najłatwiejsze rozwiązanie to odejmowanie w pętli mniejszej liczby od większej aż obie zmienne będą sobie równe - uzyskana wartość jest wtedy największym wspólnym dzielnikiem.
while(numA!=numB)
{
if(numA>numB)
{
numA-=numB;
}
else
{
numB-=numA;
}
}
edytowany 2x, ostatnio: buffalo42
0
Bo nie każdy musi być od radu wredny aby używać mocniejszych słów? Nie zamieniajcie się w drugą elektrodę.
gdybyśmy byli elektrodą, mielibyśmy osobny dział: „algorytm euklidesa - gotowce”
- Rejestracja:prawie 20 lat
- Ostatnio:17 dni
0
PrzemolPrzemol napisał(a):
int nwd(int m, int n)
{
if (m == n)
return m;
else if (m > n)
return nwd(m-n, n);
else
return nwd(n-m, m)
}
to nie będzie działać poprawnie.
Nawet po dopisaniu brakującego średnika.
Właśnie o tym mówię.
Wiedziałem, że nie chodzi Ci o średnik.
Moglibyście powiedzieć dlaczego? Nie sprawdzałem tego, ani drugiego wrzuconego przeze mnie kodu z modulo, na szybko pisałem i myślałem, że będzie ok
A średnik mi umknął
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.
numA=1,numB=10000000000. Sensowny algorytm winien korzystać z operatora modulo (%).