Strefa wyzwań - I_R_W14_M22_Java Algorytm Euklidesa - Ten sam algorytm, inny sposób myślenia

R1KXLQD32B6PA

Już wiesz

Algorytm Euklidesa można zapisać korzystając z iteracji lub rekurencji.
Algorytm Euklidesa wykorzystujący rekurencję ma dwie wersje: opartą na odejmowaniu i opartą na obliczaniu reszty z dzielenia.

Ćwiczenie 1

R1D8358LPM5X6

Do jakiego momentu wywoływana jest rekurencyjnie funkcja dla liczb a i b, według algorytmu Euklidesa wykorzystującego odejmowanie? Możliwe odpowiedzi: 1. do momentu, gdy liczby a oraz b staną się równe, 2. do momentu, gdy liczba a lub b będzie miała wartość 1, 3. do momentu, gdy liczba a lub b będzie miała wartość 0, 4. do momentu, gdy liczby a oraz b staną się różne

Ćwiczenie 2

Napisz program, który dla trzech liczb naturalnych: a, b, c wypisuje dwie z nich, które mają największy wspólny dzielnik. Przetestuj jego działanie dla liczb 51, 34, 45.

Specyfikacja problemu:

Dane:

a, b, c – liczby naturalne dodatnie

Wynik:

Na standardowym wyjściu program wypisuje dwie spośród trzech liczb, mające maksymalny NWD.

Jeśli wszystkie pary mają taki sam NWD, program wypisuje komunikat:

Pary mają taki sam NWD

Przykładowe wyjście dla a=7, b=100, c=150:

100 i 150

R1TW8ObNSanIb

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. public static int NWD otwórz nawias okrągły int x przecinek int y zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. while otwórz nawias okrągły x wykrzyknik znak równości y zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. if otwórz nawias okrągły x zamknij nawias ostrokątny y zamknij nawias okrągły. Linia 5. x znak równości x minus y średnik. Linia 6. else. Linia 7. y znak równości y minus x średnik. Linia 8. zamknij nawias klamrowy. Linia 9. return x średnik. Linia 10. zamknij nawias klamrowy. Linia 11. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. int a znak równości 51 średnik. Linia 13. int b znak równości 34 średnik. Linia 14. int c znak równości 45 średnik. Linia 15. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny int nwd1 znak równości NWD otwórz nawias okrągły a przecinek b zamknij nawias okrągły średnik. Linia 16. int nwd2 znak równości NWD otwórz nawias okrągły a przecinek c zamknij nawias okrągły średnik. Linia 17. int nwd3 znak równości NWD otwórz nawias okrągły b przecinek c zamknij nawias okrągły średnik. Linia 19. if otwórz nawias okrągły nwd2 ampersant lt średnik nwd1 ampersant amp średnik ampersant amp średnik nwd3 ampersant lt średnik nwd1 zamknij nawias okrągły. Linia 20. System kropka out kropka println otwórz nawias okrągły a plus cudzysłów i cudzysłów plus b zamknij nawias okrągły średnik. Linia 21. else if otwórz nawias okrągły nwd1 ampersant lt średnik nwd2 ampersant amp średnik ampersant amp średnik nwd3 ampersant lt średnik nwd2 zamknij nawias okrągły. Linia 22. System kropka out kropka println otwórz nawias okrągły a plus cudzysłów i cudzysłów plus c zamknij nawias okrągły średnik. Linia 23. else if otwórz nawias okrągły nwd1 ampersant lt średnik nwd3 ampersant amp średnik ampersant amp średnik nwd2 ampersant lt średnik nwd3 zamknij nawias okrągły. Linia 24. System kropka out kropka println otwórz nawias okrągły b plus cudzysłów i cudzysłów plus c zamknij nawias okrągły średnik. Linia 25. else. Linia 26. System kropka out kropka println otwórz nawias okrągły cudzysłów Pary mają taki sam NWD cudzysłów zamknij nawias okrągły średnik. Linia 27. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 29. zamknij nawias klamrowy.

public class Main {
    public static int NWD(int x, int y) {
        while (x != y) {
            if (x > y)
                x = x - y;
            else
                y = y - x;
        }
        return x;
    }
    public static void main (String [] args) {
        int a = 51;
        int b = 34;
        int c = 45;
        int nwd1 = NWD(a, b);
        int nwd2 = NWD(a, c);
        int nwd3 = NWD(b, c);
    
        if (nwd2 &lt; nwd1 &amp;&amp; nwd3 &lt; nwd1)
            System.out.println(a + " i " + b);
        else if (nwd1 &lt; nwd2 &amp;&amp; nwd3 &lt; nwd2)
            System.out.println(a + " i " + c);
        else if (nwd1 &lt; nwd3 &amp;&amp; nwd2 &lt; nwd3)
            System.out.println(b + " i " + c);
        else
            System.out.println("Pary mają taki sam NWD");
    }

}

Ćwiczenie 3

Firma Warzywa Inc produkuje włoszczyznę. Proces produkcji polega na umieszczeniu na plastikowej tacce marchewek, pietruszek, porów i selerów, owinięcie ich folią spożywczą i zapakowaniu w kartony zbiorcze. Firmie udało się zakontraktować u rolników a sztuk marchewek, b sztuk pietruszki, c sztuk porów i d sztuk selerów. Ile jednakowych paczek włoszczyzny może przygotować do sprzedaży filma Warzywa Inc, tak aby było ich jak najwięcej?

Prezes firmy, Jan Bajtek nie lubi marnowania żywności – zawsze zamawia warzywa w taki sposób, aby produkcja odbywała się bez strat i wykorzsytane były wszystkie warzywa.

Swoje rozwiązanie przetestuj dla a = 210, b = 150, c = 90, d = 60.

Specyfikacja problemu:

Dane:

a – liczba marchewek; liczba naturalna dodatnia
b – liczba pietruszek; liczba naturalna dodatnia
c – liczba porów; liczba naturalna dodatnia
d – liczba selerów; liczba naturalna dodatnia

Wynik:

Na standardowym wyjściu program wyświetla liczbę paczek włoszczyzny.

R78sPclgBOCjE

Przykładowe rozwiązanie zadania:

public class Rozwiazanie {
	public static void main(String[] args) {
		int a = 210, b = 150, c = 90, d = 60;
    	int nwdA_B = NWD(a, b);
    	int nwdC_D = NWD(c, d);
    	int nwdA_B_C_D = NWD(nwdA_B, nwdC_D);
    
    	System.out.println(nwdA_B_C_D);
    }
    
    static int NWD(int liczba1, int liczba2){
    	while(liczba2 != 0){
    		int temp = liczba1 % liczba2;
    		liczba1 = liczba2;
    		liczba2 = temp;
    	}
    	return liczba1;
    }

}

Implementacja algorytmu

I_R_W14_M22_Java Algorytm Euklidesa - Ten sam algorytm, inny sposób myślenia