[Thảo luận] Thuật toán

[11520246]

[MENTION=7969]09520019[/MENTION] Anh ơi, em đã rõ hơn rồi ạ, lúc trước em nhìn vào phương trình bài toán ban đầu: a^3 + b^3 + c^3 = 100a + 10b + c rồi lại nghe anh chuyển vế lấy cái đống kia làm hằng với 2 ẩn tự do là a và b, và rồi chỉ việc đi tìm c nên thấy hơi ngợp và thắc mắc rằng a,b lấy ở đâu ra mà bảo làm ẩn tự do gì gì đó, thì ra em quên béng đi mất là lúc này ta đã chạy vòng for rồi, cụ thể là 2 vòng lồng for a (for b) từ 0, 1,..9.
Như thế ta đã có được giá trị a, b xác định ở mỗi cặp đôi vòng lặp a, b này và bắt đầu tìm c được bằng cách thay a,b vào cái đống q = (a^3 + b^3 -100a -10b) trong phương trình chuyển vế: c^3 - c + (a^3 + b^3 - 100a - 10b) = 0. Cái đống q này khi thay vào thì là hằng số rồi nên cứ chiếu theo Vieta, hoặc phương trình tổng hợp, lượng giác trên wiki mà anh có gửi, ở dạng: c^3 + pc + q = 0, với p = -1, q = a^3 + b^3 - 100a - 10b (q đã tính được cụ thể rồi) để bắt đầu công cuộc đi tìm c.
Ở chỗ vieta trên anh úp 2 hình trùng, nên đây là link để mọi người xem đầy đủ về vieta mà anh có nói: http://en.wikipedia.org/wiki/Cubic_e...s_substitution
OK, vậy là đã sáng tỏ!

@0852001, em quên nói rõ hơn ở về phần thứ 3 này, thực ra nó cũng chưa hẳn là phần giống như hai phần của mỗi nửa mảng trái, phải kia, mà nó thuộc vào phần mà mảng đó trước khi bị chia nhỏ (chia đôi) ra để giải quyết. Em sẽ nói rõ hơn như sau:
Giả sử mảng ban đầu của ta có dạng a[đầu..đuôi] với đầu là chỉ số đầu, đuôi là chỉ số đuôi.
Ta xác định một điểm giữa (lấy (đầu + đuôi)/2 chẳng hạn) và bắt đầu chia đôi mảng đó ra thành hai nửa là: a[đầu..giữa] (nửa trái) và a[giữa+1..đuôi] (nửa phải).
Như thế xuất hiện 3 tình huống khả nghi trong việc xác định mảng con lớn nhất cần tìm (gọi là mảng R đi cho gọn), đó là Mảng R này:

1. Nằm trọn trong nửa trái kia, tức là trong khoảng a[đầu..giữa]
2. Nằm trọn trong nửa phải kia, tức là trong khoảng a[giữa+1..đuôi]
3. Hoặc nằm gối đầu, tức là nằm trong khoảng a[đầu..đuôi], và dĩ nhiên mảng R phải đi qua điểm giữa.

Do đó, công việc trước hết cần làm là thực thi cái tình huống 3 ấy, (còn 2 tình huống 1 và 2, bản chất nó đệ quy, cứ chia đôi nhỏ ra, để rồi cũng đụng độ tình huống 3), tình huống 3 này là khi ta biết vị trí điểm giữa rồi, ta sẽ đi tìm mảng con lớn nhất của nửa trái a[đầu..giữa] và của nửa phải a[giữa+1..phải] rồi kết hợp kết quả từ 2 nửa đó lại.
Nôm na như thế này:
Tìm phần lớn nhất bên trái
Tìm phần lớn nhất bên phải
Kết hợp kết quả hai phần trên để tìm được phần lớn nhất có đi qua điểm giữa.
Gọi cái nôm na ở trên là TìmMảngGốiĐầu.

Và nôm na cho việc giải quyết cả bài toán TìmMảngConLớnNhất của chúng ta như sau.
TìmMảngConLớnNhất(đầu, đuôi) =
# TH mảng chỉ có 1 phần từ (Trường hợp cơ bản (dừng)) thì phần tử duy nhất đó cùng với chỉ số đầu, đuôi sẽ là mảng con lớn nhất R cần tìm
# Ngược lại:
+ Xác định điểm giữa = (đầu + đuôi)/2, rồi
Đệ quy TìmMảngConLớnNhất(đầu, giữa)
Đệ quy TìmMảngConLớnNhất(giữa + 1, đuôi), và
TìmMảngGốiĐầu(đầu, đuôi)

Ba cái TìmMảng... ở trên ta sẽ chọn ra cái lớn nhất, thì cái lớn nhất đó chính là thứ chúng ta cần tìm.

Ví dụ cho dễ hiểu hơn, ta có mảng A gồm 16 phần tử và cần đi tìm mảng R. Như vậy
TìmMảngConLớnNhất(0, 15) sẽ gọi TìmMảngConLớnNhất(0, 7), TìmMảngConLớnNhất(8, 15)
và rồi TìmMảngConLớnNhất(0, 7) sẽ gọi TìmMảngConLớnNhất(0, 3) và TìmMảngConLớnNhất(4,7)
và rồi TìmMảngConLớnNhất(0, 3) sẽ gọi TìmMảngConLớnNhất(0, 1) và TìmMảngConLớnNhất(2, 3)
và rồi TìmMảngConLớnNhất(0, 1) sẽ gọi TìmMảngConLớnNhất(0, 0) và TìmMảngConLớnNhất(1, 1)
...
lúc này TìmMảngConLớnNhất(0, 0) và TìmMảngConLớnNhất(1, 1) cả hai đều chỉ có một phần tử nên chiếu theo trường hợp cơ bản # ở trên sẽ trả về chính mảng chứa phần tử duy nhất đó. Rồi lúc này lại quay đầu đi TìmMảngGốiĐầu(0, 1) rồi so sánh với TìmMảngConLớnNhất(0, 0) và TìmMảngConLớnNhất(1, 1) (hai nửa của (0,1)) đã có được ngay trước đó để tìm được TìmMảngConLớnNhất(0, 1).
Cứ thế lại truy hồi tới trường hợp cơ bản để TìmMảngConLớnNhất(2, 3),.... rồi nào là so sánh để lựa ra cái lớn nhất.
Viết dài dòng như thế không biết mọi người có rõ không nữa.

[12520527]

[MENTION=11756]11520246[/MENTION] : có thể áp dụng như cách anh đề cập để luyện kĩ năng chia nhị phân :smile:
Có vẻ như trường mình không mấy ai hào hứng với những bài toán tin như thế này nhỉ udency:
Để hâm nóng lại topic, em xin góp củi thêm một bài :salute:

Cho 2 số nguyên dương N, K (K <= N) và một dãy A gồm N phần tử là các số nguyên dương. Xét lần lượt N - K + 1 dãy con gồm K phần tử liên tiếp trong dãy đã cho (dãy con thứ nhất là A[1...K], dãy con thứ hai là A[2..K+1] ...), với mỗi dãy con hãy in ra phần tử có giá trị bé nhất trong dãy con đó.
Giới hạn : N <= 20000.

Ví dụ :
N = 4, K = 2
Dãy A : 3 2 4 1

Dãy con thứ nhất : 3 2 -> Phần tử bé nhất (PTBN) : 2
Dãy con thứ hai : 2 4 -> PTBN : 2
Dãy con thứ ba : 4 1 -> PTBN : 1

--> Output sẽ là 2 2 1

[08520001]

Bài của Tín có vẻ khó đây. Nếu làm bình thường, xét lần lượt từ trái qua phải tất cả các dãy con N - K 1 phần tử, với mỗi dãy con, duyệt K phần tử của dãy con đó và tìm phần tử nhỏ nhất, thì độ phức tạp là O(N * K) có thể chạy được nếu giới hạn thời gian 5s.

[14520103]

1 năm club thuật toán chưa có đến nổi 10 hoạt động nữa

[toannv]

1 năm club thuật toán chưa có đến nổi 10 hoạt động nữa

Em có thể lên các trang thi online mà thấy MSSV của UIT là .. "nó" đó.