Announcement

Collapse
No announcement yet.

Phân tích số N thành tổng của các số tự nhiên liên tiếp,liệt kê tất cả các cách có th

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • 11520145
    replied
    Originally posted by 09520019 View Post
    Đã liệt kê tất cả các cách mà độ dài dãy số là mấy trăm ngàn mà em muốn chạy nhanh thì em nên chuyển qua khoa toán tin của trường ĐH KHTN đi em.

    Để tính số cách thì ng` ta có công thức, và tính mẹo 1 cách nào đó, còn bắt buộc phải liệt kệ các cách đó thì trong TH nhanh nhất, thời gian liệt kê = số cách liệt kê
    Số cách liệt kê lại là hàm có liên quan tới C(m,n) , mà đã liên quan tới C(m,n) thì không tránh khỏi độ phức tạp giai thừa.
    Hà - Thanks Anh

    Leave a comment:


  • 09520019
    replied
    Originally posted by 11520145 View Post
    Dạ điều kiện thì em nghĩ độ dài dãy số khoảng trăm mấy ngàn hoặc mấy trăm ngàn ạ - nếu không được thì nhiều nhất có thể là bao nhiêu anh
    Đã liệt kê tất cả các cách mà độ dài dãy số là mấy trăm ngàn mà em muốn chạy nhanh thì em nên chuyển qua khoa toán tin của trường ĐH KHTN đi em.

    Để tính số cách thì ng` ta có công thức, và tính mẹo 1 cách nào đó, còn bắt buộc phải liệt kệ các cách đó thì trong TH nhanh nhất, thời gian liệt kê = số cách liệt kê
    Số cách liệt kê lại là hàm có liên quan tới C(m,n) , mà đã liên quan tới C(m,n) thì không tránh khỏi độ phức tạp giai thừa.
    Last edited by 09520019; 03-11-2011, 21:47.

    Leave a comment:


  • 11520145
    replied
    Originally posted by 08520059 View Post
    Lại thêm một bài không có giới hạn.

    Mấy bài liệt kê kiểu này thường mình vét cạn là ok, đối với bài này thì vét O(n*2^m) liệt kê ra C(m,n) (tổ hợp chập n của m) cách, m là chiều dài dãy, n <= m <= 20.
    Dạ điều kiện thì em nghĩ độ dài dãy số khoảng trăm mấy ngàn hoặc mấy trăm ngàn ạ - nếu không được thì nhiều nhất có thể là bao nhiêu anh

    Leave a comment:


  • 08520059
    replied
    Originally posted by 11520145 View Post
    Vậy cho em hỏi cái này luôn ạ :
    cho 1 dãy số và 1 số n, Hãy tìm các cách tính tổng với n số hạng.
    ...
    .
    .
    Lại thêm một bài không có giới hạn.

    Mấy bài liệt kê kiểu này thường mình vét cạn là ok, đối với bài này thì vét O(n*2^m) liệt kê ra C(m,n) (tổ hợp chập n của m) cách, m là chiều dài dãy, n <= m <= 20.

    Leave a comment:


  • 11520145
    replied
    Vậy cho em hỏi cái này luôn ạ :
    cho 1 dãy số và 1 số n, Hãy tìm các cách tính tổng với n số hạng.
    VD : n=3
    1 2 3 4 5 6
    1+2+3
    1+2+4
    1+2+5
    ...
    2+4+5
    ...
    hoặc n =4
    1+2+3+4
    ...
    1+3+4+6

    Leave a comment:


  • 08520348
    replied
    Originally posted by 10520080 View Post
    cho em hỏi cái bài này tý.......code Java nhá mấy anh chị....
    nhập số N nguyên dương (max 100000).phân tích ra tổng các số nguyên tố sao cho số số hạng là ít nhất
    Thank all .
    Ý của em về bài này là nhập 1 số nguyên dương bất kỳ vào, và tìm tổng các số nguyên tố bằng số nguyên dương đó sao cho số số hạng là ít nhất đúng không. Nếu đề bài là vậy thì anh có cách làm sau:
    B1: Lưu tất cả các số nguyên tố trong giới hạn đó vào mảng a giảm dần.
    B2: Xét lần lượt từ số lớn nhất trở đi và cộng dần theo ý tưởng sau: x*a[0]+y*a[1]+z*a[2]+...+u*a[n-1] với x=N/a[0] ; y=(N-x*a[0])/a[1] ; z=(N-(x*a[0]+y*a[1]))/a[2] ... và n là số phần tử trong mảng. Đây là ý tưởng theo cách tham lam là ưu tiên chọn bội số của số lớn nhất cho đến khi đạt kết quả. Bài này tương tự bài tập chia tiền trong môn Phân tích và thiết kế thuật toán của khoa CS học kỳ 6.
    Bạn nào có ý tưởng hay và ngắn gọn hơn thì xin nêu lên để mọi người cùng tham khảo!

    Leave a comment:


  • 07520004
    replied
    Originally posted by 10520080 View Post
    cho em hỏi cái bài này tý.......code Java nhá mấy anh chị....
    nhập số N nguyên dương (max 100000).phân tích ra tổng các số nguyên tố sao cho số số hạng là ít nhất
    Thank all .
    Đã có thread về bài này rồi em.

    Leave a comment:


  • 10520080
    replied
    cho em hỏi cái bài này tý.......code Java nhá mấy anh chị....
    nhập số N nguyên dương (max 100000).phân tích ra tổng các số nguyên tố sao cho số số hạng là ít nhất
    Thank all .

    Leave a comment:


  • 09520019
    replied
    Originally posted by 08520059 View Post
    Chỉ đưa ra độ phức tạp không thôi thì lấy gì mà học. , Văn An nhỉ.

    Dựa trên công thức anh Thương, có 1 cách tìm b nhanh mà không cần duyệt từ 1 -> N là tìm kiếm nhị phân đoạn [1,N]. Nhưng vẫn không sáng sủa gì cho lắm khi độ phức tạp vẫn còn cao O(NlogN). 15 tỷ.
    Thôi để nói luôn. Cách tà đạo thì dùng bên Toán học (bọn đi thi IMO ấy), có đáp án là công thức tổng quát cho phương trình
    ax^2 + by^2 + cxy + dx + ey + f = 0 (pt 2)
    pt2 này được phát triển từ pt1 sau đây:
    x^2 - Dy^2 = 1 (pt1)
    tên của pt1 là Pell's equation, cách giải các bạn có thể google.
    Công thức nghiệm dựa vào đây tăng hàm mũ (x = cái gì đó mũ m...) nên độ phức tạp O(log (x))
    Đó là vì sao bài 4 của post này http://forum.uit.edu.vn/showthread.php?t=2041, bài cuối cùng, mình chỉ for i = 1 to 24 do ....

    Leave a comment:


  • 08520059
    replied
    Originally posted by 08520001 View Post
    Hok biết thì học em ah. Các topic được lập ra để mọi người học hỏi lẫn nhau mà
    Chỉ đưa ra độ phức tạp không thôi thì lấy gì mà học. , Văn An nhỉ.

    Dựa trên công thức anh Thương, có 1 cách tìm b nhanh mà không cần duyệt từ 1 -> N là tìm kiếm nhị phân đoạn [1,N]. Nhưng vẫn không sáng sủa gì cho lắm khi độ phức tạp vẫn còn cao O(NlogN). 15 tỷ.
    Last edited by 08520059; 26-10-2011, 00:38.

    Leave a comment:


  • 08520001
    replied
    Hok biết thì học em ah quan ao nu. Các topic được lập ra để mọi người học hỏi lẫn nhau mà
    Last edited by 08520001; 18-04-2015, 23:29.

    Leave a comment:


  • 11520026
    replied
    Toàn siêu nhân! Nhìn e chả biết chút gì... hi

    Leave a comment:


  • 09520019
    replied
    Originally posted by 07520004 View Post
    Còn cái chỗ thời gian chạy test thử chưa em. 1s chạy đủ không


    Chuyển N từ vế trái qua thành một phương trình bậc nhất theo b, ẩn là a.
    Cho vòng for a chạy tới N rồi tính b, b là số thì quất ra, chắc là nhanh hơn nhỉ
    Độ phức tạp giải thuật lúc đó là O(N^1/2) nên chắc là nhanh hơn ^^
    Đề này có giới hạn 1 tỷ như anh Văn An đề xuất là ổn, chứ ko có giới hạn thì phải xài mẹo....mà mẹo thì ko có hay ho ^^ (mặc dù độ phức tạp O(log N) thôi)

    Leave a comment:


  • 08520521
    replied
    Originally posted by 11520126 View Post
    Hở ???? em nhầm chỗ nào hả ????
    Anh Thương mới đúng em ạ. )

    Leave a comment:


  • 11520126
    replied
    Originally posted by 07520004 View Post
    Còn cái chỗ thời gian chạy test thử chưa em. 1s chạy đủ không
    Pascall ko tính toán time chạy chương trình anh à, mà em nhẩm chắc cũng ko quá 1s đâu, nhấp Run cái ra kq liền. Nhập vào 10^9 thì: Invalid floating point operation.

    Leave a comment:

LHQC

Collapse
Working...
X