Đề thi HSG Tin học tỉnh Nam Đinh 2009-2010

[TruongTamPhong]

1000? Chắc chắn bài này giới hạn n sẽ không nhỏ hơn 10000 vì chạy với cách cổ nhất (cách của mình) thì với n=10000 chạy mất 1s. Có cải tiến phải giới hạn to nữa.

[36hoangcau]

Bài hai mình nghĩ là bạn nên đưa ra giới hạn cho số N chứ. Để mọi người có thuật toán hoàn chỉnh [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[muabuon]

Bài hai mình nghĩ là bạn nên đưa ra giới hạn cho số N chứ. Để mọi người có thuật toán hoàn chỉnh [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

xin lỗi, mình quên nêu giới hạn của n: 2<n<20000

[thieuk55]

Nếu vậy thì mình nghĩ dùng sàng Eratosthene là đủ rồi. Đơn giản, dễ cài đặt. Sau đó thì for một vòng trong tập sô nguyên tố vừa sinh được để kiểm tra xem có bao nhiêu trường hợp thôi.

@TieuLong: Đoạn kiểm tra số nguyên tố của em không được gọn lắm, anh nghĩ là em nên sinh mảng số nguyên tố trước luôn rồi mới kiểm tra. Đoạn code khởi tạo các số nguyên tố từ 1 -> MaxN có thể viết như sau:

const
  maxN = 20004;
var
  Prime : array [1..maxN] of longint; // lưu các số nguyên tố
  PrimeSqr : array [1..maxN] of longint; // lưu bình phương của các số nguyên tố.
  Count : longint;  

procedure InitPrime;
var 
  T, i, j, check : longint;
begin
  Count := 2;
  check := 0;
  Prime[1] := 2;
  Prime[2] := 3;
  PrimeSqr[1] := 4;
  PrimeSqr[2] := 9;
  T := 3;
  while true do
  begin
  // Một số nguyên tố bất kì lớn hơn 3 chỉ có thể có dạng (6k+1) hoặc (6k+5) -> Có thể áp
  //dụng "bước nhảy 2" và "bước nhảy 4" trọng thuật toán sinh các số nguyên tố
    T := T + 2;
    If T > MaxN then 
      exit;

    for i := 1 to Count do
      if (PrimeSqr[i] > T) then
        break
      else
      if (T mod Prime[i] = 0) then
      begin
        check := T;
        break;
      end;
    
    if (check <> T) then
    begin
      inc(Count);
      Prime[Count] := T;
    end;
    // 
    T := T + 4;
    If T > MaxN then 
    exit;

    {Đoạn này copy y nguyên đoạn ở trên, 
     đoạn giữa hai dòng "T := T+2" và "T := T+4" xuống}
  end;

end;

Đoạn code trên được viết trực tiếp trên diễn đàn, chưa Compile thử, nên có gì sai sót anh em sửa hộ với nhé [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Cái trên không thể nhanh bằng sàng, nhưng được cái "thân thuộc" hơn với các bạn mới học đến xử lí số nguyên tố [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Tốc độ thì cũng tạm chấp nhận được [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[kingkonghn]

Em thấy cách của em tuy chưa gọn nhưng vẫn là nhanh hơn chứ. Trong khi anh sinh hết các số nguyên tố rồi mới tiến hành xử lí thì em kiểm tra các số i=1-> n/2 nếu số nào là nguyên tố thì tiếp kiểm tra số n-i là nguyên tố thì tăng đếm. Như thế được cái là không phải tạo mảng số nguyên tố, thời gian tạo mảng số nguyên tố cũng bằng thời gian em chạy xong test rồi.
Hang_vt: giới hạn 20000 [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](!

[balothuhn]

@ Giang: Trên kia chỉ là đoạn code mẫu thôi, còn ứng dụng thì phải linh hoạt chứ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Thế để anh post thuật toán của anh lên nhá:

Đầu tiên là sinh các số nguyên tố từ 1->410 theo cách trên
Sau đó thì thực hiện các dòng lệnh:

function Check(T:longint):boolean;
var
     i, j, k  : longint;
begin
     for i := 1 to maxN do
               if PrimeSqr[i] > T then
                      exit(true)
               else
                if T mod Prime[i] = 0 then
                      exit(false);
end;

Function Answer : longint;
var
     dem,t,k : longint;
begin
      dem := 0;
      t := 2;
   while (t <= N div 2) do
   begin
            if Check(t) and Check(N-t) then
                  inc(dem);
      t := t+2;
   end;
   exit(dem);
end;

Cách này đã đủ thuyết phục em chưa Giang [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[wapa]

Cách của anh áp dụng 2 định lí trong topic kiểm tra tính nguyên tố em đưa ra đúng không? Cách này ổn hơn cách cơ bản vì bước nhảy không còn là 1 mà là 2 4 2 4, khi kiểm tra cũng không từ 1->sqrt mà các snt trong 1->sqrt(N). Cách này ngon rồi, không biết có cách nào tốt hơn nữa không nhỉ?

[admin]

Cách tốt hơn nữa thì em dùng sàng, sàng Eratosthenes hay Atkin thì tuỳ em chọn. Thuật toán sàng có lẽ đủ nhanh cho em xử lí bài toán này. Em lên Wikipedia search là có thông tin về hai thuật toán này, nếu đọc được Wiki tiếng Anh thì càng tốt [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[trungvu]

theo minh thi nen tao 1 tap hop de chua so nguyen to nho hon so n roi xet tong nhu ban da noi!!

[letien1993]

Nếu mệnh đề của Gôn-Bắc được chứng minh thì khỏe quá! Cứ output 2!
---------------------------------Bài viết đã được trộn ---------------------------------
Đây, mình xin cung cấp code sàng Eratosthenes

Procedure Eratosthenes(n: longint; var prime: array of boolean);
Var
i, j: longint;
Begin
Fillchar(prime, sizeof(prime), true);
prime[0]:=false; prime[1]:=false;
i:=2;
While (i*i<=n) do begin
if (prime) then begin
j:=i*i;
While (j<=n) do Begin
prime[j]:=false;
j:=j+i;
End;
End;
inc(i);
End;
End;