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

Đề tài: bài tập C++ về đoạn tăng trong mảng 1 chiều

  1. #1
    Ngày gia nhập
    02 2008
    Bài viết
    1

    Unhappy bài tập C++ về đoạn tăng trong mảng 1 chiều

    bài tập C++
    a. Viết chương trình nhập vào một mảng 1 chiều, sau đó tìm xem trong mảng có
    đoạn tăng nào có số phần tử nhiều nhất.
    b. Viết chương trình nhập vào một mảng 1 chiều, sau đó tìm xem trong mảng có
    đoạn tăng nào có tổng lớn nhất.
    các huynh giải giúp bài này

  2. #2
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Gợi ý chút nhé:
    1.
    count=0;
    temp=0;
    Kiểm tra hai phần tử liên tiếp A[i] < A[i+1], nếu thỏa mãn thì temp++.
    ngược lại nếu temp> count thì update lại count=temp; và temp=0 ; cho lần đếm sau.
    Làm công việc cho đến hết chuỗi.
    Có thể đặt hai flags để đánh dầu đầu và cuối đoạn.
    Bài này trước mình làm rùi, mà tìm không thấy code để đâu.
    Tại lâu quá rùi.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  3. #3
    Ngày gia nhập
    03 2008
    Bài viết
    78

    - Mình có ý kiến thế này (chỉ ứng khẩu thành code thôi nhé)..mong bạn tư duy dùm mình xem nó khả thi hay ko.Bị zì lâu wá nên cũng wên...

    + Thứ nhất thường dạng bài của bạn (2 câu luôn) làm mình liên tường đến Qui Hoạch Động.

    + Gọi F[i] là chiều dài dãy con liên tiếp tăng(ko giảm) nhiều nhất khi ta có i phần tử đầu tiên để chọn.Khi đó F[n] chính là kết quả của bài toán
    + Công thức truy hồi:
    @ F[0] = 1 vì chỉ có một thằng thôi chính nó là nhìu nhứt còn jì.

    @ Duyệt mảng A ban đầu từ i=1>>n-1.Nếu (A[i]>=A[i-1]) thì F[i] = F[i-1] + 1 ngược lại thì F[i]=1;
    + Cuối cùng duyệt mảng F tìm ra phần tử lớn nhất trong F.Khi đó giá trị F[i] chính là đô dài của dãy con tăng có độ dài nhiều nhất.Lần ngược lại ta in ra dãy con đó dễ dàng
    Xong thử test nhanh đi,bài 2 thì bạn thêm đk vào cho nó lọc ra.

    Sai thì bạn nêu ra để mình edit lại nhé.Ba lớn mau wên lắm!
    Đã được chỉnh sửa lần cuối bởi hacker_mubaohiem : 13-03-2008 lúc 08:47 AM.
    No way, No success..

  4. #4
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Bạn xem thêm tài liệu giải thuật của tác giải Lê Minh Hoàng nha. 2 bài toán của bạn thuộc loại giải thuật qui hoạt động
    Không biết ghi gì luôn ...

  5. #5
    Ngày gia nhập
    03 2008
    Bài viết
    78

    Đây là bài làm của mình đây: Qui Hoạch Động (ý tưởng ở trên nhé)
    - Lưu ý: Mảng F[] khởi gán bằng 0;
    C Code:
    1. //cho vào tag nâng cao như thế này nè, dễ đọc code hơn. Nhớ nhé Đại hacker (Post by Dr)
    2. void optimize(int A[],int F[],int n)
    3. {
    4.     F[0] = 1;
    5.     for(int i=1;i<n;i++)
    6.     {
    7.         if (A[i]>A[i-1])
    8.         {
    9.             F[i] = F[i-1] + 1 ;
    10.         }
    11.         else
    12.         {
    13.             F[i] = 1;
    14.         }
    15.     }
    16. }
    17. void trabangtimketqua(int A[],int F[],int n)
    18. {
    19.     //Tim max va vitri max of mang F
    20.     int max = F[0];
    21.     int indexMax = 0;
    22.     for(int i=1;i<n;i++)
    23.     {
    24.         if (F[i]>max)
    25.         {
    26.             max = F[i];
    27.             indexMax = i;
    28.         }
    29.     }
    30.     //In ra ket qua dua vao Max va indexMax
    31.     int vitridau = indexMax - max + 1;
    32.     for(int j=vitridau; j<=max+1; j++)
    33.     {
    34.         cout <<A[j]<<" ";
    35.     }
    36. }

    - Còn về bài 2 thì tương tự như bài 1.
    + bạn khai báo một mảng Tong[] thay cho mảng F nhưng khó hơn
    + Luôn luôn trong mọi Trg hợp qui hoạch thì đk tiên quyết là:A[i] > A[i-1] thì mới đc tính vào mảng Tong[].
    + Công thức như sau:
    Tong[0] = A[0];
    Tong[i] = Tong[i-1] + A[i] (nếu A[i]>A[i-1] && F[i-1]+A[i]>A[i])
    else Tong[i] = A[i];

    //*Tại zì nếu bản thân một mình A[i] lớn hơn dãy con từ nãy giờ mình đang qui hoạch thì lấy lun A[i](tối ưu mà)...vì 1 phần tử cũng dc xem là dãy con của mảng ban đầu

    ví dụ mảng A{1,2,5,9,999,8,6} thì kết quả ra 999 là dãy con tăng có tổng lớn nhất.

    - Bạn thử test bằng tay đi.Học về thuật toán thì nên test tay trước khi ngồi vào coding = máy.

    - Luyện nhiều ắt sẽ thạo.Nếu có member nào quan tâm thì cho mình đố các bạn câu này:

    - "tại sao bài 1 khi A[i] ko đc chọn thì tui xử lý là cho F[i] = 1 còn bài 2 thì Tong[i] = A[i]" ?
    Đã được chỉnh sửa lần cuối bởi hacker_mubaohiem : 13-03-2008 lúc 09:48 PM.
    No way, No success..

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

    Mặc định bài tập C++ về đoạn tăng trong mảng 1 chiều

    Cả 2 bài này tui nhớ là có thảo luận rất nhiều, tìm dưới nick của tui hoặc vào box bài tập C và C++ tìm thử xem sao. Nếu dãy liên tục thì chỉ cần vòng lặp là đủ, nhưng nếu không liên tục thì QHD sẽ cho lời giải tối ưu.

  7. #7
    Ngày gia nhập
    11 2008
    Bài viết
    64

    Mình chưa học qui hoạch động nhưng bạn tham khảo thử đoạn code sau xem sao:
    PHP Code:
    #include <iostream>
    using namespace std;
    #include <time.h>
    #include<stdlib.h>
    bool tang(int a[],int i,int j)
     {
         
    int temp=i;
         while(
    a[temp]<a[temp+1]&&temp<=j-1)
          ++
    temp;
         
        if(
    temp==j)
         return 
    1;
        else 
         return 
    0;
     }
     
    void main()
     {
         
    int *a,n,i,j,max,temp;
        
        
    cout<<"Nhap vao N phan tu cua mang:";
        
    cin>>n;
        
    a=new int[n];
        
    srand(time(NULL));
        for(
    i=0;i<=n-1;i++)
         
    a[i]=rand()%11;
        
    cout<<"Mang sau khi khoi tao ngau nhien la:"<<endl;
        for(
    i=0;i<=n-1;++i)
           
    cout<<a[i]<<" ";
         
            
    max=0;
        for(
    i=0;i<=n-2;++i)
          for(
    j=i+1;j<=n-1;++j)
             if(
    tang(a,i,j)==1)
                if(
    max<j-i)
                 
    max=j-i;
           
          if(
    max>0)
         {
          
    cout<<endl<<"Doan Tang nhieu phan tu nhat trong mang la:";
         
          for(
    i=0;i<=n-2;++i)
           for(
    j=i+1;j<=n-1;++j)
                if(
    tang(a,i,j)==1)
                 if(
    max==j-i)
                  {  
                     
    cout<<endl;
                  for(
    temp=i;temp<=j;++temp)
                        
    cout<<a[temp]<<" ";
                  }
                    
               
            
                  
           
         }
         else
          
    cout<<"Khong co doan tang trong mang";
     } 
    Đã được chỉnh sửa lần cuối bởi Dark Knight : 20-07-2009 lúc 04:01 PM.

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

  1. Bài tập C++ Cần giúp đỡ về sắp xếp tăng dần trong mảng 2 chiều cho chuỗi ký tự
    Gửi bởi vn00494740 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 24-04-2012, 08:24 PM
  2. Bài tập C bài tập sắp xếp số chẵn tăng dần số lẻ giảm dần trong mảng 1 chiều
    Gửi bởi ronoa trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 07-01-2012, 08:33 AM
  3. Bài tập C bài tập c sắp xếp số dương tăng dần và số âm giảm dần trong mảng 1 chiều
    Gửi bởi killervip0 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 05-01-2012, 09:21 AM
  4. tìm chiều dài đoạn con tăng dài nhất trong mảng
    Gửi bởi ngoctrungbmt trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 13-02-2011, 11:40 PM
  5. Sắp xếp giá trị lẻ tăng dần trong mảng 1 chiều
    Gửi bởi kienchochethahaha 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: 12-01-2010, 04:57 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