Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



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
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts