PDA

Xem phiên bản đầy đủ : 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



11520126
25-10-2011, 17:46
Em mới đào được bài này nè: 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ể có.
VD: N=9 thì có 2 cách
2+3+4
4+5
:D

08520001
25-10-2011, 18:27
Giới hạn N và thời gian bao nhiêu vậy em

áo chip triumph (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-triumph/ao-nguc-triumph/) quần lọt khe (http://doxinh.com.vn/danh-muc/do-lot-nu/quan-lot-nu/) dụng cụ tập ăn (http://doxinh.vn/danh-muc/do-dung-cho-be/dung-cu-tap-an/) áo sơ mi công sở (http://trangbanbuon.com/danh-muc/thoi-trang-cong-so/ao-so-mi-cong-so/) bán buôn quần áo các loại (http://trangbanbuon.vn/) đồ bơi trẻ em (http://doxinh.com/danh-muc/do-boi/do-boi-tre-em/) đồ lót nữ siêu mỏng (http://doxinh.com.vn/danh-muc/do-lot-nu/) khăn tã sơ sinh cho bé (http://doxinh.vn/danh-muc/do-so-sinh-cho-be/khan-va-ta-so-sinh/) bán buôn (http://trangbanbuon.com/) bán buôn (http://trangbanbuon.vn/) trang phục ca múa kịch (http://roses.vn/studio/cho-thue-trang-phuc/trang-phuc-ca-mua-kich/)

11520126
25-10-2011, 18:31
N nhập từ bàn phím anh à. Time ko giới hạn. Ủa mà sao ra topic riêng rùi ??

07520004
25-10-2011, 18:37
N nhập từ bàn phím anh à. Time ko giới hạn. Ủa mà sao ra topic riêng rùi ??

Admin hay mod move ra chứ còn sao nữa. Mà N nhập từ bàn phím là nhập số có giá trị bao nhiêu? Anh cứ đè phím số 9 trên bàn phím trong vòng 7 nốt nhạc là nó ra cũng khủng lắm đó.

11520126
25-10-2011, 18:54
thì anh cứ nhập đại thui, làm vui thui mà, có phải thi Olympic đâu anh @@!

07520004
25-10-2011, 19:00
thì anh cứ nhập đại thui, làm vui thui mà, có phải thi Olympic đâu anh @@!

Thì thằng Cao Văn An nó hỏi mà em không hiểu nên anh hỏi lại giùm nó thôi. Chứ anh chả quan tâm, anh làm được tới số mấy anh làm đề quy định kệ nó =))

08520001
25-10-2011, 19:07
Hi. Thường thì mỗi đề đều phải có giới hạn. Vì tùy vào giới hạn của đề mà có thuật toán tương ứng để giải hết giới hạn đó. Nếu ko ghi giới hạn thì giống như đề chưa hoàn chỉnh vậy ah. Anh có lập các topic, em có thể nghiên cứu thử xem.
quần lót triumph (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-triumph/quan-lot-triumph/) đồ lót nam (http://doxinh.com.vn/danh-muc/do-lot-nam/) dụng cụ tập ăn cho bé (http://doxinh.vn/danh-muc/do-dung-cho-be/dung-cu-tap-an/) áo sơ mi công sở nữ (http://trangbanbuon.com/danh-muc/thoi-trang-cong-so/ao-so-mi-cong-so/) thời trang công sở (http://trangbanbuon.vn/danh-muc/thoi-trang-cong-so/) đồ bơi nữ gợi cảm (http://doxinh.com/danh-muc/do-boi/do-boi-nu/) đồ lót nữ đẹp (http://doxinh.com.vn/danh-muc/do-lot-nu/) tã sơ sinh (http://doxinh.vn/danh-muc/do-so-sinh-cho-be/khan-va-ta-so-sinh/) quần áo bán buôn (http://trangbanbuon.com/) quần áo bán buôn (http://trangbanbuon.vn/) cho thuê trang phục chụp ảnh (http://roses.vn/studio/cho-thue-trang-phuc/)

07520352
25-10-2011, 19:15
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)

Cho 2 vòng for, 1 chạy a, 1 chạy b, nếu tích trên bằng n thì xuất ra dãy số từ a đến a + b.

Ví dụ, với n = 9 thì có 2 trường hợp:
a = 2, b = 2
hoặc
a = 4, b = 1

