Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: Thuật toán bài dãy số

  1. #1
    Ngày gia nhập
    07 2012
    Bài viết
    0

    Mặc định Thuật toán bài dãy số

    Cho một dãy số gồm n số nguyên dương. Xác định xem có tồn tại một dãy số liên tiếp mà sao cho tổng của chúng bằng k.

    Các anh/chị giúp em thuật toán với ạ ?

  2. #2
    Ngày gia nhập
    02 2012
    Nơi ở
    hà nội
    Bài viết
    58

    C Code:
    1. int kt(int a[],int n,int k)
    2. {
    3. int i,j;
    4. int tong;
    5. for(i=0;i<n;i++)
    6. {
    7. tong=a[i];
    8. for(j=i+1;j<n;j++)
    9. {
    10. tong+=a[j];
    11. if(tong==k) return 1;// trong day co day so nguyen duong con co tong bang k
    12. else{
    13. if(tong>k) break;
    14. }
    15. }
    16. }
    17. return 0; //ko co day so nguyen duong con co tong bang k
    18. }
    Đã được chỉnh sửa lần cuối bởi kienquach : 29-11-2012 lúc 04:39 PM. Lý do: Bổ sung.
    + Quách Việt Kiên
    + Yahoo: Kaka_8x_vn
    + skype: kiencuongno1
    + Gmail: kiencuongno1@gmail.com
    Ai có thể free cho mình 50k thẻ điện thoại ko.

  3. #3
    Ngày gia nhập
    07 2012
    Bài viết
    0

    Trích dẫn Nguyên bản được gửi bởi kienquach Xem bài viết
    C Code:
    1. int kt(int a[],int n,int k)
    2. {
    3. int i,j;
    4. int tong;
    5. for(i=0;i<n;i++)
    6. {
    7. tong=a[i];
    8. for(j=i+1;j<n;j++)
    9. {
    10. tong+=a[j];
    11. if(tong==k) return 1;// trong day co day so nguyen duong con co tong bang k
    12. }
    13. }
    14. return 0; ko co day so nguyen duong con co tong bang k
    15. }
    Với trường hợp này:
    n=4
    3
    5
    6
    7
    k=15
    thì code trên không đúng ạ.

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

    gọi s[i] là tổng của các phần tử từ 1 -> i . Tổng của 1 dãy con liên tiếp ( i, j ) bất kỳ của dãy được tính bằng s[j] - s[i-1]. Như vậy bài toán được đưa về cho dãy số tăng s[1], s[2], ..., s[n], hỏi có tồn tại cặp chỉ số (i, j) với i < j và s[j] - s[i-1] = k hay không.

    Bạn có thể giải trong O(n) nếu giá trị s[i] là nhỏ , hoặc O(nlogn) nếu giá trị s[i] lớn ( sử dụng stl map hoặc stl set hoặc binary search .... )
    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ợ

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

    Cảm ơn thuật toán trên.
    Bạn có thể cho mình ví dụ về một bài có O(nlogn) được không ?

  6. #6
    Ngày gia nhập
    02 2012
    Nơi ở
    hà nội
    Bài viết
    58

    Cool Thuật toán bài dãy số

    Trích dẫn Nguyên bản được gửi bởi babylearntcode Xem bài viết
    Với trường hợp này:
    n=4
    3
    5
    6
    7
    k=15
    thì code trên không đúng ạ.
    Bạn xem lại cái đề của bạn đi. " Xác định xem có tồn tại một dãy số liên tiếp mà sao cho tổng của chúng bằng k". cái dãy kia lấy đâu ra dãy con liên tiếp có tổng bằng 15
    + Quách Việt Kiên
    + Yahoo: Kaka_8x_vn
    + skype: kiencuongno1
    + Gmail: kiencuongno1@gmail.com
    Ai có thể free cho mình 50k thẻ điện thoại ko.

  7. #7
    Ngày gia nhập
    02 2012
    Nơi ở
    hà nội
    Bài viết
    58

    còn nếu bạn muốn lấy ra 1 dãy con có tổng bằng k, thì bạn dùng thuật toán quy hoạch động. bài này có cách giải trên mạng đó chịu khó tim đi.
    + Quách Việt Kiên
    + Yahoo: Kaka_8x_vn
    + skype: kiencuongno1
    + Gmail: kiencuongno1@gmail.com
    Ai có thể free cho mình 50k thẻ điện thoại ko.

  8. #8
    Ngày gia nhập
    07 2012
    Bài viết
    0

    Trích dẫn Nguyên bản được gửi bởi kienquach Xem bài viết
    Bạn xem lại cái đề của bạn đi. " Xác định xem có tồn tại một dãy số liên tiếp mà sao cho tổng của chúng bằng k". cái dãy kia lấy đâu ra dãy con liên tiếp có tổng bằng 15
    Mình nhầm chỗ đó
    Ví dụ:
    n=6
    1
    2
    3
    5
    6
    7
    thì nếu theo thuật toán của bạn thì k=5 sẽ không tồn tại.

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

    C Code:
    1. int KiemTraCon(int a[],int n,int vt,int l, int k)
    2. {
    3.        int s=0;
    4.        for(int i=0;i<l;i++)
    5.             s=s+a[i+vt];
    6.        if(s==k)
    7.             return 1;
    8.        return 0;
    9. }
    10.  
    11. int KiemTraTatCa(int a[],int n, int k)
    12. {
    13.       int flag=0;
    14.       for(int l=1;l<=n;l++)
    15.            for(int vt=1;vt<=n-l;vt++)
    16.            {
    17.                   if(KiemTraCon(int a[],int n,int vt,int l, int k)==1)
    18.                          flag=1
    19.            }
    20.       return flag;
    21. }

  10. #10
    Ngày gia nhập
    02 2012
    Nơi ở
    hà nội
    Bài viết
    58

    Trích dẫn Nguyên bản được gửi bởi babylearntcode Xem bài viết
    Mình nhầm chỗ đó
    Ví dụ:
    n=6
    1
    2
    3
    5
    6
    7
    thì nếu theo thuật toán của bạn thì k=5 sẽ không tồn tại.
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. int kt(int a[],int n,int k)
    4. {
    5. int i,j;
    6. int tong;
    7. for(i=0;i<n;i++)
    8. {
    9. tong=a[i];
    10. for(j=i+1;j<n;j++)
    11. {
    12. if(tong==k) return 1;// trong day co day so nguyen duong con co tong bang k
    13. else{
    14. if(tong>k) break;
    15. }
    16. tong+=a[j];
    17. }
    18. }
    19. return 0; //ko co day so nguyen duong con co tong bang k
    20. }
    21. int main()
    22. {
    23.     int a[]={1,2,3,5,6,7};
    24.     int n=6,k=5;
    25.     if(kt(a,n,k)) printf("Co ton tai day con lien tiep co tong=5");
    26.     else printf("ko ton tai!");
    27.     getch();
    28. }
    ko biết bạn như nào chứ mình chạy ok mà. Mih thêm 1 tý cho tối ưu.
    Theo như bài mình viết thì
    1+2+3> 5 => break;
    2+3=5 thỏa mãn return 1;
    Đã được chỉnh sửa lần cuối bởi kienquach : 30-11-2012 lúc 01:40 AM.
    + Quách Việt Kiên
    + Yahoo: Kaka_8x_vn
    + skype: kiencuongno1
    + Gmail: kiencuongno1@gmail.com
    Ai có thể free cho mình 50k thẻ điện thoại ko.

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

  1. Dịch thuật, công ty dịch thuật, dịch vụ dịch thuật chuyên nghiệp
    Gửi bởi vecvn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 4
    Bài viết cuối: 18-11-2012, 10:44 PM
  2. Dịch vụ kế toán: Báo cáo thuế, dịch vụ tư vấn thuế, báo cáo thuế tncn vnnp
    Gửi bởi ecomvnnp01 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 16-02-2012, 11:07 AM
  3. Bài tập C++ Viết chương trình nhập số lượng hàng hóa, giá cả, thuế, xuất ra tổng giá, thuế, tổng cộng
    Gửi bởi seit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 04-03-2011, 09:04 AM
  4. Hướng dẫn kê khai thuế thu nhập cá nhân, thuế doanh nghiệp 0903034381
    Gửi bởi thngxanhcty 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: 19-05-2010, 02:33 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