– Sử dụng Đệ Quy và Chia Để Trị để giải quyết Bài toán tìm dãy con lớn nhất:
* Cho dãy số \(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 đã cho và $\sum_{k=i}^{j}=a_{k}$ được gọi là trọng lượng của dãy con này
Bài toán đặt ra là: Hãy tìm trọng lượng lớn nhất của các dãy con, tức là tìm cực đại giá trị $\sum_{k=i}^{j}=a_{k}$. Để đơn giản ta gọi dãy con có trọng lượng lớn nhất là dãy con lớn nhất.
* Ví dụ: Nếu dãy đã cho là $-2, 11, -4, 13, -5, 2$ thì cần đưa ra câu trả lời là $20$ (là trọng lượng của dãy con \(11, -4, 13\))
– Sử dụng Đệ Quy và Chia Để Trị để giải quyết Bài toán tìm dãy con lớn nhất: * Cho dãy số \(a_1, a_2, … , a_n\) Dãy số \(a_i, a_{i+1} , …, a_j\) với \
By Jasmine
Thuật toán:
-Cho chạy dãy đệ quy nhị phân có n phần tử là b.
-Cho 1 vòng lặp:
Lặp cho tới khi: i=n, i++
{
Nếu b[i]=1 thì tong=0; j=i;
Lặp cho tới khi b[j]=1 và b[j+1]=0, tong=tong+a[j]; j=j++;
Nếu tong>max thì max=tong;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////
Khuyến mãi thêm cho bạn:
Mình có 1 cách này đơn giản hơn, dễ hơn để giải bài toán này:
Chạy i từ 1 tới n:
{
tong=0;
Chạy j từ i tới n
{
tong=tong+a[j];
If tong>max thì max=tong
}
}
Bạn tham khảo nhé! =))
#Chúc Học Tốt