30/09/2018, 16:42
Nhờ giúp đỡ chương trình tính đoạn con
Viết chương trình tìm đoạn con có tổng bằng S cho trước, em làm như sau nhưng không cho kq đúng, các bác có cách làm tối ưu hơn ko cho em tham khảo, mới nhập môn nên còn gà mờ, C++ càng tốt ạ
#include <iostream>
#include <fstream>
using namespace std;
int main(){
int mang_so[100];
int n,S,i,j,a,Tong;
Tong=0;
cin>>n>>S;
for (int i=0;i<n;i++){
cin>>mang_so[i];
}
for (i=0;i<n;i++){
for (j=0;j<n;j++){
if (i>j) {
Tong=0;
continue;
}
else {
for(a=i;a<j;a++){
Tong=Tong+mang_so[a];
}
}
if (Tong==S) cout<<i<<"---"<<j<<endl;
}
}
return 0;
}
http://codepad.org/KcZi3NYI
Bài liên quan
Ý bác là nhập vào Tổng S rồi sau đó xét xem trong mảng có đoạn nào mà tổng bằng S và in ra đúng k ??
Đề đây: Tổng đoạn
Một dãy con gồm các phần tử liên tiếp nhau trong một dãy cho trước được gọi
là đoạn. Cho dãy gồm N số tự nhiên, viết chương trình tìm đoạn ngắn nhất có tổng các
phần tử bằng giá trị K cho trước.
Input: Tập tin văn bản DOAN.INP
Output: Tập tin văn bản DOAN.OUT, chứa một dòng duy nhất gồm hai số tự
nhiên x và b. Trong đó x: là chỉ số đầu đoạn; b: là số phần tử trong đoạn (chiều dài
đoạn). Nếu tìm không có (vô nghiệm) ghi 0 0.
===================
Mình mới tìm cách tìm đoạn con có tổng = S thôi, nhờ bạn.
Bạn nghiên cứu quy hoạch động thử xem
Nếu là dãy số không âm thì mình có cách làm như sau:
Biến start=0, end,s=0;
Cho end từ 0->n:
Giải thích:
Nếu s < k. Thì tất cả đoạn con [start,end] đều không thoã mãn.
Nếu s=k. Tìm thấy, tính cho lần sau.
Nếu s > k. Tất cả đoạn con bắt đầu từ start và sau end đều lớn hơn k nên không tính các đoan con từ start nữa. Chuyển sang đoạn bắt đầu từ start+1.
dpt O(n)
Thank các thím