Bài giảng Thuật toán nâng cao - Chương 5: Chia để trị - Nguyễn Thanh Bình

Bài tập (2) | Bài 2

Ước sổ chung lớn nhất của hai số nguyên dương được định nghĩa như sau

• nếu x = y thì usc(x, y) = x.

• nếu x > y thì unc(x, y) = usc(x-y, y)

• nếu x < y thì usC(x, y) = usc(x,y-x) 1. Xây dựng thuật toán đệ quy tính ước số chung lớn nhất

hai số nguyên dương 2. Khử đệ quy của thuật toán

Bài 3 1. Xây dựng thuật toán đệ quy in dãy nhị phân tương ứng

của một số nguyên 2. Khử đệ quy thuật toán trên

151