Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 11 kết quả

Đề tài: Có bao nhiêu giá trị của một tổng cho trước

  1. #1
    Ngày gia nhập
    03 2010
    Bài viết
    9

    Question Có bao nhiêu giá trị của một tổng cho trước

    Đề bài:
    Nhập vào n và k (n,k < 500)
    Sau đó, tiếp tục nhập với n số nguyên ứng với n số đã nhập phía trên

    In ra, có bao nhiêu cách để dãy số đạt giá trị là K

    Ví dụ
    5 10 (n = 5 và k = 10)
    1
    2
    3
    7
    8

    In ra số cách: 3
    (1,2,7 - 2,8 - 3,7)

    Có bác nào cho mình cái ý tưởng hoặc thuật toán được không?
    Xin chân thành cám ơn

  2. #2
    Ngày gia nhập
    08 2010
    Nơi ở
    Home-Hà Đông
    Bài viết
    51

    Mình mới chỉ nghĩ ra cách là kiểm tra toàn bộ các tổng, có 2^n tổng nên độ phức tạp là 2^n nên lớn quá. Không biết có cách nào tối ưu hơn không.

  3. #3
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Phân tích 10 thành tổng m số bé hơn nó (m <= n). So sánh, và in. Để tối ưu, nên lấy giá trị lớn gần k nhất của dãy nhập vào để làm chặn trên.
    P/s: Nếu 1 phần tử xuất hiện trong nhiều tập số, nhưng không xuất hiện trong dãy số cho trước. Ta loại bỏ tất cả các tập số này.

    Cmt Code:
    1. n = 5 ;k = 10)
    2. input: {1 2 3 7 8}
    3. => max = 8;
    4.  
    5. Phân tích ngược:
    6. 10 = 8 + 2;
    7. 10 = 5 + 3 + 2; // Không có 5 trong input, => bỏ.
    8. 10 = 7 + 3
    9. 10 = 7 + 2 + 1
    10. 10 = 4 + 3 + 2 + 1 // Không có 4 trong input, => bỏ.
    11.  
    12. Vậy ta có:
    13. 10 = 8 + 2;
    14. 10 = 7 + 3
    15. 10 = 7 + 2 + 1
    Update: Để tối ưu hơn nữa khi so sánh tập số, ta nên sort trước dãy nhập vào, rồi dùng binary search. :]
    Đã được chỉnh sửa lần cuối bởi doicanhden : 21-11-2012 lúc 09:21 PM.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  4. #4
    Ngày gia nhập
    02 2012
    Bài viết
    5

    f[i,j] là số cách tạo tổng i từ các phần tử 1->j
    nếu a[j]>i thì f[i,j]=f[i,j-1]
    nếu a[j]<=i thì f[i,j]=f[i,j-1]+f[i-a[j],j-1]
    kết quả là f[k,n]

  5. #5
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Trích dẫn Nguyên bản được gửi bởi kingrain94 Xem bài viết
    f[i,j] là số cách tạo tổng i từ các phần tử 1->j
    nếu a[j]>i thì f[i,j]=f[i,j-1]
    nếu a[j]<=i thì f[i,j]=f[i,j-1]+f[i-a[j],j-1]
    kết quả là f[k,n]
    Có vẻ hay đấy. Nhưng tôi chưa hiểu một chỗ. Làm sao tính được f[i, j] ?
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  6. #6
    Ngày gia nhập
    02 2012
    Bài viết
    5

    Mặc định Có bao nhiêu giá trị của một tổng cho trước

    Trích dẫn Nguyên bản được gửi bởi doicanhden Xem bài viết
    Có vẻ hay đấy. Nhưng tôi chưa hiểu một chỗ. Làm sao tính được f[i, j] ?
    for (long i=1;i<=k;i++)
    for (long j=1;j<=n;j++)
    if (a[j]<=i) f[i][j]=f[i][j-1]+f[i-a[j]][j-1];
    else f[i][j]=f[i][j-1];
    Đã được chỉnh sửa lần cuối bởi kingrain94 : 21-11-2012 lúc 11:33 PM.

  7. #7
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Trích dẫn Nguyên bản được gửi bởi kingrain94 Xem bài viết
    for (long i=1;i<=k;i++)
    for (long j=1;j<=n;j++)
    if (a[j]<=i) f[i][j]=f[i][j-1]+f[i-a[j]][j-1];
    else f[i][j]=f[i][j-1];
    :| Bạn code thử xem, khởi tạo phần tử f[0][0] là giá trị gì mà cứ f[i][j - 1]? Giá trị nó là cái quái gì?
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  8. #8
    Ngày gia nhập
    12 2009
    Nơi ở
    The country of happiness
    Bài viết
    182

    bài này QHD như kingrain94 là đúng rồi, check công thức thôi :d
    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    Ôi skill của mình đã đạt đến hàng tuyệt đỉnh
    Không chỉ ăn, tắm, đi lại có thể code
    Mà giờ đã mình có thể code cả khi ngủ. Code tạm vào buffer của não, lúc nào dậy chỉ việc viết ra một cách trôi chảy không lưỡng lự.
    PS: Nếu ngủ dài rảnh rảnh có thể debug luôn, dậy chỉ việc build ?
    Trích dẫn Nguyên bản được gửi bởi vietanh8286 Xem bài viết
    Lập trình viên giỏi là lập trình viên có vợ

  9. #9
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Trích dẫn Nguyên bản được gửi bởi doicanhden Xem bài viết
    :| Bạn code thử xem, khởi tạo phần tử f[0][0] là giá trị gì mà cứ f[i][j - 1]? Giá trị nó là cái quái gì?
    Giá trị khởi tạo của mảng QHĐ tùy thuộc vào định nghĩa công thức truy hồi.

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  10. #10
    Ngày gia nhập
    02 2012
    Bài viết
    5

    code đây bạn:
    #include<iostream>
    #define nmax 500
    using namespace std;
    long n,k,a[nmax],f[nmax][nmax];
    main()
    {
    cin>>n>>k;
    for (long i=1;i<=n;i++) cin>>a[i];
    for (long i=1;i<=k;i++)
    for (long j=1;j<=n;j++) f[i][j]=0;
    for (long j=0;j<=n;j++) f[0][j]=1;
    for (long i=1;i<=k;i++)
    for (long j=1;j<=n;j++)
    if (a[j]<=i) f[i][j]=f[i][j-1]+f[i-a[j]][j-1];
    else f[i][j]=f[i][j-1];
    cout<<f[k][n]<<endl;
    }

Các đề tài tương tự

  1. Gà đông tảo giá bao nhiêu?
    Gửi bởi pirate91 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 11-12-2013, 09:50 PM
  2. nhà hẻm 7m Nhiêu Tứ, dt 113 m2- 4 tỷ, Hướng Bắc
    Gửi bởi nadareal trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 23-06-2012, 11:03 AM
  3. Bài tập C++ đếm xem có bao nhiêu số thỏa mãn
    Gửi bởi nguyenhuanvp trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 07-12-2011, 07:01 PM
  4. Kỹ thuật C Viết hàm đếm có bao nhiêu ký tự hoa , bao nhiêu ký tự thường
    Gửi bởi tyrant trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 10-09-2010, 10:58 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn