Cong Ty Cong Nghe Tin Hoc Nha Truong - Lăn Tăn, Lèo Tèo Toán Và Tin

Có thể bạn quan tâm

Lăn tăn, lèo tèo Toán và Tin 31/01/2008

Trong dân gian có câu

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 chung lớn nhất của chúng.

Bình luận

Nếu đã biết phân số t/m trong dãy Farey và giá trị mẫu số y trong khoảng 2..N ta sinh ra phân số x/y thông qua hệ thức x = (ty div m) + 1 thì phân số x/y có thể chưa tối giản. Thí dụ, với N = 15, t/m = 3/4, y = 12 ta có x = (ty div m)+1 = 10 thì phân số 10/12 không tối giản, do đó ta cần gọi thủ tục RutGon để giản ước phân số x/y. Tuy nhiên ta có thể để thủ tục RutGon ở ngoài vòng lặp for. Bạn hãy giải thích vì sao?

Chương trình SFarey dưới đây hiển thị dãy Farey trên màn hình với mỗi giá trị N nạp từ bàn phím. Muốn dừng chương trình bạn hãy nạp N < 1.

Phương án 2.

Ta có thể sinh dần các phần tử cho dãy Farey như sau. Cho hai phân số t1/m1 và t2/m2, ta gọi phân số (t1+t2)/(m1+m2) là phân số trung bình của hai phân số này.

Vào các năm 1858-1860 nhà toán học Đức Moriz Stern và một nhà sản xuất đồng hồ người Pháp Achille Brocot đã đề xuất một cấu trúc sinh dãy Farey khá thú vị gọi là cây Stern-Brocot.

Ta sẽ diễn tả thuật toán xây dựng cây Stern-Brocot theo cách dễ hiểu hơn và tạm gọi thủ tục này là Tam giác Stern-Brocot vì nó khá giống với thủ tục xây dựng tam giác Pascal để tính các hệ số của nhị thức Newton .

Ta khởi trị dòng đầu tiên với hai phân số là 0/1 và 1/1.

Dòng 1: 0/1 1/1

Tiếp đến ta sinh các phân số cho Dòng 2 bằng cách lấy lại toàn bộ các phân số của dòng 1 và xen phân số trung bình vào giữa các cặp phân số kề nhau. Ta thu được

Dòng 2: 0/1 1/2 1/1 (Để dễ quan sát ta gạch dưới các phần tử mới thu thêm tại mỗi dòng.)

Tại Dòng 3 ta lại tạo ra các phân số trung bình của hai phần tử kề nhau trên Dòng 2 rồi xen chúng vào giữa hai đỉnh đó. Ta có

Dòng 3: 0/1 1/3 1/2 2/3 1/1

Lặp lại các thao tác trên ta thu được

Dòng 4: 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1

Dòng 5: 0/1 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 1/1

…

Dĩ nhiên dãy phân số thu được chưa phải là dãy Farey. Từ dãy này sẽ có cách thu được dãy Farey. Trước hết ta để ý kết quả sau:

Nhận xét 1. Nếu t1/m1 và t2/m2 là hai phân số liên tiếp trong dòng bất kỳ của tam giác Stern-Brocot thì

m1.t2 – m2.t1 = 1 (1)

Điều này có thể chứng minh dễ dàng bằng quy nạp toán học như sau.

Tại dòng 1, lúc xuất phát ta có: m1.t2 – m2.t1 = 1.1 – 1.0 = 1.

Giả sử hệ thức (1) đúng với mọi dòng từ 1 đến i. Ta chứng minh hệ thức này đúng với mọi phần tử trên dòng i+1 tiếp theo.

Gọi t1/m1 và t2/m2 là hai phân số kề nhau trên dòng i. Theo giả thiết quy nạp ta có m1.t2 – m2.t1 = 1. Phân số trung bình của hai phân số này là (t1+t2)/(m1+m2). Ta xét dãy ba phân số sau t1/m1 (t1+t2)/(m1+m2) t2/m2.

