Trang 2 / 15 FirstFirst 123457 ... LastLast
Hiển thị kết quả từ 11 đến 20 / 148
  1. #11
    Tham gia
    17-10-2007
    Location
    Hà Nội
    Bài viết
    758
    Like
    0
    Thanked 8 Times in 7 Posts
    Nếu muốn tăng tốc phần kiểm tra tính nguyên tố của một số thì có thể dùng nhận xét:
    - Xét dãy gồm các số -1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31...
    Số thứ 2n = số thứ 2n-1+6 và số thứ 2n+1= số thứ 2n+2
    - Người ta đã chứng minh được dãy trên chứa tất cả các số nguyên tố (trừ 2 và 3) và một số hợp số khác (không nhiều lắm). Do đó khi xét tính nguyên tố của một số ta chỉ cần kiểm tra xem số đó có chia hết cho 3 và mọi số trong dãy (nhỏ hơn số đó) không

    Còn nếu muốn liệt kê các số nguyên tố thì có thể có hướng dùng các cách sau
    - Sử dụng Sàng Eurathosten (chẳng hiểu tôi viết tên có đúng không nhỉ?) bằng cách dùng một mảng đánh dấu, nhưng do dung lượng mảng cho phép trong Turbo Pascal khá ít nên bạn nào đã biết dữ liệu động có thể sử dụng cấu trúc này để tăng số phần tử
    - Có thể lưu lại các số nguyên tố đã tìm được vào một mảng rồi khi cần tìm số mới thì thử chia cho các số nguyên tố đã tìm được
    Có gì sai sót mong các bạn góp ý
    Được sửa bởi mr_invincible lúc 20:08 ngày 18-01-2008

  2. #12
    Tham gia
    17-10-2007
    Location
    Hà Nội
    Bài viết
    758
    Like
    0
    Thanked 8 Times in 7 Posts
    Tôi xin góp thêm cho các bạn một thuật toán sắp xếp cũng khá đơn giản (hình như tên là Straight Selection)
    - Giả sử có mảng số thực tên là a, số phần tử là n:
    Procedure SapXep;
    Var
    i,j:integer;
    tg:real;
    Begin
    For i:=1 to n-1 do
    For j:=i+1 to n do
    If a[i]>a[j] then
    begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; end; {Đổi chỗ 2 số}
    End;
    Độ phức tạp của thuật toán này và Bubble Sort là tương đương nhau
    Ý tưởng của thuật toán Sắp xếp nhanh (Quick Sort)
    - Chia dãy thành 2 nửa, lấy điểm giữa làm mốc, sắp xếp lại các số trong dãy sao cho các số nhỏ hơn mốc nằm về một phía, các số lớn hơn mốc nằm về phía còn lại, lặp lại bước này đến khi toàn bộ dãy đã được sắp xếp tăng
    Còn chương trình mẫu thì bạn chungkid đã nói rồi
    - Độ phức tạp O(n log n)
    - Ngoài ra, còn có rất nhiều thuật toán sắp xếp khác (insertion sort, merge sort, heap sort...). Mỗi thuật toán sắp xếp đều có ưu điểm và nhược điểm riêng của nó. Bạn nào quan tâm có thể tham khảo trong các tài liệu về pascal (tôi cũng chẳng biết sách nào, các bạn chịu khó tự tìm mua nhé)

    Có gì sai sót mong các bạn góp ý

  3. #13
    Tham gia
    14-10-2007
    Location
    ô hay, đến từ đâu thì kệ người ta chứ :p
    Bài viết
    112
    Like
    0
    Thanked 19 Times in 7 Posts
    Lâu lắm mới nghía vô diễn đàn, đọc bài này cũng thấy hay hay, khá là có ích đối với những người mới lập trình nhưng mà ngay cái #1 đã có vấn đề rồi nè mà không ai phát hiện ra
    Tức là cái viết ra ma trận theo hàng và cột đó, của bạn chung ghi thế thì chưa nó còn báo lỗi cú pháp trước khi ghi ra sai ấy chứ
    Code:
    for i:=1 to m do begin
        for j:=1 to n do 
          write(a[i],' ');
        writeln;
      end;
    => lỗi trầm trọng
    phải sửa thành là :
    Code:
     for i:=1 to m do
         begin
               for j:=1 to n do
                   write(a[i,j],' ');
               writeln;
         end;
    <-- thấy sai chưa


    Tiện thể ghi luôn cách nhập ma trận m hàng n cột từ bàn phím ( hồi mới học cũng mãi mới hiểu lúc nào thì phẩy trên mà lúc nào thì phẩy dưới )

    Code:
    write('nhap m: '); readln(m);
    write('nhap n: '); readln(n);
    for i:=1 to m do
        for j:=1 to n do
            begin
                  write('A[',i,',',j,']= '); readln(a[i,j]);
            end;


    (@chungkid : cơ mà đây là tranh thủ lúc đợi máy diệt virut đó, không bình thường thì "Nu, pogodi!" , gõ mấy dòng mà sắp đông tay lại rùi đây nè )

  4. #14
    Tham gia
    14-10-2007
    Location
    ô hay, đến từ đâu thì kệ người ta chứ :p
    Bài viết
    112
    Like
    0
    Thanked 19 Times in 7 Posts
    Tiếp nào, đã có sắp xếp thì phải có tìm kiếm chứ nhỉ, để tui bắt đầu với bài toán tìm kiếm đơn giản và cơ bản nhất nhá : Tìm xem số x có mặt trong mảng a gồm n phần tử hay không :
    Code:
    function kt(x:integer):boolean;
     var i:integer;
     begin
          kt:=true;
          for i:=1 to n do
              if a[i]=x then exit;
          kt:=false;   
     end;
    ngoài ra, đối với mảng đã sắp xếp, người ta sẽ tìm kiếm nhị phân ( BSearch thì phải - cũng không bít nhớ có đúng không nữa )
    ý tưởng cơ bản của thuật toán chia đôi không gian tìm kiếm, xét xem x thuộc nửa nào rồi tiếp tục chia đôi không gian đó ra cho đến khi gặp phần tử = x hoặc không tìm thấy phần tử nào = x trong không gian tìm kiếm

    Và thêm nữa là tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng .
    Mấy vấn đề này, thực ra em cũng chỉ biết sơ sơ, không am hiểu lắm nên mong được mọi người chỉ giáo !


    (@chungkid: tay hoá đá rồi nà, thế này thì mai chắc phải ngồi cạnh cái lò có cái chảo trong có một số thứ ấm ấm rồi ; T_T : 75% - 372 viruts )

  5. #15
    Tham gia
    14-03-2007
    Bài viết
    57
    Like
    0
    Thanked 8 Times in 4 Posts
    Sorry bà con,mấy hôm nay bận ko post được,với lại kiến thức có hạn,nghĩ mãi chả biết post gì,hôm nay chỉ post được hai cách tính x^y(x lũy thừa y)
    Cách 1:Viết hàm
    Cách này dễ nhất,ai cũng có thể nghĩ ra,nhưng tôi cứ post vào đây cho bài nó
    dài(^.^)
    Code:
      Function GT(x,y:integer):Longint;
      Var 
        i:integer;
        s:longint;
      Begin
          s:=1;
          for i:=1 to y do
            s:=s*x;
          gt:=s;
      End;
    rồi,rất dễ phải ko
    Cách hai:
    x^y=exp(y*ln(x))
    biểu thức exp(y*ln(x)) sẽ trả về một giá trị real,nếu bạn cần giá trị nguyên có thể dung hàm trunc()
    CHÚ Ý:Tôi đang bí chả biết post gì,vì vậy kêu gọi anh em có biết gì hãy post vào đây để cho các bạn mới học có thể tham khảo,ko cần lập topic trong forum

  6. #16
    Tham gia
    08-01-2006
    Location
    Hà Nội
    Bài viết
    318
    Like
    0
    Thanked 3 Times in 2 Posts
    - Gửi ChungKid:
    Bạn ui, longint rất dễ bị tràn, đặc biệt là trong phép tính lũy thừa hay giai thừa. Có thể khắc phục bằng cách xài real hoặc extended, tuy nhiên hai kiểu dữ liệu này đều thuộc loại gần đúng nên nếu xài với số lớn thì không nên tin tưởng. (tui cũng không nhớ là C hay Pascal, trước tui có thử round(0.7 + 0.3) = 1 nhưng trunc(0.7 + 0.3) = 0, lý do là 0.7 + 0.3 không bằng 1.0 mà thực ra là bằng 0.(9))
    Cách tốt nhất là dùng phương pháp nhân số lớn, có thể lưu trong mảng hoặc danh sách liên kết. Thường lưu trong mảng là đủ, nếu thích có thể xài danh sách liên kết cho chủ động cũng được ^^.
    Còn điểm này nữa, với r kiểu real và i kiểu integer thì phép gán r:= i * 2000000000 gây lỗi tràn số, mặc dù giới hạn của real rất lớn (vì i kiểu integer, 2 tỷ kiểu longint, kết quả phép nhân trả về kiểu longint, với i > 2 kết quả vượt quá giới hạn của longint)
    - Gửi Cashier:
    Binary Search chỉ áp dụng được với mảng đã sắp xếp thui
    Ngoài ra còn có phương pháp cây tìm kiếm nhị phân và cây tìm kiếm cơ số, nhưng hai cách này thường chẳng ai áp dụng vì khá khó nhớ và không cần thiết (tìm kiếm trong khoảng vài chục hay vài trăm phần tử mà cài 2 cách này thì quả là... phí phạm ^^)
    - Gửi... mọi người :
    Về quicksort:
    Code:
    const
      MAX = 10000;
    var
      x: integer;
      a: array[1..MAX] of integer;
    procedure qSort(l: integer; r: integer);
    var
      i: integer;
      j: integer;
      tg: integer;
    begin
      x:= a[l + random(r - l + 1)];
      i:= l;
      j:= r;
      repeat
        while (a[i] < x) do inc(i);
        while (a[j] > x) do dec(j);
        if (i <= j) then 
        begin
          tg:= a[i];
          a[i]:= a[j];
          a[j]:= tg;
        end;
      until i >= j;
      if (i < r) then qSort(i, r);
      if (j > l) then qSort(l, j);
    end;
    Ngoài quick sort còn có merge sort, chạy khá hiệu quả. Tư tưởng của merge sort như vầy:
    - Với 2 dãy đã sắp xếp tăng dần, việc "trộn" 2 dãy để dãy kết quả cũng tăng dần là khá dễ dàng: so sánh phần tử đầu tiên trong 2 dãy, phần tử nào nhỏ hơn thì đẩy vào dãy kết quả, "dồn toa" lên. Cứ như vậy cho đến lúc hết dãy.
    - Có thể áp dụng phương pháp trên với n dãy tăng dần: tương tự như quick sort, phân đoạn ra sắp xếp, rồi trộn 2 đoạn cạnh nhau lại, cuối cùng có một dãy tăng dần.

    Bàn một chút về sorting nhá . Mặc dù có khá nhiều phương pháp sắp xếp, nhưng bubble sort vẫn được nhiều người sử dụng nhất vì rất rất dễ nhớ, dễ hiểu cho mọi người, kể cả với người mới học. Và giới hạn yêu cầu thường chỉ vài chục hay nhiều lắm là vài trăm trong các bài toán thông thường, nên với bubble sort O(n^2) là chấp nhận được.

    Lâu không code nên có thể có sai sót, nhờ mọi người chỉ giúp -'______'-.


    P/s: Cashier ui, bạn học lớp 11 ah, giờ mình mới để ý cái chữ ký trắng của bạn đấy. "Đồng cảnh ngộ" nè ^^

  7. 2 thành viên Like bài viết này:


  8. #17
    Tham gia
    14-10-2007
    Location
    ô hay, đến từ đâu thì kệ người ta chứ :p
    Bài viết
    112
    Like
    0
    Thanked 19 Times in 7 Posts
    hum nọ vừa làm một bài toán là cho số n m tìm căn bậc n của a thế nên phải làm một hàm tính m mũ n ( với số lớn - đương nhiên )
    post lên đây mong các bạn góp ý :
    Code:
    function cong_2_xau(st1,st2:string):string;
     var i,so1,so2,nho:byte;
         sai:integer;
         kq,tam:string;
     begin
          nho:=0; kq:='';
          while length(st2)<length(st1) do st2:='0'+st2;
          while length(st2)>length(st1) do st1:='0'+st1;
          for i:= length(st2) downto 1 do
              begin
                   val(st1[i],so1,sai);
                   val(st2[i],so2,sai);
                   str((so1+so2+nho) mod 10,tam);
                   kq:=tam+kq;
                   nho:=(so1+so2+nho) div 10;
              end;
          if nho<>0 then
             begin
                  str(nho,tam);
                  kq:=tam+kq;
             end;
          cong_2_xau:=kq;
     end;
    function nhan_xau_so(st1,st2:string):string;
     var i,so1,so2,nho:byte;
         sai:integer;
         kq,tam:string;
     begin
          nho:=0; val(st2[1],so2,sai);
          kq:='';
          for i:= length(st1) downto 1 do
              begin
                   val(st1[i],so1,sai);
                   str((so1*so2+nho) mod 10,tam);
                   kq:=tam+kq;
                   nho:=(so1*so2+nho) div 10;
              end;
          if nho<>0 then
             begin
                  str(nho,tam);
                  kq:=tam+kq;
             end;
          nhan_xau_so:=kq;
     end;
    function nhan_so_so (st1,st2:string):string;
     var i:byte;
         kq:string;
     begin
          kq:='';
          for i:=1 to length(st2) do
              begin
                   kq:=cong_2_xau(kq+'0',nhan_xau_so(st1,st2[i]));
              end;
          nhan_so_so:=kq;
     end;
    function tinh(m:longint; n:byte):string;
     var st,kq:string;
         i:byte;
     begin
          str(m,st);
          kq:=st;
          for i:=1 to n-1 do
              kq:=nhan_so_so(kq,st);
          tinh:=kq;
     end;
    ý tưởng cơ bản của mình là nhân số m n lần, với mỗi lần nhân mình thực hiện phép nhân 2 số lớn , mà phép nhân 2 số lớn thực hiện như theo thực hiện tay là nhân với từng số một rồi cộng vào
    Mình đã chạy và ra kết quả đúng nhưng gọi là số lớn mà cái của mình thì chỉ chạy với số mà ra kết quả có nhiều nhất 255 kí tự ( vì dùng xâu mà ) tức là chỉ cỡ 10^255 hoặc là 2147483647 ^ 30
    Còn chuyển sang DLLK thì xem chừng phải thay đổi lại thuật toán
    Mong các bạn góp ý thêm

    @Master_Baby : Bạn tinh thật đấy, không ngờ vẫn có người chú ý và đọc được ( chắc tại "đồng cảnh ngộ " ), mà sao bạn biết mình học lớp 11 zậy, hay quá ( chắc cũng lại .. ) Dù sao cũng rất vui được bít thêm 1 người " đồng cảnh ngộ "

  9. #18
    Tham gia
    17-10-2007
    Location
    Hà Nội
    Bài viết
    758
    Like
    0
    Thanked 8 Times in 7 Posts
    Quote Được gửi bởi cashier View Post
    ý tưởng cơ bản của mình là nhân số m n lần, với mỗi lần nhân mình thực hiện phép nhân 2 số lớn , mà phép nhân 2 số lớn thực hiện như theo thực hiện tay là nhân với từng số một rồi cộng vào
    Còn chuyển sang DLLK thì xem chừng phải thay đổi lại thuật toán
    Mong các bạn góp ý thêm
    Dùng Danh sách liên kết thì cũng vậy thôi, cũng nhân theo từng chữ số rồi cộng vào là được mà

  10. #19
    Tham gia
    03-01-2004
    Bài viết
    903
    Like
    0
    Thanked 10 Times in 7 Posts
    Thân gửi bạn cashier,

    Tui thấy cái hàm nhan_xau_so bạn viết phức tạp quá: để nhân a cho m thì chỉ cần cộng a cho chính nó (m-1) lần là được rồi

    Nói giỡn chút vậy thôi . Tui có thử tính 2^800 => tính khá nhanh
    Tuy nhiên nếu tui tính 100 lần liên tiếp như vậy (bỏ vô vòng lặp) thì thấy mất khoảng 20 giây .

    Viết như bạn là đạt yêu cầu rồi.
    Nhưng tui thử sửa lại 1 chút => tính "2^800" 100 lần liên tiếp tốn khoảng 5 giây

    Để tính a^1234 thì bạn cần làm 1233 phép nhân (a với chính nó)
    Mình có thể làm ít phép nhân hơn như sau:

    a^1234 = ((((((a^1)^10).(a^2))^10).(a^3))^10).(a^4)
    => sẽ cần làm khoảng (10+2+10+3+10+4) = 39 phép nhân

    (điều này tương tự như: để tính a*1234 thì mình không cần làm tới 1234 phép cộng mà chỉ cần làm ít hơn nhiều)

    Để tính lũy thừa với số mũ bất kỳ thì mình chỉ cần có 1 hàm để tính lũy thừa với số mũ nhỏ hơn hay bằng 10. Điều này cũng tương tự như: để làm phép nhần với 1 số bất kỳ thì mình chỉ cần có 1 hàm để làm phép nhân với 1 số nhỏ hơn hay bằng 9 (nhân với 10 thì quá dễ rồi cho nên không cần có 1 hàm)

    Mình còn có thể làm nhanh hơn 1 chút nữa: để tính lũy thữa với số mũ nhỏ hơn hay bằng 10 => phân tích số mũ ra cơ số 2

    (hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

    -thân
    Được sửa bởi bete lúc 13:43 ngày 01-01-2008

  11. #20
    Tham gia
    02-01-2008
    Bài viết
    1
    Like
    0
    Thanked 0 Times in 0 Posts
    phân tích một số ra thừa số nguyên tố
    không biết đã ai biết chưa? mình mới tham gia 4rum mà:



    program nguyento;
    uses crt;
    var i,n:integer;
    S:char;
    BEGIN
    repeat
    clrscr;
    write('n:='); readln(n);
    Write(n,'=');
    while n>1 do
    begin
    i:=2;
    while (n mod i) <>0 do
    inc(i);
    Write(i);
    n:= n div i;
    if n>1 then
    write('*');
    end;
    Writeln;
    Write('Co lam tiep hay khong?(Y/N)');
    S:=readkey;
    until S='n';
    readln;



    END.

Trang 2 / 15 FirstFirst 123457 ... LastLast

Tags for this Thread

Bookmarks

Quy định

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
  •