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 £ 480.000. Hãy phân tích n! ra tích của các thừa số nguyên tố theo trật tự tăng dần. Thí dụ,  13! = 210.35.52.7.11.13. Kết quả hiển thị dưới dạng các dòng, mỗi dòng một số nguyên tố tiếp đến là số mũ tương ứng. Các số trên cùng dòng cách nhau qua dấu cách. Thí dụ trên cho ta kết quả hiển thị như sau
2  10
3  5
5  2
7  1
11 1
13 1

Thuật toán

Nhận xét  Cho số tự nhiên N và một số nguyên tố p. Khi đó,
Nếu viết dãy thừa số 1, 2, ..., N vào một bảng có p cột thì ta thấy có n1 = N div p dòng chứa p, 2p,...,n1.p (ở cột cuối cùng). Nhóm các phần tử này lại ta được,
1p.2p....n1p = (1.2...n1).pn1. Thực hiện tương tự với tích 1.2...n1 ta thu được n2 = n1div p dòng chứa  p, 2p,...,n2.p... Từ đây ta suy ra lũy thừa k của p, pk trong dạng phân tích của N! sẽ là k = n1+n2+...+nv, trong đó ni = ni-1 div p, n1 = N div p, nv = 0, i = 2..v. Hàm tính lũy thừa của p trong dạng phân tích của N! bằng các phép chia liên tiếp khi đó sẽ như sau,    
function Power(n,p: longint): byte;
var k: byte;
begin
  k := 0;
  while (n <> 0) do
   begin
    n := n div p;
    k := k + n;
   end;
  Power := k;
 end;
Ta dùng hàm NextPrime để sinh lần lượt các số nguyên tố p trong khoảng 2..N và tính Power(N,p). Nếu giá trị này lớn hơn 0 thì ta hiển thị kết quả.
procedure Fac(n: longint);
const bl = #32; { Dau cach }
var p: longint; k: byte;
begin
  writeln;
  p := 2;
  while p <= n do
  begin
    k := Power(n,p);
    if (k > 0) then writeln(p,bl,k);
    p := NextPrime(p);
  end;
end;
Hai hàm phụ trợ.
Hàm IsPrime(p) kiểm tra p có phải là số nguyên tố hay không bằng cách xét xem trong khoảng từ 2 đến  có ước nào không.
function IsPrime(p: longint): Boolean;
var i: longint;
begin
  IsPrime := false;
  if p < 2 then exit;
  for i := 2 to round(sqrt(p)) do
     if p mod i = 0 then exit;
  IsPrime := True;
end;
Hàm NextPrime(p) sinh số nguyên tố sát sau p bằng cách duyệt tuần tự các số lẻ sau p là p+2k nếu p lẻ và (p-1) + 2k, nếu p chẵn.
function NextPrime(p: longint): longint;
begin
  if p < 2 then
   begin
     NextPrime := 2;
     exit;
   end;
  if not odd(p) then p := p-1;
  repeat
    p := p+2;
  until IsPrime(p);
  NextPrime := p;
end;
Ta có thể cải tiến khá mạnh tốc độ tính toán bằng các kỹ thuật sau.
Sinh sẵn các số nguyên tố trong khoảng từ 1..N bằng giải thuật Sàng mang tên nhà toán học Hi Lạp Eratosthene. Từ vài nghìn năm trước, Eratosthenes đã dạy như sau:


Baì giảng của Eratosthenes

Eratosthenes (276-194 tr. CN) Nhà toán học lỗi lạc Hy Lạp Cổ đại. Ông sinh tại Cyrene, theo học trường phái Plato tại Athens. Hoàng đế Ptolemy II mời ông đến Alexandria để dạy cho hoàng tử.
 
 
Nếu trò muốn liệt kê toàn bộ các số nguyên tố nằm trong khoảng từ 1 đến N hãy làm như sau
   1. Viết dãy số từ 1 đến N.
   2. Xóa đi số 1 vì nó không phải là số nguyên tố, cũng không phải là hợp số. Nó là một số đặc biệt.
   3. Lần lượt duyệt từ 2 đến như sau. Nếu gặp số chưa bị xóa thì đó chính là một số nguyên tố. Trò hãy xóa mọi bội của số này kể từ bình phương của nó trở đi.
    Khi kết thúc, những số nào không bị xóa trên tấm bảng sẽ là các số nguyên tố. Đó là kho các số nguyên tố trong khoảng 1..N.
     
Thời đó chưa có giấy viết nên thày trò phải viết trên những tấm bảng bằng đất sét vào lúc đất còn dẻo, các số bị xóa được đục thủng. Sau khi phơi khô ta thu được những tấm bảng thủng lỗ chỗ như một cái sàng gạo.
Với mảng a[0..MN] of byte đủ lớn, thí dụ, MN = 60.000 ta có thể  ghi nhận các số nguyên tố nằm trong khoảng 1..MN. Ta qui ước a[i] = 0 thì i là số nguyên tố, a[i] = 1 ứng với số i bị dùi thủng nên i không phải là số nguyên tố.
procedure Eratosthenes(n: longint);
var i,j: longint;
begin
  fillchar(a,sizeof(a),0);
  for i := 2 to round(sqrt(n)) do
    if a[i]=0 then
       for j := i to (n div i) do a[i*j] := 1;