Thật vậy, bạn hãy triển khai hai về trái của hai biểu thức trên và áp dụng hệ thức (1) để ước lược là thu được ngay điều phải chứng minh.

Ngoài ra ta để ý rằng nếu t1/m1 < t2/m2 thì t1/m1 < (t1+t2)/(m1+m2) < t2/m2. Để kiểm tra điều này bạn chỉ cần dùng kỹ thuật nhân chéo như đã trình bày trong phương án 1.

Như vậy các dòng trong tam giác Stern-Brocot bảo lưu trật tự sắp tăng của các phân số.

Điều thú vị nữa là mọi phân số sinh ra theo cách trên đều tối giản!

Nhận xét 2. Tam giác Stern-Brocot chứa mọi phân số tối giản trong khoảng 0/1.

Thật vậy, giả sử ta có phân số tối giản a/b thỏa 0 a/b 1. Nếu a/b = o/1 hoặc a/b = 1/1 thì a/b xuất hiện tại dòng 1. Ta giả thiết là a/b 0 và a/b 1. Khi đó tại một dòng nào đó ta phải có t1/m1 < a/b < t2/m2 với t1/m1 và t2/m2 là hai phân số kề nhau tại dòng đang xét. Bất đẳng thức trên cho ta a.m1 – b.t1 > 0 và b.t2 – a.m2 > 0. Do các đại lượng đều là những số nguyên nên ta có

a.m1 – b.t1 1 và b.t2 – a.m2 1 (2)

Do t1/m1 và t2/m2 là hai phân số kề nhau trong dãy nên hệ thức (1) được thỏa, tức là m1.t2 - m2.t1 = 1. Nhân từng vế của hệ thức (2) lần lượt với (t2+m2) và (t1+m1) rồi cộng từng vế của chúng lại ta được

(t2 + m2)(a.m1 – b.t1) + (t1 + m1)(b.t2 – a.m2) t1 + m2 + t2 + m1

Rút gọn vế trái của bất đẳng thức trên ta thu được

a.t2.m1-b.t1.t2+a.m1.m2-b.t1.m2+b.t1.t2-a.t1.m2+b.t2.m1-a.m1.m2 =

= a.t2.m1-b.t1.m2-a.t1.m2+b.t2.m1 = a(t2.m1-t1.m2) + b(t2.m1-t1.m2) =

= (a+b).1 = a+b. Vậy là,

a+b (t1 + t2) + (m1 + m2)

Hệ thức trên cho thấy rằng sau nhiều nhất là a+b lần tính phân số trung bình ta sẽ thu được phân số trung bình là a/b.

Để thu được dãy Farey ta tiến hành như sau.

Khởi trị hai phân số giới hạn đầu và cuối của dãy: 0/1 1/1.

Lặp với m := 2 .. N: Tạo các phân số trung bình có mẫu số m.

Thí dụ, với N = 5 ta thực hiện như sau,

Khởi trị hai phân số mẫu số 1: a = (0/1, 1/1)

m = 2: Tạo các phân số trung bình mẫu số 2, a = (0/1, 1/2, 1/1)

m = 3: Tạo các phân số trung bình mẫu số 3, a = (0/1, 1/3, 1/2, 2/3, 1/1)

m = 4: Tạo các phân số trung bình mẫu số 4, a = (0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1)

m = 5: Tạo các phân số trung bình mẫu số 5, a = (0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1)

Để cài đặt ta sử dụng 2 mảng a và b chứa các phân số được tạo ra sau mỗi bước lặp, trong đó a là dãy thu được tại bước i, b là dãy thu được tại bước i+1. Hàm Next(m) trong chương trình dưới đây tạo dãy b từ dãy a bằng cách xen thêm vào dãy các phân số trung bình mẫu số m. Hàm cho ra số lượng các phân số được tạo ra tại mỗi dòng.