452 2

452

12. Rozwiązania zadań

Jeśli z, =0. to nwd (r__łt r₀) = nwd (x, y)=r₀-y. Zauważmy,że

(i)    dowolna liczba dzieląca r__x i r₀ musi dzielić także r,,

(ii)    odwrotnie, dowolna liczba dzieląca r, i r₀ musi dzielić także r_ ,.

To sugeruje następujący algorytm (Euklidesa). Tworzymy ciągi skończone {r„} \    ^

+ *■«    (&><>. r,n = 2, 3.....M.

Obliczenia są skończone, gdyż /'_B+l<r_ll dla «>0. czyli musi być /-„-O. np. dla * = >-. Jeśli jednak r_v = 0. to *>,,[/•*_ ₂ i r,_v|r^_ j (w istocie jest r_v__x=nwd (r_A_₂, /•*_,)). _(cź 3 wobec (ii). Rozumując tak dalej, otrzymujemy, że r_K__v|r₀ i r_v_,|r_₁. To, żc ^rs-1 jest największym wspólnym dzielnikiem r₀ i r_. wynika stąd, że dzięki (i) dowolny dzielnik r₀ i r, musi dzielić r_N_,.

Poniższy program w języku Basic jest rozwiązaniem ostatniej części zadania. Działa on dla dowolnego ułamka 11/12.

10 PR1NT "WPROWADZIĆ LICZBY CAŁKOWITE Tl I 12, GDZIE 12#0"

20 INPUT II, 12 30 S-SGN(I1)*SGN (12)

40 RI = ABS(Il)

50 R2= ABS(I2)

60 Q=INT(RI/R2)

70 PRINT "CZESC CAŁKOWITA =", S*Q 80 R1 = RI — Q*R2

90 REM STOSUJE SIE TERAZ ALGORYTM EUKLIDESA (WIERSZE 130- 170) 100 REM DO UPROSZCZENIA CZĘŚCI UŁAMKOWEJ (=S*(RI/R2))

110 Tl = Rl 120 T2=R 2

130 R3 = RI — INT (R1/R2)*R2 140 IF R3 = 0 TI1EN ISO 150 Rl — R2 160 R2 = R3 170 GOTO 130

180 PRrNT "CZESC UŁAMKOWA-', S»T!/R2, 7*\ T2/R2 190 END

(Funkcja INT(X/Y) daje największą liczbę całkowitą nic większą od X/Y.) Czytelnik może wykonać ten program na maszynie lub ręcznie, aby upewnić się, że daje on nastę pujące wyniki.

11	12	Część całkowita	Część ułamkowa
5	4	1	1/4
162	54	3	0/1
172	22	7	9/11
-44	154	0	— 2/7
-7	7	-l	on
— 65	— 3	21	2/3