Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Phân tích số

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Phân tích số   Tue 27 Jul 2010, 13:31

Hãy đếm số cách phân tích số N ( N<=100000 ) thành tổng các số nguyên dương.
Lưu ý 2 cách chỉ khác nhau về thứ tự các số hạng được coi là giống nhau. Ví dụ 4 có 5 cách phân tích sau:
4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 1 + 3
4 = 2 + 2
4 = 4

Hai cách phân tích 4 = 1 + 3 = 3 + 1 chỉ được tính một lần.
Vì kết quả sẽ rất lớn nên các bạn chỉ cần đưa ra phần dư của phép chia số cách tìm được cho 1000000000 ( 10^9 ).
Input

Một số tự nhiên N duy nhất.
Output

In ra phần dư của của số cách tìm được cho 10^9.
Example

Input:
4

Output:
5
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Phân tích số   Wed 28 Jul 2010, 11:24

f[i,j]=f[i-1,j]+f[i,j-a[i]]

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Phân tích số   Wed 28 Jul 2010, 15:36

Đó là cách cơ bản.Chỉ chạy được các test cơ bản thôi.Bạn cần phải tối ưu từng đoạn code.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Phân tích số   Thu 29 Jul 2010, 18:00

Ý anh là sao. Mà cũng công nhận cách đó cơ bản nhất laughing

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Phân tích số   Thu 29 Jul 2010, 22:26

Với mỗi k thì ta có công thức tính P(k) qua các P(k-1),P(k-2),... rồi; tính xong thì lưu vào một mảng. Với mỗi k thì P(k) liên quan đến các số P(k-1/2i*(3i+/-1)) nghĩa là các số 1/2*i*(3i+/- 1) phải tính đi tính lại nhiều lần nên tính trước các số như vậy và lưu vào mảng để khi nào cần sử dụng thì ko phải tính lại.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Phân tích số   Fri 30 Jul 2010, 11:21

Thì tất nhiên là QHD mà laughing .

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Phân tích số   Fri 30 Jul 2010, 14:49

Quy hoạch động là đúng.Nhưng bạn chưa tối ưu từng đoạn code.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Phân tích số   Fri 30 Jul 2010, 17:23

Anh nói kĩ hơn đi. Cái anh nói trên em chả hiểu chi hết

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Phân tích số   Fri 30 Jul 2010, 21:52

Anh đọc trên Trang này

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Sponsored content




Bài gửiTiêu đề: Re: Phân tích số   Today at 21:32

Về Đầu Trang Go down
 
Phân tích số
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến