Lăn tăn

(Suu tam)
Trong dân gian có câu Lăn tăn, lèo tèo Toán và Tin
Cây lăn tăn khó ăn dễ trèo
Cây lèo tèo khó trèo dễ ăn
Vận dụng trong học tập, câu này có thể hiểu là có những bài Toán Tin khá dễ hiểu nhưng giải thì khó lắm, ngược lại, có những bài, khi đọc đề thì toát mồ hôi, dựng tóc gáy, nhưng khi sờ tay vào bàn phím thấy nhẹ nhàng như không, loáng cái đã giải xong. Chúng ta thử xem bài sau đây là lăn tăn hay lèo tèo nhé
Dãy Faray
Năm 1816 Farey, một nhà địa chất học người Anh mô tả dãy phân số sau đây.
Cho số tự nhiên N > 0. hãy liệt kê theo trật tự tăng dần các phân số t/m thỏa đồng thời các tính chất sau:
- t/m là phân số tối giản nằm trong khoảng 0..1,
- m biến thiên trong khoảng 1..N.
Mới xem ai cũng cho rằng đây là bài toán lèo tèo. Tuy nhiên khi bắt tay vào giải mới thấy rằng bài này rất là … lăn tăn. Chả thế mà nhiều nhà toán học lớn đã viết hàng loạt công trình khảo cứu dãy phân số trên. Cũng vì thế mà mọi người đặt tên cho dãy đó là dãy Farey để vinh danh người đầu tiên đề xuất ra bài toán trên.
Thí dụ, với N = 5 chúng ta có dãy gồm 11 phân số như sau:
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.
Nếu sinh lần lượt các phân số rồi sắp xếp chúng thì khá tốn bộ nhớ vì tối đa phải dành đủ bộ nhớ để lưu trữ
phân số. Ngoài ra chúng ta còn phải lọc bớt những phân số trùng lặp nữa chứ, thí dụ, với N=5 thì các phân số t/m = 2/4 và 1/2 là như nhau. Vậy là thuật giải tự nhiên nói trên đòi hỏi miền nhớ
và thời gian
.
Để so sánh hai phân số t1/m1 và t2/m2 ta sử dụng hệ thức nhân chéo sau đây:
t1/m1
t2/m2 khi và chỉ khi t1.m2
t2.m1.
Chúng ta cùng lần theo lịch sử toán học để xem lời giải bài toán trên được hoàn thiện dần ra sao.
Phương án 1.
Với N cho trước ta tìm cách sinh lần lượt theo trật tự tăng dần các phân số cho dãy Farey. Giả sử ta đã viết được phân số t/m và cần xác định phân số a/b tiếp theo. Dễ thấy a/b phải là phân số đầu tiên sau t/m thỏa các điều kiện của đầu bài, cụ thể là
•

• t/m < a/b
• (a,b) = 1, (a,b) là ước chung lớn nhất của hai số tự nhiên a và b. Điều kiện này cho biết a/b là phân số tối giản.
Từ các điều kiện trên ta suy ra


Nói cách khác, phân số sát sau phân số t/m trong dãy Farey cần tìm sẽ là phân số nhỏ nhất trong tập các phân số x/y mô tả như trên.
Với mỗi phân số t/m tập các phân số x/y mô tả như trên được gọi là các ứng viên. Ta sẽ chọn ra càng ít ứng viên càng tốt.
Với y = 1, do
nên ta có ngay phân số 1/1 là phần tử lớn nhất trong dãy. Đây cũng là phân số duy nhất trong dãy có tử số bằng mẫu số, mọi phân số t/m còn lại của dãy luôn luôn thỏa t < m.
Với mỗi y = 2..N ta xét phân số x/y là phân số đầu tiên lớn hơn t/m như sau.
Từ t/m < x/y ta suy ra mx > ty nên x > (ty div m). Nếu biết m ta chọn x = (ty div m) + 1 sẽ thu được phân số x/y là phân số đầu tiên lớn hơn t/m.
Đặc tả trên được thu gọn lại là


Như vậy, nếu đã sinh được phân số t/m cho dãy Farey thì phân số tiếp theo a/b sẽ được chọn là phân số nhỏ nhất trong tập N-1 phân số nói trên.
Để ý rằng 0/1 là phân số đầu tiên trong dãy Farey.
Thủ tục Next(t,m) dưới đây sẽ xác định phân số a/b sát sau phân số t/m trong dãy Farey.
Giá trị tìm được sẽ đặt ngay trong t/m.


Thủ tục RutGon(a,b) sẽ rút gọn phân số a/b bằng cách chia cả tử a và mẫu b cho ước