08520001
25-10-2011, 19:23
Mình đề nghị bài này giới hạn N <= 10^9 và thời gian là 1s. Mình nghĩ vậy sẽ khoa học hơn
quần lót (http://doxinh.com/) mỹ phẩm hàn quốc (http://doxinh.com/danh-muc/my-pham/) mỹ phẩm nam hàn quốc (http://doxinh.com/danh-muc/my-pham/my-pham-nam/) nước hoa hàng hiệu (http://doxinh.com/danh-muc/my-pham/nuoc-hoa/) đồ lót nam hàng hiệu (http://doxinh.com/danh-muc/do-lot-nam/) áo lót nam tay ngắn (http://doxinh.com/danh-muc/do-lot-nam/ao-lot-nam/) quần lót nam cá tính (http://doxinh.com/danh-muc/do-lot-nam/quan-lot-nam/) đồ lót nữ đẹp (http://doxinh.com/danh-muc/do-lot-nu/) bộ đồ lót nữ đẹp (http://doxinh.com/danh-muc/do-lot-nu/bo-do-nu/) áo chip (http://doxinh.com/danh-muc/do-lot-nu/ao-lot-nu/) quần lót nữ lọt khe (http://doxinh.com/danh-muc/do-lot-nu/quan-lot-nu/) váy ngủ (http://doxinh.com/danh-muc/do-lot-nu/do-ngu/) đồ lót gợi cảm (http://doxinh.com/danh-muc/do-lot-sexy/) áo ngực sexy (http://doxinh.com/danh-muc/do-lot-sexy/ao-lot-sexy/) quần lót sexy đẹp (http://doxinh.com/danh-muc/do-lot-sexy/quan-lot-sexy/) đồ ngủ sexy đẹp (http://doxinh.com/danh-muc/do-lot-sexy/do-ngu-sexy/) đồ lót độc (http://doxinh.com/danh-muc/do-lot-cao-cap/) áo ngực cao cấp (http://doxinh.com/danh-muc/do-lot-cao-cap/ao-lot-cao-cap/) quần ngực cao cấp (http://doxinh.com/danh-muc/do-lot-cao-cap/quan-lot-cao-cap/) đầm ngủ cao cấp (http://doxinh.com/danh-muc/do-lot-cao-cap/do-ngu-cao-cap/) đồ lót cao cấp (http://doxinh.com/danh-muc/thuong-hieu-do-lot/) áo ngực bon bon (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-bonbon/) áo ngực triumph (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-triumph/) áo ngực winny (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-winny/) áo ngực paltal (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-paltal/) áo ngực vera (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-vera/) áo ngực annie (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-annie/) quần áo nữ (http://doxinh.com/danh-muc/quan-ao-thoi-trang/) quần áo cao cấp (http://doxinh.com/danh-muc/quan-ao-thoi-trang/) quần áo nam cao cấp (http://doxinh.com/danh-muc/quan-ao-thoi-trang/quan-ao-nam/) quần áo nữ cao cấp (http://doxinh.com/danh-muc/quan-ao-thoi-trang/quan-ao-nu/) quần áo trẻ em nữ (http://doxinh.com/danh-muc/quan-ao-thoi-trang/quan-ao-tre-em/) đồ bơi 2 mảnh (http://doxinh.com/danh-muc/do-boi/) đồ bơi nam kiểu dài (http://doxinh.com/danh-muc/do-boi/do-boi-nam/) áo tắm bikini (http://doxinh.com/danh-muc/do-boi/do-boi-nu/) đồ bơi trẻ em nữ (http://doxinh.com/danh-muc/do-boi/do-boi-tre-em/) bộ sưu tập đồ lót vera (http://doxinh.com/bo-suu-tap/hang-vera.html) bộ sưu tập đồ lót winking (http://doxinh.com/bo-suu-tap/hang-winking.html) đồ xinh (http://doxinh.com/) đồ xinh (http://doxinh.com.vn/) đồ xinh (http://doxinh.vn/)

08520500
25-10-2011, 19:24
Đồng ý với bạn An.

08520500
25-10-2011, 19:29
Xin phép post một đề cho các bạn tham khảo :
Cho số nguyên dương N. Hãy cho biết có thể phân tích N thành tổng các số tự nhiên liên tiếp hay không? Nếu có hãy phân tích N thành tổng của các số tự nhiên liên tiếp với nhiều số hạng nhất có thể được.
Dữ liệu vào: cho trong File PTICH.INP gồm một số dòng, mỗi dòng ghi một số nguyên dương N (N <= 10^9)
Kết quả: ghi ra file PTICH.OUT theo cấu trúc sau:
+ Nếu N phân tích được thành tổng các số tự nhiên liên tiếp thì ghi chữ d sau đó là các số hạng trong cách phân tích đó, các số hạng ghi cách nhau một dấu cách, mỗi dòng ghi không quá 25 số.
+ Nếu N không phân tích được thì chỉ ghi chữ k.
Ví dụ:

PTICH.INP
12
8
PTICH.OUT
d: 3 4 5
k

11520126
25-10-2011, 19:43
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)

Cho 2 vòng for, 1 chạy a, 1 chạy b, nếu tích trên bằng n thì xuất ra dãy số từ a đến a + b.

Ví dụ, với n = 9 thì có 2 trường hợp:
a = 2, b = 2
hoặc
a = 4, b = 1
Thanks anh, giờ em mới hiểu bài này, em có cái đáp án mà ghi công thức gì á, ngẫm hoài ko hiểu, cách này có vẻ dễ hiểu hơn.

