Trang 1 / 5 1234 ... LastLast
Hiển thị kết quả từ 1 đến 10 / 42
  1. #1
    Tham gia
    23-02-2003
    Location
    Melbourne
    Bài viết
    5,201
    Like
    0
    Thanked 24 Times in 18 Posts

    Thuật toán xác định số chính phương?

    Có ai biết thuật toán dùng để xác định số chính phương ngắn gọn và hiệu quả không?

    Hiện nay tui được đề nghị 3 thuật toán :
    1. sqr(sqrt(n))=n
    2. round(sqrt(n))=sqrt(n)
    3. xác định trong lân cận [ [sqrt(n)]-1; [sqrt(n)]+1 ]: chỉ cần có một số nguyên trong lận cận đó bình phương lên bằng n thì n là số cp.

    3 thuật toán trên đều đúng trong trường hợp n là số Cp. Thuật toán 1 bị sai vì gần như lúc nào cho ra KQ n là số Cp. 2 thuật toán còn lại cũng bị sai khi n quá lớn. Tui đã thử trong Pascal, FreePascal, Delphi 7, Delphi for .NET, VB.NET, PHP (thử tt 1,2,3); VC++.NET (thử tt 1 và 3) với các kiểu longint, int64, uint64, qword.

    Có ai biết thuật toán nào khác ko?
    Quote Quote

  2. #2
    Tham gia
    05-07-2003
    Location
    sinh ngay 1 thang 1
    Bài viết
    73
    Like
    0
    Thanked 0 Times in 0 Posts
    nếu tổng các số mũ các thừa số nguyên tố của 1 số là lẻ thì nó là số chính phương.
    {có lẽ thuật toán này chạy hơi lâu ?}

  3. #3
    Tham gia
    05-07-2003
    Location
    sinh ngay 1 thang 1
    Bài viết
    73
    Like
    0
    Thanked 0 Times in 0 Posts
    chú ý là nếu chỉ cần nó có 1 thừa số nguyên tố có số mũ lẻ là coi như nó không phải là số chính phương.
    vd:9=1^1.3^2
    tổng các số mũ là lẻ nên nó là số chính phương
    10=2^1*x
    thừa số nguyên tố 2 có số mũ là lẻ nên ta lập tức loại.
    tôi nói tổng các thừa số nguyên tố của 1 số là lẻ thì nó là số chính phương là nếu có kể thêm số 1 (xin mọi người hiểu cho)

  4. #4
    Tham gia
    26-03-2003
    Location
    Hanoi
    Bài viết
    73
    Like
    0
    Thanked 0 Times in 0 Posts
    2 thuật toán đầu dựa trên sự so sánh 2 số thực, điều này không thể tin tưởng được. Vì việc so sánh này dựa trên sự lệch nhau 1 lượng nhỏ "chấp nhân được " , ngôn ngữ nào cũng vậy, có thể là 10 hay 20 csố sau dấu ,. Ngoài ra còn phụ thuộc độ chính xác của hàm sqrt.
    Thuật toán 3 tôi nghĩ là không sai, vì nó so sánh 2 số nguyên.
    Bạn có thể nói rõ nó sai theo kiểu nào được không, có cp báo không hay là ngược lại
    Đảm bảo không bao giờ sai là các thuật toán số học, nhưng lại rất chậm. Btw, phát biểu của xyxy là sai rồi, bạn thử giải thích số 3*5 và 3*5*7 xem nào

  5. #5
    Tham gia
    23-02-2003
    Location
    Melbourne
    Bài viết
    5,201
    Like
    0
    Thanked 24 Times in 18 Posts
    Đúng như Hasterisk nói, 2 tt đầu so sánh số thực nên không thể tin tưởng mặc dù tt 2 có vẻ rất đúng. Còn thuật toán 3 ko sai về lý thuyết (do chỉ so sánh số nguyên), nhưng nó lại bị lỗi trong thực tế do hàm sqrt (trả về số thực) khi xử lý ở những số rất lớn (cỡ khỏang ngàn tỷ trở lên). Tôi đã thử bằng cách tạo ra số Cp N bằng cách bình phương một số nguyên M. Khi M khỏang từ vài tỷ đến vài chục tỷ thì các tt bắt đầu chạy sai (lúc đúng lúc sai). Còn nếu dùng các thuật toán số học (ví dụ như cách thử từ 1->sqrt(N) ) thì nó lại chạy wa' chậm.

  6. #6
    Tham gia
    26-03-2003
    Location
    Hanoi
    Bài viết
    73
    Like
    0
    Thanked 0 Times in 0 Posts
    Có lẽ không phải sai ở thuật toán mà sai ở việc xử lý số nguyên lớn của các ngôn ngữ lập trình,kiểu 64 bit chỉ được đến khoảng 19 hay 20 csố, khi lấy vài chục tỷ bp lên thì chắc chắn bị overflow, kết quả không thể tính trước, thường là theo kiểu modulo, nghĩa là MAX+1 --> MIN

  7. #7
    Tham gia
    05-07-2003
    Location
    sinh ngay 1 thang 1
    Bài viết
    73
    Like
    0
    Thanked 0 Times in 0 Posts
    ý cậu là giải thích thế nào hả hasterik

  8. #8
    Tham gia
    26-03-2003
    Location
    Hanoi
    Bài viết
    73
    Like
    0
    Thanked 0 Times in 0 Posts
    Là giải thích theo kiểu tổng số mũ các thừa số nguyên tố làm sao cho 2 số đó đều o phải số cphương

  9. #9
    Tham gia
    29-08-2002
    Location
    Long An
    Bài viết
    47
    Like
    0
    Thanked 1 Time in 1 Post
    Theo mình nghĩ nên cho biến i chạy từ 1 đến số đó. Nếu i^2=n thì n là số cp
    Có thể chia số n ra làm nhiều phần rồi chạy biến i

  10. #10
    Tham gia
    23-02-2003
    Location
    Melbourne
    Bài viết
    5,201
    Like
    0
    Thanked 24 Times in 18 Posts
    Hasterisk có thể giải thích cụ thể hơn được ko?

    To minhhuu: Thuật toán số học mà bạn đề nghị chạy rất chậm, ở đây đang cần tìm một tt nhanh và chính xác.

Trang 1 / 5 1234 ... LastLast

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
  •