Originally posted by 09520019
View Post
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
-
Originally posted by 11520145 View PostDạ đ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
Để 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:
-
Originally posted by 08520059 View PostLạ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:
-
Originally posted by 11520145 View PostVậ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.
...
.
.
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:
-
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:
-
Originally posted by 10520080 View Postcho 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 .
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:
-
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:
-
Originally posted by 08520059 View PostChỉ đư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ỷ.
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:
-
Originally posted by 08520001 View PostHok 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à
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:
-
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:
-
Originally posted by 07520004 View PostCò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ỉ
Đề 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:
-
Originally posted by 07520004 View PostCòn cái chỗ thời gian chạy test thử chưa em. 1s chạy đủ không
Leave a comment:
Leave a comment: