Một vài bài toán nhỏ :D

[11520676]

Có mấy bài toán nhỏ để mọi người chém gió. Gọi là vui xuân đi.
Đầu tiên là xào lại bài pascal bên kia: trong các đoạn con của dãy a1, a2... aN. Tìm đoạn con có tổng các phần tử là lớn nhất.
INPUT: N và dãy N số a1, a2, ... aN.
OUTPUT: Tổng lớn nhất của các đoạn con.

Ví dụ:
dãy 5 3 -9 0 7
có đoạn con lớn nhất: 5 3 ~> output 8

[09520109]

Có mấy bài toán nhỏ để mọi người chém gió. Gọi là vui xuân đi.
Đầu tiên là xào lại bài pascal bên kia: trong các đoạn con của dãy a1, a2... aN. Tìm đoạn con có tổng các phần tử là lớn nhất.
INPUT: N và dãy N số a1, a2, ... aN.
OUTPUT: Tổng lớn nhất của các đoạn con.

Ví dụ:
dãy 5 3 -9 0 7
có đoạn con lớn nhất: 5 3 ~> output 8

đoạn con đó có chiều dài cố định hay là tự xác định hở bạn

[08520206]

đoạn con đó có chiều dài cố định hay là tự xác định hở bạn

chiều dài bất định

---

Nhớ hồi đó mấy dạng này làm bằng quy hoạch động thì phải ^^

[11520676]

Chiều dài từ 1 đến N. Chiều dài cố định thì là cái bài bên kia rồi. Còn bài toán với các đoạn con chiều dài từ 1 đến M (1 < M <N) thì chưa nghĩ ra được thuật toán hiệu quả

[09520019]

liên tục hay không liên tục ?

Nếu không liên tục thì có thể search "dãy con tăng dài nhất", cài giống y chang vậy, nhưng thay vì phép so sánh tăng thì đổi thành phép tổng

[11520676]

Đoạn con là liên tục, dãy con là không liên tục. Ở đây là đoạn con

[08520206]

Đoạn con là liên tục, dãy con là không liên tục. Ở đây là đoạn con

gì vậy em @@

đoạn con với dãy con là như nhau mà

Bài này đang so sánh các đoạn (dãy) con với nhau để xem cái nào tạo nên tổng lớn nhất thôi mà ?
Ở đây cũng không quan tâm lớn bé, dãy chứa các số miễn kề nhau là được .

[11520676]

- A ha anh đầu trọc chơi cờ vua.
- Vậy thì có thể cách gọi khác nhau. Mình gọi đoạn con là 1 dãy các số liên tiếp nhau trong dãy cho trước. Còn đoạn con thì không yêu cầu liên tiếp
Ví dụ: Dãy 5 6 8 9 3 0
thì 6 8 9 là đoạn con 3 phần tử bắt đàu từ vị trí 2
còn 5 8 3 chỉ là dãy con của dãy đã cho chứ không phải là đoạn con.
- Ở bài này mình hỏi rõ là đoạn con. Nếu là dãy con thì bài toán khá tầm thường. Ta chỉ cần nhặt các số không âm của dãy; nếu các số trong dãy đều âm thì ta chỉ cần chọn số lớn nhất.

[truonganpn]

- A ha anh đầu trọc chơi cờ vua.
- Vậy thì có thể cách gọi khác nhau. Mình gọi đoạn con là 1 dãy các số liên tiếp nhau trong dãy cho trước. Còn đoạn con thì không yêu cầu liên tiếp
Ví dụ: Dãy 5 6 8 9 3 0
thì 6 8 9 là đoạn con 3 phần tử bắt đàu từ vị trí 2
còn 5 8 3 chỉ là dãy con của dãy đã cho chứ không phải là đoạn con.
- Ở bài này mình hỏi rõ là đoạn con. Nếu là dãy con thì bài toán khá tầm thường. Ta chỉ cần nhặt các số không âm của dãy; nếu các số trong dãy đều âm thì ta chỉ cần chọn số lớn nhất.

Có lẽ bài này em lấy từ trong sách vở nào đó ra. Nếu vậy thì em nên ghi lại nguyên văn, sẽ thuận tiện hơn cho tất cả mọi người.

[11520676]

- Sách vở nào ?_? em xào lại cái bài tìm đoạn con M phần tử sao cho tổng của nó lớn nhất ở topic PASCAL bên kia.
- Còn việc phân biệt đoạn con và dãy con thì ai học tin được vài năm đều rõ. Đâu cần bắt bẻ như vậy. Bên trên mình type nhầm Đoạn con yêu cầu liên tiếp, còn dãy con thì không.

[truonganpn]

- Sách vở nào ?_? em xào lại cái bài tìm đoạn con M phần tử sao cho tổng của nó lớn nhất ở topic PASCAL bên kia.

Nếu vậy em đưa link đến topic đó đi để các bạn đỡ phải tốn 10 post chỉ loanh quanh ở việc "giải mã" đề bài.

[11520676]

http://forum.uit.edu.vn/threads/2867-PASCAL-Giup-minh-mot-bai-toan-nho-D

Không hiểu mọi người muốn làm bài hay bắt bẻ đề bài nữa :|

[11520676]

Nào thì vừa đánh trống vừa thổi kèn.
- Từ bài toán PASCAL bên kia, ta viết được hàm: int maxM(int a[], int n, int m);
trả về MAX(Si); i = 1, 2, ..., n - m: Si là tổng các phần tử của đoạn con bắt đầu từ i, m phần tử.
ta có thuật toán:
int maxSum = 0;
for (int i = 1; i <= m; i++)
cập nhật giá trị của maxSum từ hàm maxM(a, n, i);
output: maxSum. Độ phức tạp O(n^3)
- Quy hoạch động: Đặt F[i] = giá trị lớn nhất các đoạn con của dãy a1, a2, ..., ai.
tập các dãy đoạn con được phân hoạch thành:
+ Không chứa phần tử a[i]. Khi đó, F[i] = F[i - 1];
+ Chứa phần tử a[i]. Khi đó F[i] = max(S1 S2, ... Si). Trong đó Sj là tổng các phần tử của đoạn con có độ dài j, kết thúc tại i. Cụ thể s1 = a[i],
s2 = a[i] + a[i-1]
...
si = a[i] + a[i-1] +... + a1
Tóm lại ta có công thức truy hổi: F[i] = max(F[i-1], S1, S2,...,Si).
Output: F[n]
Độ phức tạp O(n^2)
- Tham lam:
Đặt Si = a1 + a2 +.. + ai.
Cụ thể: S1 = a1
S2 = a1 + a2
...
Sn = a1 + a2 + ... + an.
Khi đó: Tổng các phần tử của đoạn con bắt đầu từ i, kết thúc tại j (i < j) là Sj - Si
Bài toán trở thành: tìm 2 chỉ số i, j sao cho Sj - Si lớn nhất.
Mình mới chỉ nghĩ ra thuật toán tham lam thế này:

Ơ lười trình bày, hôm nào có hứng viết tiếp

[09520019]

Nào thì vừa đánh trống vừa thổi kèn.
- Từ bài toán PASCAL bên kia, ta viết được hàm: int maxM(int a[], int n, int m);
trả về MAX(Si); i = 1, 2, ..., n - m: Si là tổng các phần tử của đoạn con bắt đầu từ i, m phần tử.
ta có thuật toán:
int maxSum = 0;
for (int i = 1; i <= m; i++)
cập nhật giá trị của maxSum từ hàm maxM(a, n, i);
output: maxSum. Độ phức tạp O(n^3)
- Quy hoạch động: Đặt F[i] = giá trị lớn nhất các đoạn con của dãy a1, a2, ..., ai.
tập các dãy đoạn con được phân hoạch thành:
+ Không chứa phần tử a[i]. Khi đó, F[i] = F[i - 1];
+ Chứa phần tử a[i]. Khi đó F[i] = max(S1 S2, ... Si). Trong đó Sj là tổng các phần tử của đoạn con có độ dài j, kết thúc tại i. Cụ thể s1 = a[i],
s2 = a[i] + a[i-1]
...
si = a[i] + a[i-1] +... + a1
Tóm lại ta có công thức truy hổi: F[i] = max(F[i-1], S1, S2,...,Si).
Output: F[n]
Độ phức tạp O(n^2)
- Tham lam:
Đặt Si = a1 + a2 +.. + ai.
Cụ thể: S1 = a1
S2 = a1 + a2
...
Sn = a1 + a2 + ... + an.
Khi đó: Tổng các phần tử của đoạn con bắt đầu từ i, kết thúc tại j (i < j) là Sj - Si
Bài toán trở thành: tìm 2 chỉ số i, j sao cho Sj - Si lớn nhất.
Mình mới chỉ nghĩ ra thuật toán tham lam thế này:

Ơ lười trình bày, hôm nào có hứng viết tiếp

Fully Brute force attack O(n^3)
Half Brute force attack - Dynamic Programming O(n^2)
Fully Dynamic Programming - Mathematics O(n)
Greedy algorithm - O(n) - 90% test case will be wrong
Challenging - O(log n) - Unknown algorithm - Maybe binary tree/Binary indexed tree/Interval tree/or something like that can help
màu đỏ: cái bạn đạt được - màu xanh lá cây: cái mình đạt được - màu xanh dương: cái mình chưa làm được ^_^

Nhận xét: 1 dãy là liên tục. Giả sử ta tính G[i] = tổng(a1 ... ai), ta có giá trị của dãy từ i tới j F[i,j] = G[j] - G[i - 1]
Với mỗi j, F[i,j] đạt max khi và chỉ khi G[i - 1] đạt min
Ngoài ra: trong G[1 ... j - 1], chỉ tồn tại duy nhất 1 giá trị min G[x] (có thể có nhiều x, nhưng chỉ có 1 min)
=> Linh cảm mách bảo: với mỗi j, ta có thể tính được i sao cho G[i] là phần tử min ngay trong O(1) => giảm được độ phức tạp

Cài đặt:
Gọi G[x] với G[x] = G[x - 1] + a[x]; Tính O(n)
Gọi minG[x] với minG[x] = min(G[x-1],minG[x - 1]); cũng tính trong O(n), chú ý không tồn tại minG[0]
Gọi F[x] = G[x] - minG[x]; tính trong O(n)
Gọi res là kết quả cần tìm, res = min (F[0] .... F[n - 1]) O(n)

Example:
a: 5 3 -9 0 7
G: 5 8 -1 -1 6
minG: 0 0 -1 -1 -1
F[G]: 5 8 0 0 7
res = 8

Challenge : bạn nào nghĩ ra được thuật toán O(log n) thì cho tớ tham khảo

Đôi lời nhắn nhủ:
+ bạn bị sai lầm về greedy algorithm bởi vì greedy algorithm quan tâm tới giá trị tối ưu cục bộ của bài toán để đạt tới giá trị tối ưu toàn cục của bài toán. Chứ nếu nói như bạn tìm i, j sao cho Sj - Si max thì cái đó là Brute Force attack/ Dynamic Programming
+ tớ đi thi nhiều rồi nên hiểu cái đề quá. Dãy con là gì, Đoạn con là gì, đề phải nói rõ. Liên tục hay không đề cũng phải nói rõ. Ở đây chúng ta thi về mặt thuật toán chứ không phải thi về mặt từ vựng. Mấy cái vụn vặt đó không nên đánh đố nhau, nên đề phải nói rõ ra là có liên tục hay không, giới hạn của n là bao nhiêu chứ ko phải khơi khơi cái đề là hết. Nên em đừng nên nói " Còn việc phân biệt đoạn con và dãy con thì ai học tin được vài năm đều rõ." Có những đề đoạn con không liên tục, và dãy con liên tục ^_^. Với tiếng anh, nó chỉ đơn giản là subsequence.

[11520132]

Cái dãy con tăng dài nhất thì bài đó mình làm rồi. Chỉ cần đổi cái phép tính số đếm phần tử dãy con thành tổng các phần tử trong dãy con có thể sẽ giải quyết được