Praca domowa 3 zad 17
17. Napisz metodę o nazwie nwd, która przyjmuje dwa argumenty typu całkowitego, a jako rezultat
zwraca wartość największego wspólnego dzielnika tych dwóch liczb. Do obliczenia największego
wspólnego dzielnika dwóch liczb można wykorzystać jedną z wersji algorytmu Euklidesa: bierzemy
dwie liczby, dla których chcemy obliczyć największy wspólny dzielnik i tworzymy z nich nową parę:
pierwszą z liczb jest liczba mniejsza, drugą jest reszta z dzielenia liczby większej przez mniejszą. Z
tak utworzonej pary znowu tworzymy nową w ten sam sposób. Cały proces powtarzamy do momentu
aż jedna z liczb jest równa 0. Wówczas druga z liczb jest największym wspólnym dzielnikiem. W
metodzie main() przetestuj działanie stworzonej metody.
Przykładowy wynik działania programu:
Największy wspólny dzielnik liczb 512 i 128 wynosi 128
Największy wspólny dzielnik liczb 378 i 1647 wynosi 27
// //=======================================================================================
// // ZADANIE 17:
// // SPOSOB 1:
// class Main
// {
// static int nwd(int a, int b)
// {
// int nwd = 1;
// while(a!=0 && b!=0)
// {
// if(a > b)
// {
// a = a%b;
// if(a%b == 0)
// {
// nwd = b;
// }
// else if(b%a == 0)
// {
// nwd = a;
// }
// }
// else
// {
// b = b%a;
// if(a%b == 0)
// {
// nwd = b;
// }
// else if(b%a == 0)
// {
// nwd = a;
// }
// }
// }
// return nwd;
// }
// public static void main(String[] args)
// {
// int p = 512 , q = 128 , x = 378 , y = 1647;
// System.out.println("Najwiekszy wspolny dzielnik liczb "+p+" i "+q+" wynosi "+nwd(p,q));
// System.out.println("Najwiekszy wspolny dzielnik liczb "+x+" i "+y+" wynosi "+nwd(x,y));
// }
// }
// //======================================================================================
// // SPOSOB 2:
// public class MyClass
// {
// public static void main(String args[])
// {
// int a = 512;
// int b = 128;
// System.out.println("Najwiekszy wspolny dzielnik liczb " + a + " i " + b + " wynosi " + nwd(a,b));
// int c = 378;
// int d = 1647;
// System.out.println("Najwiekszy wspolny dzielnik liczb " + c + " i " + d + " wynosi " + nwd(c,d));
// }
// static int nwd (int a, int b)
// {
// while (a != 0 && b != 0)
// {
// if (a > b)
// {
// a = a%b;
// }
// else
// {
// b = b%a;
// }
// }
// if (a != 0)
// {
// return a;
// }
// else
// {
// return b;
// }
// }
// }
1 - Czy w pętli while musi być (a!=0 && b!=0) a nie (a!=0 || b!=0) tylko dlatego, że nie dzielimy przez zero? Bez tego program mi nie działał, ale nie wiem, w którym miejscu mogłoby się stać a=0 lub b=0
2 - Jak działa ostatni if i else w drugim sposobie? Nie mogę sobie tego wyobrazić, bo przecież już w pętli while jest zapisane (a!=0 && b!=0)
Programowanie Dodaj post do ulubionych Poproś o pomoc
- 1
- Zaloguj się lub zarejestruj, by móc oceniać komentarze.
- Dodaj do ulubionych
1 - To wynika z przedstawionego w treści algorytmu. Działanie ma się wykonywać dopóki żadna z liczb nie jest zerem. Czyli obie jednocześnie muszą być różne od zera. Stąd iloczyn logiczny.
2 - ten if siedzi poza pętlą while, która skoro się skończyła, to znaczy to, że albo a albo b stało się zerem. I ten if działa zgodnie z tym jak zapisany jest w treści algorytm, tzn. największy wspólny dzielnik to ta liczba, która nie jest zerem.