pp hàm sinh (gerneration function )

298 lời bình

*
zeroman89 says:
October 24, 2009 at 2:34 am

Mọi người giúp em tìm một generating function cho bài toán sau với:
Có N đồng xu có giá trị 1, 2, 3, …, N. Đếm số lượng tập con K phần tử có tổng bằng N.
Giới hạn: N\le 1000 000 000, K \le 10

Tiện thể, mọi người cho em hỏi có cuốn nào hay về generating funtion và các ứng dụng của nó thì giới thiệu cho em với.
Thanks in advance !
*
Ngô Quang Hưng says:
October 28, 2009 at 8:58 am

@zeroman89,

khai triển g(x,t) = \prod_{i=1}^N (1+x^it) và lấy hệ số của x^Nt^K.

Tuy nhiên, giải pháp này chỉ có giá trị lý thuyết. Tôi nghĩ Mathematica sẽ không chạy nổi nếu bạn bảo nó Expand đa thức trên. Cách có lẽ khả thi hơn là dùng dynamic programming: gọi a[n, k, s] là tổng số các tập con kích thước k của [n] = \{1, 2, \cdots, n\} với tổng bằng s. Sau đó viết một công thức đệ quy cho a[n,k,s]. Dùng memoization (cộng với indexing) thì sẽ tốt hơn là tính từ dưới lên vì máy tính của bạn sẽ không chứa nổi cái dãy 3 chiều này.

Bạn Google vấn đề “subset sum enumeration” xem có heuristic nào hay hơn không.

Sách enumerative combinatorics thì tôi đã giới thiệu ở đây. Generating functions dùng để định trị một hàm số nào đó: đếm các đối tượng rời rạc, tính xác suất, moments, vân vân. nói chung là nhiều ứng dụng.

One Response to “pp hàm sinh (gerneration function )”

  1. vanchanh123 Says:

    Xem hàm sinh của Anh Chương cho


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: