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

[12520527]

Lúc trước có seri topic Mỗi ngày một bài toán của anh Thắng hay Hùng gì đó cũng vui, mà rồi cũng thất truyền :brick:
Cho em góp vui 2 bài nhé :funny:

Cho 1 dãy số nguyên, tìm dãy con có tổng lớn nhất (Dãy con là dãy gồm các phần tử liên tiếp trong dãy ban đầu). VD : 1 2 3 4 -1 thì dãy có tổng lớn nhất là 1 2 3 4.

[08520001]

Sau khi giải quyết bài toán của bạn Tín, Anh đề nghị ý kiến chúng ta sẽ thảo luận thuật toán theo chủ đề. Mỗi chủ đề lớn có nhiều chủ đề con, mỗi topic sẽ thảo luận 1 chủ đề con như vậy, các bài toán đưa ra sẽ thuộc chủ đề đó. Và đối với các bài toán đưa lên topic, tác giả sẽ phải cung cấp đầy đủ các thông tin về giới hạn dữ liệu (chúng ta mặc định thời gian chạy là 1 giây cho mỗi test). Vì có những bài, tùy vào giới hạn dữ liệu mà sẽ có những cách giải khác nhau. Ngoài ra, tác giả phải giải được bài toán đó, và sau khi các bạn khác thảo luận, tác giả phải đưa ra cách giải của mình, gồm đầy đủ thuật toán, cơ sở để chứng minh thuật toán đó là đúng, khuyến khích các bạn diễn đạt sao cho mọi người dễ hiểu.

[09520019]

Cảm ơn anh An đã tạo topic hay cho mọi người trao đổi.

Tuy nhiên em xin được góp ý đến với anh An, bạn Huy và bạn Lân. Có lẽ mọi người không cố ý nhưng em nghĩ sau này không nên đánh giá độ dễ, khó của một bài nữa. Mục đích để tôn trọng người giải bài đó, tôn trọng những người không giải được và không để triệt tiêu những ý tưởng sáng tạo, mở rộng của bài toán.

Thời học phổ thông, em cũng đã từng rất buồn và hụt hẫng khi bài toán mình mất cả tuần mới giải được thì nhận được một câu từ người khác : "Bài này dễ ợt mà..."

Còn về bài thứ nhất, em nghĩ đó là bài hay. Nhất là đối với sinh viên thích toán. Vì nếu ta nghĩ nó khó, thì nó khó, để ra cả trăm vấn đề để giải.

Thử đặt vấn đề cho bài 1, nếu ta không duyệt từ 001 -> 999 để kiểm tra, thì ta phải làm gì để tối ưu, có cách nào nhanh hơn không ?

Giả sử, với code của bạn Trần Đại Dương, em sửa chút ít lại thế này để 2 số a,b luôn cùng tính chẵn lẻ.

for (int a = 1; a < 10; a++)
                for (int b = (a % 2) ; b < 10; b = b + 2)
                    for (int c = 0; c < 10; c++)
                        if (a * a * a + b * b * b + c * c * c == a * 100 + b * 10 + c)
                            Console.WriteLine("{0}{1}{2}", a, b, c); 

Cùng với đó là những modulo khác giúp bài toán vui hơn.

Em không thích dạy đời ai hết, nhưng thực sự, mong mọi người đặt bản thân mình vào vị trí của người khác để suy nghĩ.

O_o Nghe đồn đội thuật toán có truyền nhân nên ghé forum coi thử..... comment của bạn Nguyên khá ấn tượng ...nhưng mà phải nói rõ cho bạn hiểu tại sao anh An lại nói bài này dễ rồi skip luôn. Hồi xưa mình cũng hơi hơi giống bạn, tức là cái gì cũng muốn tối ưu cả. Nhưng các Olympiad contest là có giới hạn về mặt thời gian. Đôi khi mình chấp nhận code O(n^3) hoặc O(n^4) chỉ với mục đích là chắc chắn pass test càng nhanh càng tốt. Nếu đang trong phòng thi thì mình chắc chắn sẽ theo code của bạn Dương vì tính đơn giản của nó. Với cái bài như thế này, thì mục tiêu bạn đặt ra không phải là tối ưu càng nhiều càng tốt, mà là code càng nhanh càng tốt, 1 phút nộp bài. Hiểu chứ ?

Sau đó, mới bắt đầu nghĩ tới chuyện tối ưu, và "hơi tối ưu" và đánh bạo nộp bài. Tối ưu là việc chuyển đoạn code trên từ O(n^3) xuống O(n^2), chỉ khi bí rồi (hoặc nhận thấy bất khả thi), hoặc cách hơi tối ưu của bạn code nhanh hơn với ít thời gian suy nghĩ và chắc chắn là khó xảy ra bug, thì mới dám code theo hướng đó.

Bây giờ là phần tối ưu O(n^2)

bài toán là gì ? a^3 + b^3 + c^3 = 100a + 10b + c
<-> c^3 - c + (a^3 + b^3 - 100a - 10b) = 0
<-> c^3 - c + (A) = 0 (I)

Đặt a,b là biến tự do, c là ẩn cần tìm, như vậy xem như cái cụm (A) là hằng số
phương trình (I) có thể giải bằng phương pháp tìm nghiệm phương trình bậc 3 theo phương pháp Vieta http://en.wikipedia.org/wiki/Cubic_f...n_of_the_roots

hoặc theo phương pháp dùng lượng giác với a = 1,b = 0 và c = -1, hoặc công thức nghiệm tổng quát. Nói chung là gì cũng được http://vi.wikipedia.org/wiki/Ph%C6%B...b%E1%BA%ADc_ba

vậy thì từ 3 vòng for, giảm còn 2 vòng for, tính c dựa theo phương trình bậc 3 còn lại. Nếu vô nghiệm thì chuyển tới vòng for tiếp theo.

[11520447]

Lúc trước có seri topic Mỗi ngày một bài toán của anh Thắng hay Hùng gì đó cũng vui, mà rồi cũng thất truyền :brick:
Cho em góp vui 2 bài nhé :funny:

Cho 1 dãy số nguyên, tìm dãy con có tổng lớn nhất (Dãy con là dãy gồm các phần tử liên tiếp trong dãy ban đầu). VD : 1 2 3 4 -1 thì dãy có tổng lớn nhất là 1 2 3 4.

Chỉ nghĩ được cách cho duyệt số chữ số của dãy con tăng dần

[08520001]

@Tú: em có thể viết cụ thể hơn không?

[10520100]

@ anh Châu : Lời giải hoàn hảo ! Đúng là k uổng công e ngưỡng mộ a Châu.

Hề hề, mà anh Châu lại lái ý của em đi qua hướng khác rồi. Điều em mong muốn ở đây đã thể hiện rất rõ :

- Không nên đánh giá độ khó của bài toán.

- Nên kích thích tính tò mò, giải quyết vấn đề độc đáo của các bạn.

Em đâu dám đề cập đến Olimpic hay ACM gì đâu Cả đời chưa được đi thi một lần, lấy gì mà đề cập

Theo em thấy, ở cái thời điểm Facebook, Haivl, Internet gây bão thì cách kích thích tính tò mò, sáng tạo của các bạn là tốt nhất. Chỉ có vậy mới mong các bạn giảm thời gian game, và tăng sự hứng thú code, bị thách thức bởi một cái gì đó.

Cũng giống như thời cấp 3, tụi em thường mua báo Toán học tuổi trẻ để giải, nộp những bài trong đó. Những bài mà kì thi đại học không bao giờ ra thì tụi em vẫn làm.
Bởi vì mỗi người đều yêu thích cảm giác giải được bài trong đó.
giờ code cũng vậy, tự thách thức mình hay gọi là "tự sướng" cũng được, giúp ta code vui hơn, sâu hơn và có cái tâm của nghề IT hơn.

Em xin hết ạ, hi vọng a An thông cảm vì đã làm loãng topic.

[08520001]

Không sao em. Đó là tâm sự của 1 sinh viên yêu thích thuật toán mà.
Quay lại với bài toán, a có ý tưởng như sau:
Đặt current_sum là tổng hiện tại, max_sum là tổng lớn nhất
Duyệt qua dãy, với mỗi số, ta cộng dồn vào current_sum. Nếu current_sum

[09520019]

- Không nên đánh giá độ khó của bài toán.
- Nên kích thích tính tò mò, giải quyết vấn đề độc đáo của các bạn.

tăng sự hứng thú code, bị thách thức bởi một cái gì đó.

Về việc kích thích sáng tạo với trí tò mò thì a không có gì để phản đối, anh chỉ theo hướng khác em thôi Với những dạng bài như thế này thì thách thức mà anh thường đặt ra là code nhanh (tầm 1~3' là xong), pass hết test. Code ngắn, đẹp, gọn, súc tích . Đó cũng là 1 thách thức lớn, vì đối với những người quen với tư duy tối ưu sẽ gặp trục trặc, thường sẽ tốn tầm 10' cho bài này Nói chung là ý của em thì không có vấn đề gì lớn. Chỉ là anh giải thích cho em thấy tại sao anh An lại chấp nhận đáp án và đi tiếp

Không sao em. Đó là tâm sự của 1 sinh viên yêu thích thuật toán mà.
Quay lại với bài toán, a có ý tưởng như sau:
Đặt current_sum là tổng hiện tại, max_sum là tổng lớn nhất
Duyệt qua dãy, với mỗi số, ta cộng dồn vào current_sum. Nếu current_sum < 0 thì ta gán lại current_sum = 0. Ngược lại current >= 0, ta so sánh với max_sum và cập nhật lại max_sum = max(max_sum, current_sum)

Anh giải thế thì còn ai giải nữa :-w

[08520001]

@Châu: Anh nghĩ một đề bài không nên tồn tại quá lâu. bài đó đã xuất hiện từ qua tới giờ rồi, nhưng ít comment quá. Không biết trường mình có bao nhiêu bạn biết về thuật toán, yêu thích lĩnh vực này, mà theo tình hình này chắc cũng sẽ chìm vào quên lãng như nhưng topic trước.

Theo kinh nghiệm của mình thì đúng là thuật toán không quan trọng lắm khi ra trường vào làm ở đa số công ty phần mềm ở Việt Nam. Cho nên bạn nào nghĩ học thêm thuật toán để phục vụ sau này đi làm thì không cần tốn thời gian học nó nữa. Vậy học thêm thuật toán để làm gì trong khi nó vừa khó, vừa khô khan. Trước tiên, trong các khoa của CNTT thì có khoa Khoa học máy tính là có học và nghiên cứu về lĩnh vực này. Tuy nhiên, ở chương trình học ở Việt Nam, có thể nó không được thấy rõ, nhưng nếu đi du học về ngành này thì sẽ thấy, yêu cầu khá cao. Ví dụ có một cuộc phỏng vấn của google, trong đó có một câu thuật toán yêu cầu giải một bài toán thuộc lĩnh vực cấu trúc dữ liệu nâng cao, làm và viết code trong 15 phút. Theo mình thấy thì đó là khó. Ngoài ra, học thuật toán, làm các bài tập về thuật toán, sẽ giúp hiểu rõ về ngôn ngữ hơn. Vì hiện nay có rất nhiều ngôn ngữ, khi chúng ta học một ngôn ngữ, và muốn luyện tập để thành thạo ngôn ngữ đó, thì chúng ta luyện tập bằng cách nào ngoài các làm bài tập, những bài tập đó thuộc về thuật toán. Bài tập càng phức tạp thì càng đòi hỏi phải thành thạo ngôn ngữ. Tiếp theo, học thuật toán giúp rèn luyện tư duy về phân tích, xử lý các vấn đề nhỏ thiên về kĩ thuật trong các project. Thuật toán tốt thì nhanh chóng tìm ra được solution phù hợp và chính xác, code viết ra sẽ rõ ràng, dễ hiểu, còn có thể cải tiến về tốc độ.
Đó là những ý kiến của mình về việc học thuật toán để giúp các bạn hiểu thêm về lĩnh vực này. Hàng năm có các kì thi thuật toán như Olympic Tin học sinh viên, kì thi lập trình quốc tế ACM-ICPC, trường mình đều có tham gia, và có kế hoạch ôn luyện. Nhưng năm nay, tới thời điểm này thì chưa thấy tổ chức ôn luyện. Trong những năm qua, dù có phổ biến nhưng thuật toán vẫn chỉ là 1 khái niệm mơ hồ, không đáng quan tâm của đa số sinh viên trường mình. Mình thấy đây là điều đáng buồn vì trường mình là trường Đại học Công nghệ thông tin.

[11520246]

• Anh Châu ơi [MENTION=7969]09520019[/MENTION] anh có thể làm mẫu thử về việc giải phương trình bậc 3 với các ẩn tự do, em chưa hiểu ý anh nói lắm để hạ từ 3 vòng for xuống còn 2 vòng for.
• Anh An [MENTION=7280]08520001[/MENTION] về bài của Tín em thấy cách anh đưa ra chính là thuật toán Kadane đã được đề cập ở Wikipedia - Maximum subarray problem, giải pháp đưa ra là duyệt toàn bộ mảng và dĩ nhiên độ phức tạp là vào khoảng tuyến tính O(n) với n là độ dài mảng.

Ngoài ra trên trang wiki trên cũng có nhắc đến một giải pháp khác là dùng Chia để trị để giải quyết bài toán Mảng con lớn nhất mà Tín đã giới thiệu. Em cũng xin chia sẻ thêm những gì đã tìm hiểu, đó là:
Ở đây ta phân chia vấn đề ra theo đúng nguyên tắc chia để trị, cụ thể là chia đôi ra, đại loại mục tiêu ở đây là "tìm mảng con lớn nhất của nửa trái mảng ban đầu", rồi lại "tìm mảng con lớn nhất của nửa phải mảng ban đầu", và rồi sẽ kết hợp lại để có được "mảng con lớn nhất". Như vậy từ mảng ban đầu ta cứ chia đôi ra, tìm mảng con lớn nhất ở mỗi bên, rồi gộp lại. Chắc chắc sẽ thực thi bằng đệ quy (giống như Merge Sort bình thường) với trường hợp cơ bản (dừng đệ quy) là khi mảng chỉ có 1 phần tử thì phần tử đó chính là max.

1. Như vậy ta sẽ thực thi một hàm tính tổng một mảng con (có chỉ số cho trước hẳn hoi). (Được một giá trị)
2. Bên cạnh đó ta chia mảng con đó ra làm hai, rồi tìm mảng con lớn nhất, cụ thể là của nửa mảng bên trái, nửa mảng bên phải (Được hai giá trị).
3. Sau đó so sánh và tìm max trong 3 giá trị trên, cứ thế truy hồi ngược trở về mảng có độ dài n ban đầu.
4. Tiếp tục đệ quy, vân vân vân.

Đại loại ý tứ là thế, cũng là do em có đọc được trong sách Introduction to Algorithms (Cormen, Leisserson,..), em có trích cho mọi người tiện đọc:
Trich-MangConLonNhat-Introduction_to_algorithms.pdf
Source Python, mọi người xem sẽ hiểu rõ hơn: max-subarray-divive-n-conquer.py
Làm mẫu chạy thử code:
Khai báo một mảng trong Python IDLE A = [2, 3, ,4 .....] tùy ý
Gọi hàm FindMaxSubArray(A,0, len(A) -1 ) sẽ trả về một bộ 3 thứ gồm: chỉ số đầu, chỉ số cuối, và giá trị của mảng con lớn nhất tìm thấy được.

[08520001]

[MENTION=11756]11520246[/MENTION]: Thuật toán của em thiếu phần thứ 3 thì phải. Em mới nói 2 phần có được từ 2 mảng con trái và phải thôi. Thuật toán chia để trị này hay, nhưng ghi bằng tiếng Anh như vậy, anh sợ nhiều bạn không đọc. Nên em xem lại và ghi chi tiết để những bạn không đọc có thể hiểu được luôn nha. Thanks em.
Và mình khuyến khích các bạn sau khi hiểu 2 thuật toán này thì nên code bài này với cả 2 thuật toán này luôn.

[11520447]

@Tú: em có thể viết cụ thể hơn không?

Có học qua mấy cái chia để trị ji đó nhưng em ko biết áp dụng.
Nên gặp bài nào em cũng nghĩ ngay đến cách vẹn cạn
Bài này e nghĩ thế này :
- Số phần tử của dãy con tăng dần.
- Mảng có n phần thử thì duyệt n lần (mỗi lần duyệt sẽ có số phần tử trong mảng con khác nhau )
- bonus thêm cái hàm tính tổng mảng con đag xét, so sánh và lưu vào 1 biến kq

[12520244]

thấy mấy anh thảo luận sôi nổi quá, thấy thích ghê :byebye: giờ em mới để ý mấy thời gian lướt facebook, haivl vô ích quá, em thích code mà giờ trình độ vẫn bập bẹ :sad:, phải đầu tư thêm thôi, có gì mấy anh giúp đỡ em nha :funny:

[09520019]

[*]Anh Châu ơi [MENTION=7969]09520019[/MENTION] anh có thể làm mẫu thử về việc giải phương trình bậc 3 với các ẩn tự do, em chưa hiểu ý anh nói lắm để hạ từ 3 vòng for xuống còn 2 vòng for.

thế này nhé: bài toán là a^3 + b^3 + c^3 = 100a + 10b + c
Bình thường chúng ta sẽ chạy 3 vòng for a,b,c để tìm nghiệm, tuy nhiên nếu để ý rằng ta chạy 2 vòng for thôi, thì ẩn còn lại sẽ trở thành 1 phương trình bậc 3. Mình thích chọn hệ số a b c nhỏ, nên chạy a và b, còn lại ẩn c, tức là

c^3 - c + (a^3 + b^3 - 100a - 10b) = 0 (I)

Đối với phương trình bậc 3 thì có công thức nghiệm. Công thức nghiệm này có thể tính trong O(1), cũng như công thức nghiệm pt bậc 2 vậy. Cho nên áp dụng công thức nghiệm thôi


(I) là phương trình bậc 3 tổng quát Ac^3 + Bc^2 + Cc + D = 0 với các hệ số A = 1, B = 0,C = -1, D = a^3 + b^3 - 100a - 10b (II)
ngoài ra nó cũng là phương trình bậc 3 suy biến c^3 + pc + q = 0 với p = -1 và q = a^3 + b^3 - 100a - 10b (III)

Nên bạn có nhiều lựa chọn:

http://en.wikipedia.org/wiki/Cubic_equation#Three_real_roots

Theo wiki, bạn có thể dùng cách giải tổng quát cũng được, nhưng khá dài.
Phương pháp Carnado là phương pháp dùng trong SGK, thường mình không dùng phương pháp này.

Thường thì mọi người thích phương trình suy biến hơn (III)

+ Carnado, dùng phương pháp này bạn chắc chắn tìm ra được 1 nghiệm, sau đó bạn chia đa thức cho đơn thức, tìm ra 2 nghiệm còn lại bằng phương trình bậc 2, hoặc cách khác là bạn tìm ra được 6 nghiệm, và thử lại 6 nghiệm này. Do đó mình mới đề xuất thêm Vieta
+ Vieta:
phương trình:
Đặt
Tức là ra phương trình
Nhân 2 vế với w^3
Đây là dạng phương trình bậc 2 của w^3. Tìm ra được nghiệm, thay vào cái phần đặt t hồi nãy.


Mấy cái phương pháp trên thì mệt nhất là lúc đụng vào số ảo, ưu điểm là không đụng lượng giác. Nhưng mà cách làm lượng giác thì nhanh và không phải lo số ảo. Nên hồi trước mình dùng công thức nghiệm bằng lượng giác cho nhanh ở wiki tiếng Việt http://vi.wikipedia.org/wiki/Ph%C6%B...b%E1%BA%ADc_ba

Đặt:



Xét 4 TH theo như wikipedia, cả 4 TH đều có công thức nghiệm sẵn, bạn cứ ráp vào là ra.

[08520001]

[MENTION=11957]11520447[/MENTION]: Thông thường vét cạn là cách dễ hiểu, dễ code nhất. Tuy nhiên trong đa số trường hợp, nó chạy khá chậm. Vd bài này em duyệt n lần, mỗi lần duyệt, em duyệt thêm 1 số lần để tính tổng mảng con, cập nhật kết quả nữa. Thì số lần lặp sẽ rất lớn. Với n nhỏ