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

[08520001]

Hi. Mình nghĩ giải với độ phức tạp O(căn N) là ok rồi ah. do lot nam.

[11520126]

Thử với cái giới hạn trên kia chưa

Chạy được tới 10^8 à. @@!

[07520004]

Chạy được tới 10^8 à. @@!

Còn cái chỗ thời gian chạy test thử chưa em. 1s chạy đủ không

a + (a + 1) + (a + 2) + ... + (a + b)
= (b + 1) * a + (1 + 2 + ... + b)
= (b + 1) * a + b * (b + 1) / 2
= (b + 1) * (a + b/2)

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ỉ

[11520126]

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.

[08520521]

Hở ???? em nhầm chỗ nào hả ????

Anh Thương mới đúng em ạ. )

[09520019]

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)

[11520026]

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

[08520001]

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à

[08520059]

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ỷ.

[09520019]

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 ....

[10520080]

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 .

[07520004]

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.

[08520348]

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!

[11520145]

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

[08520059]

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.