Come as guests, stay as family.

I ♥ 4MGHC


Hướng dẫn sử dụng diễn đàn Với mong muốn có một Website hỏi đáp chất lượng 4MGHC đã ra đời. Đây là cộng đồng hỏi đáp dành cho lập trình viên, sinh viên, các bạn ưu thích lập trình... Việt Nam. Huy vọng các bậc tiền bối, các bằng hữu gần xa chung tay chia sẽ, giúp đỡ, giải đáp các thắc mắc trên Website. Cùng nhau củng cố, đóng góp cho sự nghiệp phát triển thông tin, công nghệ của đất nước.
Trong diễn đàn bạn có thể
  1. Hỏi đáp trong diễn đàn
  2. Đánh giá và like bài post
Đăng ký

Số người đang xem trên diễn đàn: 1098
1
  1. Tân thế giới
    Posts:
    784319
    Vote:
    2
    Like:
    4
    Tìm dãy con liên tiếp có tổng lớn nhất
    Image
    Image
    Users online on this topic: 1
    doantai1988
    Awaiting Email Confirmation
    Ngày gia nhập: 10 2009
    Bài viết: 3
    -------------------------
    Tìm dãy con liên tiếp có tổng lớn nhất
    BT tìm dãy con liên tiếp có tổng lớn nhất

    Code:
    Code: Select all

    void dayconlientiepcotongdainhat(int a[],int n)
    {
    int sum=0,dau,cuoi,max=sum-1,temp=0;
    for(int i=0;i<n;i++)
    {
    sum+=a[i];
    if(sum>max)
    {
    max=sum;
    dau=temp;
    cuoi=i;
    }
    if(sum<0)
    {
    temp=i+1;
    sum=0;
    }
    }
    for(i=dau;i<=cuoi;i++)
    cout<<a[i];
    cout<<endl<<max;
    }

    Test:

    n=7 4 -5 6 -4 2 3 -7

    n=4 0 -1 -2 -3

    n=4 -1 -2 -3 -4 ->sai nhưng nếu khai báo biến đầu hàm kiểu float thì lại đúng

    Mình ko hiểu tại sao lại như vậy?

    Bạn nào giải thích giúp với
    Image 0
    Image
  2. Ký Túc Xá
    Posts:
    2533979
    Vote:
    19
    Like:
    2
    Image
    Image
    butbi_pro
    Thành viên chính thức
    Ngày gia nhập: 04 2010
    Bài viết: 30
    -------------------------
    khởi tạo sum = a[0]

    sau đó vòng lặp chạy từ 1->n

    bạn thử sửa xem sao?
    __________________

    ...

    Và sao không là gió, là mây để thấy trời bao la?

    Và sao không là phù sa dâng mỡ màu cho hoa?

    Sao không là bài ca của tình yêu đôi lứa?

    Sao không là mặt trời gieo hạt nắng vô tư?

    ...
    Image 0
    Image
    Image
  3. Ký Túc Xá
    Posts:
    2533979
    Vote:
    19
    Like:
    2
    Image
    Image
    peterdrew
    Banned
    Ngày gia nhập: 01 2010
    Nơi ở: до свидания!
    Bài viết: 1,827
    -------------------------
    Trích dẫn:
    Nguyên bản được gửi bởi butbi_pro
    Quote: Select all

    khởi tạo sum = a[0]

    sau đó vòng lặp chạy từ 1->n

    bạn thử sửa xem sao?


    Dùng lặp duyệt từ 1->n thì coi như sai! (Bỏ).
    Image 0
    Image
    Image
  4. Ký Túc Xá
    Posts:
    2533979
    Vote:
    19
    Like:
    2
    Image
    Image
    doantai1988
    Awaiting Email Confirmation
    Ngày gia nhập: 10 2009
    Bài viết: 3
    -------------------------
    hic ktra lại rồi, dãy toàn số âm ra sai
    Image 0
    Image
    Image
  5. Ký Túc Xá
    Posts:
    2533979
    Vote:
    19
    Like:
    2
    Image
    Image
    peterdrew
    Banned
    Ngày gia nhập: 01 2010
    Nơi ở: до свидания!
    Bài viết: 1,827
    -------------------------
    Thấy cái này hay hay:

    PHP Code:
    Code: Select all


    summax=0;
    for(i=0,i<n,i++) //n là chặn trên của mảng.
    {
    sumtmp=0;
    for{j=i,j<n,j++)
    {
    sumtmp=sumtmp+a(j);
    if (sumtmp>summax)
    {
    summax=sumtmp;
    pos_start=i //Vị trí bắt đầu của dãy có tổng max.
    pos_end=j //Vị trí kết thúc của dãy có tổng max.
    }
    }
    }

    Image 0
    Image
    Image
  6. Ký Túc Xá
    Posts:
    2533979
    Vote:
    19
    Like:
    2
    Image
    Image
    doantai1988
    Awaiting Email Confirmation
    Ngày gia nhập: 10 2009
    Bài viết: 3
    -------------------------
    trích từ quyển sách Những viên ngọc trong kỹ thuật lập trình của Jon Bentley

    Algorithms2:O(N2)

    Tổng a[L..U]= Tổng a[L..U-1]+a[U]

    Code:
    Code: Select all

    maxsofar=0;
    for (L=1;L<=n;L++)
    {
    sum=0;
    for (U=L;U<=n;U++)
    {
    sum=sum+a[U];
    maxsofar=max(maxsofar,sum);
    }
    }

    thuật toán này sẽ sai nếu nhập dãy toàn số âm

    với lại độ phức tạp là O(N^2) mà mình đang làm btap tối ưu hóa cấu trúc
    Image 0
    Image
    Image
  7. Ký Túc Xá
    Posts:
    2533979
    Vote:
    19
    Like:
    2
    Image
    Image
    trihn_kt
    Thành viên nhiệt tình
    Ngày gia nhập: 09 2009
    Nơi ở: 205Bee
    Bài viết: 231
    -------------------------
    Mình đóng góp code cái. Loằng ngoằng quá

    C++ Code:
    Code: Select all

    Lựa chọn code | Ẩn/Hiện code
    #include <iostream>

    using namespace std;

    int tong(int a[], int left, int right)
    {
    return left==right ? a[left] : a[left]+tong(a, left+1, right);
    }

    int main()
    {
    int a[100], n;
    cin >> n;
    for (int i=0; i<n; ++i)
    cin >> a[i];

    int max = a[0], max1;
    int imax = 0, jmax = 0;

    for (int i=0; i<n; ++i)
    for (int j=i; j<n; ++j)
    {
    if(i==0 && j==n-1)continue;
    max1 = tong(a, i, j);
    if(max1 > max) {max = max1; imax = i; jmax = j;}
    }

    cout << "\nDay ban dau: ";
    for (int i=0; i<n; ++i)
    cout << a[i] << " ";

    cout << "\nDay con co tong max: ";
    for (int i=imax; i<=jmax; ++i)
    cout << a[i] << " ";
    cout << "\nn = " << max;
    system("pause");
    }
    Image 0
    Image
    Image
  8. Ký Túc Xá
    Posts:
    2533979
    Vote:
    19
    Like:
    2
    Image
    Image
    doantai1988
    Awaiting Email Confirmation
    Ngày gia nhập: 10 2009
    Bài viết: 3
    -------------------------
    Code:
    Code: Select all

    void tongmax(int a[],int n)
    {
    int dau,cuoi=0,sum=0,max=a[0];
    for(int i=0;i<n;i++)
    {
    sum +=a[i];
    if(sum>max)
    {
    max=sum;
    cuoi=i;
    }
    if(sum<0)
    {
    dau=i+1;
    sum=0;
    }
    }
    cout<<"maxsofar= "<<max<<endl;
    for(i=dau;i<=cuoi;i++)
    cout<<a[i]<<" ";
    }
    Image 0
    Image
    Image
  9. Ký Túc Xá
    Posts:
    2533979
    Vote:
    19
    Like:
    2
    Image
    Image
    thanhbaton
    Thành viên mới
    Ngày gia nhập: 11 2011
    Bài viết: 11
    -------------------------
    cho dãy n pt. tìm dãy con m (m<=n) sao cho dãy tổng lớn nhất (liên tiếp nhau) trong mảng. hjx mình làm cái tìm dãy l
    C++ Code:
    Code: Select all

    Lựa chọn code | Ẩn/Hiện code
    int daylientiep(int A[20],int n)
    { for(int i=1;i<=n;i++)
    {
    if(A[i+1]-A[i]==1) return 0;

    else return daylientiep(A,n-1) ;
    if(A[i]-A[i+1]==1) return 0;
    else return daylientiep(A,n-1) ;
    }

    cout<<A[i]<<"\t"<<A[i+1];
    }
    Image 0
    Image
    Image
1