Đề như sau: Cho 1 dãy số nguyên, có giá trị âm và không âm. vd: 1 -2 5 -10 2 33 12 -9 -3. Viết thuật toán tìm dãy số dài nhất có thể và có tổng dương. Mình có thuật toán như sau: - Xét tổng của dãy. Nếu tổng lớn hơn 0 --> dãy dài nhất chính là dãy ban đầu --> xuất ra. - Nếu tổng nhỏ hơn 0. - Duyệt từ đầu dãy và, duyệt qua phần từ nào đếm số phần tử và gán số phần tử đã duyệt cho biến i. dừng lại tại giá trị < 0 đầu tiên gặp được. - Duyệt từ cuối dãy về. đếm số phần tử đã duyệt cho biến j. dừng lại khi gặp giá trị âm đầu tiên --> Lúc này 2 biến i và j thể hiện vị trí từ đầu danh sách đến số âm đầu tiên đi lên và từ cuối danh sách đến số âm đầu tiên từ cuối về. Ta xét 2 số i ,j. i = j => số nào nhỏ hơn thì loại. Mục đích là lấy số lớn hơn. 2 số bằng nhau(trường hợp này mình chưa xét). i > j. lấy danh sách xuất phát từ đầu đến vị trí j. Vì ta lấy theo tiêu chí là dãy số dài nhất có thể. từ cuối dãy về gặp số âm trước nên loại phần cuối(tính từ j -> hết dãy). tính tổng dãy . nếu dương --> xuất ra, nếu âm --> gọi đệ quy, xét tiếp dãy số còn lại. i < j. Ngược lại, lấy danh sách mời từ vị trí i -> hết dãy. tính tổng. nếu dương --> xuất kết quả. nếu âm --> gọi đệ quy tính tiếp. Đây mới là thuật toán sơ bộ, còn nhiều thuật toán khác để làm việc này. mình chưa cài đặt thuật toán này. ai làm rồi cho tham khảo nhé.
Tân xuân khai bút, nghiệp mình không dùng bút thì chuột và bàn phím Demo chưa test đâu: Mã: int tong(int m[],int f,int n) { int tong=0; for(int i=f; i<n; i++) tong+=m[i]; if(tong>0) return tong; else return 0; } void xuat(int m[],int f,int n) { for(int i=f; i<n; ++) cout<<m[i]<<"\t"; } void nhap(int m[],int n) { cout<<"\nNhap n: "; cin>>n; for(int i=0; i<n; i++) { cout<<"Nhap "<<i<<": "; cin>>m[i]; } } main () { int f=0;// vi tri dau tien if(tong(m,n)<=0) xuat(m,f,n); else { int cfirst=0,clast=0; for(int i=0; i<n; i++) { if(m[i]<0) break; else cfirst++; } for(int j=n;j>0;j--) { if(m[j]<0) break; else clast++; } //xet 2 so i,j if(i==j) { if(m[i]<m[j]) { f=i+1;// lay day sau vi tri i den n xuat(m,f,n); } else xuat(m,f,(n-j)-1);//n-j la vi tri gap so am dau tien, lay n tai //loai them phan tu tai vi tri j nua } if(i>j) { } } } Khai bút nên làm tạm thế đã, ra tết làm tiếp, chúc mọi người học tốt
