System.out.println(backwards);
s ph i là
ẽ
ả
yenwoD nellA
Bài t p 9
ậ
Hãy vi t m t ph
ng th c đ quy có tên
ế
ộ
ươ
ứ ệ
power đ nh n vào
ể
ậ
x và m t s nguyên
ộ ố
n r i tr
ồ
ả
l i
ạ x
n
. G i ý: m t đ nh nghĩa đ quy đ i v i phép tính này là
ợ
ộ ị
ệ
ố ớ
x
n
= x · x
n −1
. Đ ng th i, c n nh r ng m i
ồ
ờ ầ
ớ ằ
ọ
s nâng lên lũy th a b c 0 đ u b ng 1. Câu h i khó t ch n: b n có th làm cho ph
ng th c này hi u
ố
ừ
ậ
ề
ằ
ỏ
ự ọ
ạ
ể
ươ
ứ
ệ
qu h n, trong tr
ng h p
ả ơ
ườ
ợ n ch n, b ng cách dùng công th c
ẵ
ằ
ứ x
n
= (x
n/2
)
2
.
Bài t p 10
ậ
(Bài t p này đ
c d a trên trang 44 cu n sách Structure and Interpretation of Computer
ậ
ượ ự
ố
Programs c a Abelson và Sussman.) Kĩ thu t sau đây có tên g i Thu t toán Euclid vì nó xu t hi n trong
ủ
ậ
ọ
ậ
ấ
ệ
t p C b n c a Euclid (Cu n s 7, kho ng năm 300 TCN). Có l đây là thu t toán đáng k t lâu đ i
ậ
ơ ả ủ
ố ố
ả
ẽ
ậ
ể ừ
ờ
nh t
ấ
. Quy trình tính toán đ
c d a theo quan sát th y, n u
ượ ự
ấ
ế r là ph n d trong phép chia
ầ
ư
a cho b, thì
các
c s chung c a
ướ ố
ủ a và b cũng b ng c s chung c a
ằ
ướ ố
ủ b và r. Do v y ta có th dùng ph ng trình
ậ
ể
ươ
gcd(a, b) = gcd(b, r)
đ liên ti p rút g n bài toán tính
c s chung (GCD) v bài toán tính GCD c a các c p s nguyên ngày
ể
ế
ọ
ướ ố
ề
ủ
ặ ố
càng nh h n. Ch ng h n,
ỏ ơ
ẳ
ạ
gcd(36, 20) = gcd(20, 16) = gcd(16, 4) = gcd(4, 0) = 4
ng ý r ng GCD c a 36 và 20 thì b ng 4. Có th th y r ng v i b t kì hai s ban đ u nào, cách liên ti p
ụ
ằ
ủ
ằ
ể ấ ằ
ớ ấ
ố
ầ
ế
rút g n này cu i cùng s cho ta m t c p s mà s th hai b ng 0. Khi đó GCD s b ng s còn l i trong
ọ
ố
ẽ
ộ ặ ố
ố ứ
ằ
ẽ ằ
ố
ạ
c p.
ặ
Hãy vi t m t ph
ng th c có tên
ế
ộ
ươ
ứ
gcd đ nh n tham s là hai s nguyên r i dùng Thu t toán Euclid đ
ể
ậ
ố
ố
ồ
ậ
ể
tính và tr l i
c s chung l n nh t c a hai s .
ả ạ ướ ố
ớ
ấ ủ
ố