end;
 Thủ tục phân tích N! ra thừa số nguyên tố dạng cải tiến sẽ như sau,
procedure NewFac(n: longint);
const bl = #32; { Dau cach }
 var i,p: longint;
begin
  Eratosthenes(n);
  writeln;
  for i := 2 to n do
    if a[i] = 0 then
       begin
         p := Power(n,i);
         if P > 0 then writeln(i,bl,p);
       end;
end;

Dùng kỹ thuật đánh dấu bit có thể tạo kho số nguyên tố cỡ 8.MN vì một byte có 8 bit, mỗi bit sẽ quản lí 1 số.
Mảng a vẫn được khai báo như trước: a[0..MN] of byte(quan trọng là chỉ số phải tính từ 0 trở đi) nhưng lúc này mỗi phần tử a[i] sẽ quản lí 8 số chứ không phải một số như trước. Tiếp đến bạn cần  viết thêm ba thủ tục sau đây:
Thủ tục BitOn(i) -  đặt trị 1 cho bit thứ i trong dãy bit a (bật bit). Các bit trong dãy a sẽ được mã số từ 0 đến 8MN-1= 480.000-1. Bản thân số 480.000 là hợp số nên ta có thể bỏ qua.

procedure BitOn(i: longint);
 var b,p: longint;
begin
  b := i shr 3; { i div 8 }
  p := i and 7; { i mod 8 }
  a[b] := a[b] or (1 shl p);
end;

Đặt trị 1 cho bit i trong dãy bit a
1. Xác định xem bit i nằm trong byte nào
b := i div 8
2. Xác định xem bit i là bit thứ mấy trong byte b (tính theo trật tự 7,6,5,4,3,2,1,0)
p := i mod 8
3. Lấy số nhị phân 8 bit 00000001 dịch trái p vị trí rồi cộng logic theo bit với a[b].
a[b] := a[b] or (1 shl p);

Bạn ghi nhớ sự tương đương của các phép toán sau đây
Phép toán
Phép toán tương đương
x div 2k
x shr k
x mod 2k
x and 2k-1

Tính theo dạng này sẽ nhanh hơn

Thủ tục BitOff(i) đặt trị 0 cho bit thứ i trong dãy bit a (tắt bit).
procedure BitOff(i: longint);
 var b,p: longint;
begin
  b := i shr 3; { i div 8 }
  p := i and 7; { i mod 8 }
  a[b]:=a[b] and (not(1 shl p));
end;


Đặt trị 0 cho bit i trong dãy bit a
1. Xác định xem bit i nằm trong byte nào
b := i div 8;
2. Xác định xem bit i là bit thứ mấy trong byte b (tính theo trật tự 7,6,5,4,3,2,1,0)
p := i mod 8;
3. Lấy số nhị phân 6 bit 00000001 dịch trái p vị trí, lật rồi nhân logic theo bit với a[b].
a[b]:=a[b] and (not(1 shl p));

Hàm GetBit(i) cho ra trị (1/0) của bit i trong dãy bit a.
function GetBit(i: longint): byte;
 var b,p: longint;
begin
  b := i shr 3;
  p := i and 7; { i mod 8 }
  GetBit := (a[b] shr p) and 1;
end;
Đặt trị 0 cho bit i trong dãy bit a
1. Xác định xem bit i nằm trong byte nào
b := i div 8;
2. Xác định xem bit i là bit thứ mấy trong byte b (tính theo trật tự 7,6,5,4,3,2,1,0)
p := i mod 8;
3. Dịch a[b] qua phải p vị trí, rồi nhân logic theo bit với 00000001 để lấy bit phải nhất (bit 0).
GetBit := (a[b] shr p) and 1;

Các thủ tục cơ bản theo kỹ thuật xử lí bit khi đó sẽ như sau.
procedure Eratosthenes_B(n: longint);
var i,j: longint;
begin
  fillchar(a,sizeof(a),0);
  for i:=2 to round(sqrt(n)) do
    for j:=i to (n div i) do
       BitOn(i*j);      
end;
procedure BFac(n: longint);
const bl = #32; { Dau cach }
 var i,p: longint;
begin
  Eratosthenes_B(n);
  writeln;
  for i:=2 to n do
    if GetBit(i)=0 then
       begin
         p := Power(n,i);
         if P > 0 then writeln(i,bl,p);
       end;
end;



Độ phức tạp

Để liệt kê các số nguyên tố từ 1..N ta duyệt từ 1 đến , với mỗi số nguyên tố ta phải gạch tối đa cỡ N các bội của chúng. Vậy độ phức tạp tính toán cỡ N..

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