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
biến thiên trong khoảng 0..1,
- m biến thiên trong khoảng
1..N.
|
FAREY.INP
|
FAREY.OUT
|
|
5
|
11
0 1
1 5
1 4
1 3
2 5
1 2
3 5
2 3
3 4
4 5
1 1
|
Dữ
liệu vào: tệp văn bản FAREY.INPchứa số
N.
Dữ
liệu ra: tệp văn bản FAREY.OUT
Dòng
thứ nhất: D – số lượng các phân số trong dãy.
Từ
dòng thứ hai: mỗi dòng hai số tự nhiên t m ghi cách nhau qua dấu cách, thể hiện
một phân số trong dãy sắp tăng.
Thuật toán
Nếu sinh lần lượt các phân số (PS) rối sắp xếp thì khá tốn
bộ nhớ vì tối đa phải dành đủ bộ nhớ để lưu trữ n2 PS.
|
Farey là nhà địa chất
học người Anh. Ông mô tả dãy phân số trên vào năm 1816.
|
Phương
án 1. Nếu t/m và a/b là hai PS số liên tiếp trong dãy Farey thì
a/b = min { x/y | x/y > t/m, y
= 1..n, x £ y, (x,y) = 1 }
trong đó (x,y) là
ước chung lớn nhất của x và y.
Các PS x/y trong
tập trên được gọi là các ứng viên. Ta sẽ đề cử càng ít ứng viên càng tốt.
Với y = 1, do x £ y nên ta có ngay PS 1/1 là phần tử lớn nhất trong dãy.
Với mỗi y = 2..n
ta xét PS x/y là PS đầu tiên lớn hơn t/m.
Ta có 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 PS x/y thỏa đồng thời các tính chất sau:
- 1 £ m £ n
- x/y lầ PS đầu
tiên lớn hơn t/m.
Đặc tả trên được
thu gọn lại với n-1 ứng viên như sau,
a/b = min { x/y |
y = 2..n, x = (ty div m) + 1 }
Như vậy, nếu đã
sinh được PS t/m cho dãy Farey thì PS tiếp theo a/b sẽ được chọn là PS nhỏ nhất
trong tập n-1 PS nói trên. Để ý rằng 0/1 là PS đầu
tiên và 1/1 là PS cuối cùng của dãy Farey. Thủ tục Next(n,t,m) trong phương án 1 sẽ xác định PS a/b sát sau
PS t/m trong dãy Farey. Giá trị tìm được sẽ đặt ngay trong t/m.
Độ phức tạp. Xuất
phát từ PS đầu tiên 0/1, mỗi lần ta phải sinh ra n-1 ứng viên để từ đó chọn ra 1 PS trong dãy. Nếu
dãy có s PS thì ta phải thực hiện s(n-1) phép toán trên các PS. Giá trị max của s là n2.
Vậy độ phức tạp tính toán vào cỡ n3.
Bình luận
Nếu từ PS t/m
trong dãy Farey và giá trị mẫu số y trong khoảng 2..n cho trước ta sinh ra PS
x/y thông qua hệ thức x = (ty div m) + 1 thì PS 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ì PS 10/12
không tối giản do đó ta cần gọi thủ tục RutGon đẻ giản ước PS x/y.
Vì không tính
trước được số lượng các PS trong dãy nên ta cần đếm dần và ghi tạm dãy PS vào
tệp FAREY.TMP. Sau đó mở tệp FAREY.OUT ghi số lượng s và chuyển dữ liệu từ tệp FAREY.TMP
sang tệp FAREY.OUT, cuối cùng xóa tệp FAREY.TMP.
Phương án 2. Ta có thể sinh dần các phần tử cho dãy Farey như
sau. Cho hai PS a/b và c/d, PS (a+c)/(b+d) được gọi là PS trung bình của
hai PS này.
Nhận xét. Nếu t1 / m1 , t2
/ m2 , t3 / m3 là ba PS liên tiếp trong dãy
Farey thì PS giữa là PS trung bình của hai PS kia.
Ta có thuật toán
sau:
Xuất phát với mẫu
số m = 1 ta có dãy 2 PS: 0/1, 1/1.
Với mỗi mẫu số m
= 2..n ta sinh các PS trung bình có mẫu số
m của hai PS kề nhau trong dãy trước và xen PS này vào giữa hai PS sinh
ra nó dần vào trong dãy kết quả.
m = 2: thêm các
PS trung bình với mẫu bằng 2: 0/1, 1/2 , 1/1.
m = 3: thêm các
PS trung bình với mẫu bằng 3: 0/1, 1/3, 1/2, 2/3, 1/1.
...
Các phân số mới
sinh trong mỗi lần duyệt được gạch dưới.
Ta dùng hai
mảng: a lưu các PS của dãy trước, b lưu
các PS của dãy sau. Sau mỗi bước lặp ta chuyển b qua a. Dữ liệu được mô tả như sau:
const mn = 1000;
type
PS = record tu,mau: byte
end;
mps = array[0..mn] of
PS; { mảng các PS }
var a,b: mps;
Độ phức tạp. Thời gian: n3, miền nhớ : 2 mảng
kích thứơc n2.
Phương án 3. Ta
sử dụng một số tính chất của dãy Farey để tiếp tục cải tiến thuật toán.
Nếu t1 / m1 , t2
/ m2 , t3 / m3 là ba PS liên tiếp trong dãy
Farey thì
1. t2m1 – t1m2
= 1,
2. m1 + m2 > n,
3. t2 / m2 = (t1
+ t3) / (m1 + m3),
4. t3 = vt2 – t1,
m3 = vm2 – m1 với v = (m1 + n) div m2.
Từ tính chất 4 ta
suy ra ngay cách xác định PS t3/m3 thông
qua hai PS sát trước.
Các trình dưới
đây minh họa 3 phương án với các kết quả hiển thị trên màn hình để bạn đọc có
thể theo dõi.
(* Pascal *)
(*------------------------------------*
Ba phuong an cho bai
Day Farey
*-------------------------------------*)
uses crt;
const bl = #32; nl = #13#10;
var n: integer;
{ Uoc chung lon nhat cua hai so tu nhien a, b }
function Ucln(a,b:integer):integer;
var r: integer;
begin
while b > 0 do begin
r := a mod b; a := b; b:=r end;
Ucln:=a;
end;
{ Rut gon PS a/b thanh PS t/m }
procedure RutGon(a,b:integer; var t,m:integer);
var d:integer;
begin d :=Ucln(a,b); t := a div d; m := b div d; end;
{ Tim PS sat sau PS
t/m, ket qua dat trong t/m }
function Next(n: integer; var t,m: integer): Boolean;
var a,b,x,y: integer;
begin
if (t+m=2) then begin
Next := false; exit end;
a := 1; b := 1;
for y := 2 to n do
begin
x := t*y div m + 1;
if a*y > b*x then begin a := x;
b:=y end;
end;
RutGon(a,b,t,m); Next := true;
end;
procedure Farey1(n: integer);
var t,m,d:integer;
begin
writeln(nl,'Farey1'); d :=
0;
t := 0; m := 1;
repeat
write(t,'/',m,bl); inc(d);
until not Next(n,t,m);
writeln(nl,'Total: ',d,'
PS');
readln;
end;
procedure Farey2(n: byte);
const mn = 1000;
type PS = record tu,mau: byte end;
mps1 = array[0..mn] of
PS;
var a,b: mps1; { 2 day PS a , b }
d,k,i,m:integer;
begin
writeln(nl,'Farey2'); d :=
2;
a[1].tu := 0; a[1].mau := 1; { PS dau day }
a[2].tu := 1; a[2].mau := 1; { PS thu hai }
for m:=2 to n do
begin
k := 0; inc(k); b[k] :=
a[k];
for i := 2 to d do
begin
if a[i].mau+a[i-1].mau
= m then
begin
inc(k); b[k].tu :=
a[i-1].tu + a[i].tu;
b[k].mau :=
a[i-1].mau + a[i].mau;
end;
inc(k); b[k] := a[i];
end;
a := b; d := k;
end;
for i := 1 to d do
write(a[i].tu,'/',a[i].mau,bl);
writeln(nl,'Total ',d,'
PS');
readln;
end;
procedure Farey3(n: integer);
var t1,m1,t2,m2,t3,m3,v,d: integer;
begin
writeln(nl,'Farey3'); d :=
2;
t1 := 0; m1 := 1; { PS dau day }
t2 := 1; m2 := n; { PS thu hai }
write(t1,'/',m1,bl,t2,'/',m2,bl);
while (t2 + m2 <> 2) do
begin
v := (m1+n) div m2;
t3 := v*t2 - t1; m3 := v*m2 - m1;
write(t3,'/',m3,bl); inc(d);
t1 := t2; t2 := t3;
m1 := m2; m2 := m3;
end;
writeln(nl,'Total ',d,' PS'); readln;
end;
BEGIN
n := 5;
Farey1(n); Farey2(n);
Farey3(n);
END.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét