Question

Hej! Proszę pomoże mi ktoś w zadaniu? 8 klasa informatyka (alogorytmy) przy okazji wytłumaczyłby mi ktoś o co tu chodzi? Dam 15 puntków <3

Answer 1

Wyjaśnijmy przedstawiony algorytm Euklidesa dla obliczenia NWW (największy wspólny dzielnik).

Przykład 1

- Zaczynamy program od przypisania wartości: a=28, b=42.

- W pierwszym kroku sprawdzamy, czy a i b są różne. Są, dlatego odpowiadamy TAK i idziemy do kolejnego warunku.

- Sprawdzamy, czy a > b. Czy 28 > 42? Nie, dlatego idziemy do zielonej ramki, gdzie mamy: b=b-a.

- Obliczamy 42-28 = 14, nasze nowe b to 14 i sprawdzamy warunek niebieski, zgodnie ze strzałką.

- Czy a !=b? Tak, dlatego sprawdzamy warunek a > b.

- Czy  28 > 14?  Tak, dlatego obliczamy nową wartość a: a=a-b.

- Liczymy a = 28- 14 = 14.

- Wracamy do warunku a!=b. Czy jest prawdziwy? Nie, dlatego idziemy za strzałką i mamy odpowiedź: Podaj liczbę a.

Dzięki temu wiemy, że NWW(28,42) = 14.

Przykład 2

- Zaczynamy program od przypisania wartości: a=15, b=95.

- W pierwszym kroku sprawdzamy, czy a i b są różne (a!=b). Są, dlatego odpowiadamy TAK i idziemy do kolejnego warunku.

- Sprawdzamy, czy a > b. Czy 15 > 95? Nie, dlatego idziemy do zielonej ramki, gdzie mamy: b=b-a.

- Obliczamy 95-15 = 80, nasze nowe b to 80 i sprawdzamy warunek niebieski, zgodnie ze strzałką.

- Czy a !=b? Tak, dlatego sprawdzamy warunek a > b.

- Sprawdzamy, czy a > b. Czy 15 > 80? Nie, dlatego idziemy do zielonej ramki, gdzie mamy: b=b-a.

- Obliczamy 80-15 = 65, nasze nowe b to 65 i sprawdzamy warunek niebieski, zgodnie ze strzałką. Czy a !=b? Tak, dlatego sprawdzamy warunek a > b.

- Czy 15 > 65? Nie, dlatego idziemy do zielonej ramki, gdzie mamy: b=b-a.

- Obliczamy 65-15 = 50, nasze nowe b to 50 i sprawdzamy warunek niebieski, zgodnie ze strzałką.

- Czy a !=b? Tak, dlatego sprawdzamy warunek a > b. Czy 15 > 50? Nie, dlatego idziemy do zielonej ramki, gdzie mamy: b=b-a.

- Obliczamy 50-15 = 35, nasze nowe b to 35 i sprawdzamy warunek niebieski, zgodnie ze strzałką.

- Czy a !=b? Tak, dlatego sprawdzamy warunek a > b. Czy 15 > 35? Nie, dlatego idziemy do zielonej ramki, gdzie mamy: b=b-a.

- Obliczamy 35-15 = 20, nasze nowe b to 20 i sprawdzamy warunek niebieski, zgodnie ze strzałką.

- Czy a !=b? Tak, dlatego sprawdzamy warunek a > b. Czy 15 > 20? Nie, dlatego idziemy do zielonej ramki, gdzie mamy: b=b-a.

- Obliczamy 20-15 = 5, nasze nowe b to 5 i sprawdzamy warunek niebieski, zgodnie ze strzałką.

- Czy a !=b? Tak, dlatego sprawdzamy warunek a > b. Czy 15 > 5? Tak, dlatego liczymy nowe a: a= a- b.

- Liczymy a = 15-5 = 10.

- Nasze nowe a to 10 i sprawdzamy warunek niebieski, zgodnie ze strzałką.

- Czy a !=b? Tak, dlatego sprawdzamy warunek a > b. Czy 10 > 5? Tak, dlatego liczymy nowe a: a= a- b.

- Liczymy a = 10-5 = 5.

- Wracamy do warunku a!=b. Czy jest prawdziwy? Nie, dlatego idziemy za strzałką i mamy odpowiedź: Podaj liczbę a.

Dzięki temu wiemy, że NWW(15,95) = 5.