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

Đề tài: tìm tổng con lớn nhất

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    1

    Mặc định tìm tổng con lớn nhất

    Cho dãy số nguyên a[1], a[2], …, a[n]. Dãy số a[i], a[i+1], …, a[j] với 1 ≤ i ≤ j ≤ n được gọi là dãy con của dãy số đã cho. Viết chương trình tìm dãy con co tổng a[i]+ a[i+1]+ …+ a[j] là lớn nhất.
    Bà con giúp mình giải bài này với nhé!

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài này không khó, nhưng trước khi giúp bạn, mình muốn hỏi bạn nếu cho 1 dãy số 10 số thôi, đặt trường hợp bạn giải tay thì bạn sẽ làm sao ?^^

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Hic, bạn vẫn không suy nghĩ ra à ? Thôi mình giúp bạn lần này, mình nghĩ chắc bạn cũng mới học thôi, thực ra hồi mới gặp bài này mình cũng suy nghĩ phức tạp lắm ^^ nhưng suy nghĩ 1 hồi thì thấy nó không khó đâu :
    Ý tưởng là ta dùng 1 biến tổng ( ở đây mình gl SUM )
    SUM = SUM + A[_th];
    Bạn tính từ phần từ đầu đến phần tử cuối dãy, nếu dãy toàn dương thì không nói nữa rồi, tổng lớn nhất chính = tổng tất cả các phần tử .Nhưng nếu bây h nó có phần tử âm thì sao ? Ta tạo thêm 1 biến nữa chạy song song để xét tổng này, nếu nó nhỏ hơn tức là : ta không nhận phần tử này , và cắt chỗ này, ví dụ :
    1 2 3 4 5 6 -7 8 9 10
    Lúc này ta có thông tin dãy có tổng là 1 SUM nào đó, bây h xét tiếp thì dãy mới sẽ là 1 2 3 4 5 6 -7 8 9 10
    và tiếp nữa : 1 2 3 4 5 6 -7 8 9 10...
    Cứ dần lên như thế và xong !
    PHP Code:
    #include <iostream>
    #include <iomanip>

    using namespace std;

    long int A[1000];
    long int maxxSUM;
    int firstElement
        
    lastElement
             
    int lengthSeries;
    void Input()
    {
        
    cout << "Enter the length of Series: ";
        
    cin >> lengthSeries;

        for ( 
    int i 1<= lengthSeriesi++ )
        {
            
    cin >> A[i];
        }
    }

    void TheBiggestSumSolve()
    {
        
    int tmp;
        
    firstElement 1;  //phần tử khởi đâừ và 
        
    lastElement 1;  //phần tử cuối của dãy cần tìm
        
    tmp 1;

        
    maxx = -10000;
        for ( 
    int _th 1_th <= lengthSeries_th++ )
        {
            
    SUM SUM A[_th];
            if ( 
    SUM maxx 
            {
                
    maxx SUM;
                
    firstElement tmp
                
    lastElement _th;
            }
            if ( 
    SUM )
            {
                
    SUM 0;
                
    tmp _th 1;
            }
        }
    }

    void Output()
    {
        for ( 
    int i firstElement<= lastElementi++ )
        {
            
    cout << A[i] << setw(4);
        }
        
    cout << "\n";
        
    cout << "Its sum is : " << maxx;
    }

    int main()
    {      
        
    Input();
        
    TheBiggestSumSolve();
        
    Output();
        return 
    0;


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

  1. Sửa máy tính, cài đặt windows, phần mềm tại nhà nhanh nhất, rẻ nhất, hiệu quả nhất …
    Gửi bởi hopluccc 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: 08-07-2013, 02:07 PM
  2. Trả lời: 12
    Bài viết cuối: 25-10-2012, 02:48 AM
  3. Bài tập C++ NHập mảng một chiều gồm n phần tử kết thúc nhập khi nhập một chữ cái
    Gửi bởi thienthanoze trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 15
    Bài viết cuối: 09-07-2012, 10:10 PM
  4. Bài tập C++ Viết phương trình nhập vào 1 chuỗi số.Hãy nhập vào 1 số.Đếm xem có bao nhiêu chữ số bạn vừa nhập
    Gửi bởi namtuocdn trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 16-10-2011, 10:39 AM
  5. Bài tập C++ Nhập mảng 1 chiều, nếu phần tử nhập trùng nhau thì bắt nhập lại
    Gửi bởi danielh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 09-07-2011, 03:35 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