Trang 2 của 5 Đầu tiênĐầu tiên 1234 ... CuốiCuối
Kết quả 11 đến 20 của 47
  1. #11
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    cảm ơn bạn nhiều. mình ghi nhầm bạn ạ.ý mình ở đây là 10^5 và có thể lớn hơn nữa đó bạn...mình học hỏi được được bạn rất nhiều..

  2. #12
    Ngày tham gia
    Nov 2015
    Bài viết
    3
    nhờ bạn gửi nguyên chương trình với thuật toán tối ưu nhất cho minh với..thank ban nhiều

  3. #13
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    mình phải công nhận bạn nắm rất chắc kiến thức thức lập trình.cảm ơn bạn nhiều..cho mình hỏi thêm luôn nếu theo thuật toán của bạn thì mình có thể in ra được các số pp trong đoạn từ left to right ko bạn.

  4. #14
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    mình in được các số pp trong đoạn đó rồ. hiện tại đang nghiên cứu thuật toán của bạn.có j ko hiểu mình sẽ hỏi bạn..mong bạ giúp đỡ.thank bạn nhiều

  5. #15
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    nhờ bạn giải thích lại nguyên lý của thuật toán được không ak.mình ngồi phân tích một chút thấy vẫn lang mang quá..nhờ bạn nói rõ lại thuật toán 1 chút cũng giống như bài xóa số cho mình với......

  6. #16
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    Phần quan trọng nhất trong thuật toán đó là mảng 'sum', nên mình bắt đầu vào mảng này luôn nhé.
    Mã:
    sum[J] = tổng các ước số của số J >= 2, không tính chính nó.
    (Kết quả của bài toán thì chỉ việc duyệt mảng 'sum', xem coi sum[J] > J hay không).

    Nếu I là ước của J (hoặc nói cách khác, J là bội của I), thì ta có thể tính được:

    Mã:
    sum[J] = sum[J] + I.
    (mình đặt I và J như vậy cho nó gần với đoạn code mình viết để dễ theo dõi)

    Tới chỗ này là sự khác biệt của thuật toán dùng mod với thuật toán mình ghi đây. Đó là thứ tự của I và J.
    - Ở thuật toán dùng mod: chúng ta làm việc với ước của J (duyệt I tìm xem J mod I = 0).
    - Ở thuật toán này: chúng ta làm việc với bội của I (dùng trực tiếp J = 2*I, 3*I, 4*I,...). Tại mỗi bội số của I, ta đều cộng vào mảng 'sum' tại chỗ đó giá trị của I.

    (I+I, I+I+I, I+I+I+I,.... đều là bội số của I cả).

    Khởi tạo mảng 'sum' là 1, tượng trưng cho ước số 1. Như vậy tại mỗi bước I, ta cộng tất cả các bội số J của I một giá trị là I.

    Ví dụ: với right = 12:

    Ban đầu ta có:
    Mã:
    index  2  3  4  5  6  7  8  9  10  11  12
    sum    1  1  1  1  1  1  1  1   1   1   1
    Bắt đầu từ I = 2, bội số của 2 ko tính nó là J = 4, 6, 8, 10, 12. Mình sẽ cộng vào mảng 'sum' tại những vị trí đó giá trị I = 2.
    Mã:
    index  2  3  4  5  6  7  8  9  10  11  12
    sum    1  1  3  1  3  1  3  1   3   1   3
    I = 3, bội số của 3 ko tính nó là J = 6, 9, 12. Mình sẽ cộng vào mảng 'sum' tại những vị trí đó giá trị I = 3.
    Mã:
    index  2  3  4  5  6  7  8  9  10  11  12
    sum    1  1  3  1  6  1  3  4   3   1   6
    I = 4, bội số của 4 ko tính nó là J = 8, 12. Mình sẽ cộng vào mảng 'sum' tại những vị trí đó giá trị I = 4.
    Mã:
    index  2  3  4  5  6  7  8  9  10  11  12
    sum    1  1  3  1  6  1  7  4   3   1  10
    Nhìn lại một chút, chúng ta thấy giá trị hiện tại của sum[12] là 10, tượng trưng cho 1 + 2 + 3 + 4 (đều là ước của 12 cả). Tiếp tục cho tới I = 12 thì sẽ điền đc đủ hết tổng các ước số từ 2 tới 12. Đặc điểm của thuật toán này là J nhảy theo bội số mà ko cần đi từng từ phần tử một như cách tìm ước số, bởi vậy độ phức tạp giảm đi, và chương trình chạy nhanh hơn.

  7. #17
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi vansonqtqb
    nhờ bạn gửi nguyên chương trình với thuật toán tối ưu nhất cho minh với..thank ban nhiều
    Về bộ nhớ (space):
    - Nếu bạn dùng Turbo Pascal với N lớn tới hàng trăm ngàn hay hơn nữa thì chỉ có thể dùng cách tìm ước rồi tổng của mấy ước đó theo kiểu div, mod bình thường thôi bởi vì Pascal bị giới hạn bộ nhớ (16-bit), ko thể trade bộ nhớ cho tốc độ được.
    - Nếu bạn dùng Free Pascal thì cách của mình vẫn chạy được. Khi đó mấy biến chạy là phải longint hết, và có thể dùng mảng kích cỡ lớn.

    Về tốc độ:
    - Thuật toán mình viết cho bạn có độ phức tạp là O(n log n), khá là tối ưu rồi. Mình chỉ biết còn 1 cách nữa tối ưu hơn xíu (về tốc độ) sử dụng sàng nguyên tố, nhưng nó phức tạp hơn và nói thật, có 1 chỗ mình cũng chưa biết viết thế nào cho đẹp (mình ko phải ngành computer science).

  8. #18
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    ak.mình có ý kiên nhỏ thế này. ko biết bạn nghĩ sao. mình thấy ở đây ta có thế duyệt vòng lặp i thứ 2 đến div 2 là được. không biết ý kiến bạn thế nào?

  9. #19
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi vansonqtqb
    ak.mình có ý kiên nhỏ thế này. ko biết bạn nghĩ sao. mình thấy ở đây ta có thế duyệt vòng lặp i thứ 2 đến div 2 là được. không biết ý kiến bạn thế nào?
    Cám ơn bạn. Vòng lặp i bên ngoài đúng là bạn có thể duyệt tới 'right / 2' là được, ko cần tới 'right' như mình đã ghi. Còn vòng j thì cần giữ nguyên.

  10. #20
    Ngày tham gia
    Aug 2015
    Bài viết
    1
    ý của mình đây
    for i := 2 to b do
    sum[i] := 1;
    for i := 2 to (b div 2) do

 

 
Trang 2 của 5 Đầu tiênĐầu tiên 1234 ... CuốiCuối

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • 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
  •  
Múi giờ GMT +7. Bây giờ là 10:18 AM.
Diễn đàn sử dụng vBulletin® Phiên bản 4.2.5.
Bản quyền của 2024 vBulletin Solutions, Inc. Tất cả quyền được bảo lưu.
Ban quản trị không chịu trách nhiệm về nội dung do thành viên đăng.