uses crt;
var n:longint; a,
i,m,dem,max:integer;

begin
clrscr;
Write('Nhap N = ');readln(n);
max:=trunc(sqrt(N*8+1)+1) div 2;
dem:=0;
For i:=2 to max-1 do

If ((N-i*(i-1)div 2) mod i = 0) then
begin
A:=(N-i*(i-1)div 2) div i;
inc(dem);
Writeln('Cach thu ',dem);
For m:=a to a+i-1 do
write(' ',m);
writeln;
end;


readln;
end.

08520604
25-10-2011, 19:47
Thanks chị, giờ em mới hiểu bài này, em có cái đáp án mà ghi công thức gì á, ngẫm hoài ko hiểu, cách này có vẻ dễ hiểu hơn.
=)) chào chị Thương ;)

11520126
25-10-2011, 19:49
=)) chào chị Thương ;)
Hở ???? em nhầm chỗ nào hả ????

07520004
25-10-2011, 19:50
Mình đề nghị bài này giới hạn N <= 10^9 và thời gian là 1s. Mình nghĩ vậy sẽ khoa học hơn


Thanks chị, giờ em mới hiểu bài này, em có cái đáp án mà ghi công thức gì á, ngẫm hoài ko hiểu, cách này có vẻ dễ hiểu hơn.

uses crt;
var n:longint; a,
i,m,dem,max:integer;

begin
clrscr;
Write('Nhap N = ');readln(n);
max:=trunc(sqrt(N*8+1)+1) div 2;
dem:=0;
For i:=2 to max-1 do

If ((N-i*(i-1)div 2) mod i = 0) then
begin
A:=(N-i*(i-1)div 2) div i;
inc(dem);
Writeln('Cach thu ',dem);
For m:=a to a+i-1 do
write(' ',m);
writeln;
end;


readln;
end.

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

08520001
25-10-2011, 20:16
Hi. Mình nghĩ giải với độ phức tạp O(căn N) là ok rồi ah.

áo ngực annie (http://doxinh.com/danh-muc/thuong-hieu-do-lot/hang-annie/ao-nguc-annie/) đồ lót nam gợi cảm (http://doxinh.com.vn/danh-muc/do-lot-nam/) bô cho bé các loại (http://doxinh.vn/danh-muc/do-dung-cho-be/bo-cho-be/) quần áo bán buôn (http://trangbanbuon.com/) vest công sở (http://trangbanbuon.vn/danh-muc/thoi-trang-cong-so/vest-cong-so/) đồ bơi nam cá tính (http://doxinh.com/danh-muc/do-boi/do-boi-nam/) quần áo nữ đẹp (http://doxinh.com.vn/danh-muc/quan-ao-thoi-trang/quan-ao-nu/) tất sơ sinh cho bé (http://doxinh.vn/danh-muc/do-so-sinh-cho-be/tat-so-sinh/) áo sơ mi công sở nữ (http://trangbanbuon.com/danh-muc/thoi-trang-cong-so/ao-so-mi-cong-so/) áo sơ mi công sở nữ (http://trangbanbuon.vn/danh-muc/thoi-trang-cong-so/ao-so-mi-cong-so/) chụp ảnh đám cưới (http://roses.vn/studio/chup-anh-studio/chup-anh-su-kien/)

11520126
25-10-2011, 20:22
Thử với cái giới hạn trên kia chưa :D
Chạy được tới 10^8 à. @@!

07520004
25-10-2011, 20:26
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
25-10-2011, 20:33
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
25-10-2011, 20:52
Hở ???? em nhầm chỗ nào hả ????

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

09520019
25-10-2011, 20:58
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
25-10-2011, 21:45
Toàn siêu nhân! Nhìn e chả biết chút gì... hi :rolleyes:

08520001
25-10-2011, 21:53
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à

đồ lót (http://doxinh.com/) đồ lót (http://doxinh.com.vn/) đồ sơ sinh (http://doxinh.vn/) bán buôn quần áo (http://trangbanbuon.com/) bán buôn quần áo (http://trangbanbuon.vn/) chụp ảnh cho bé (http://roses.vn/)

08520059
25-10-2011, 23:41
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. :mad:, 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). :p 15 tỷ.

09520019
26-10-2011, 10:04
Chỉ đưa ra độ phức tạp không thôi thì lấy gì mà học. :mad:, 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). :p 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
26-10-2011, 14:37
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
26-10-2011, 14:38
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
26-10-2011, 15:41
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
03-11-2011, 19:10
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
03-11-2011, 20:44
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. :confused:

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.

11520145
03-11-2011, 20:50
Lại thêm một bài không có giới hạn. :confused:

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

09520019
03-11-2011, 21:44
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.

11520145
03-11-2011, 21:58
Đã 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