Có một dãy các số nguyên a1, a2, ..., an. Ta chia dãy số này thành 2 dãy con như sau:
– Dãy con thứ nhất gồm k số đầu tiên trong dãy đã cho và tổng các phần tử của dãy con này là T1.
– Dãy con thứ hai gồm các số còn lại của dãy số đã cho và tổng các phần tử của dãy con này là T2.
Yêu cầu: Tìm số nguyên dương k là độ dài của dãy con thứ nhất sao cho|T1-T2| nhỏ nhất.
Chú ý: Nếu có hơn một số k thỏa mãn thì ghi ra số k nhỏ nhất.
Cách làm: Tạo một mảng T[1..n] với T[i] = a1 + a2 + ... + ai.
Xét hai dãy {a1, a2,...ak} có tổng là T1 và dãy {ak+1, ak+2, ...,an} có tổng là T2. Khi đó, ta có:
T1 = T[k] và T2 = T[n] – T[k]
=> |T1 – T2|= |T[n] – 2*T[k]|
Dùng vòng lặp để duyệt tất cả các biểu thức |T[n]–2T[i]| với . Trong các biểu thức có GTNN, ta chọn giá trị i nhỏ nhất là số cần tìm
GIUP EM VOI A CAN GAP LAMMM
Loga
Sinh Học lớp 12
