Hướng dẫn viết thuật toán giải quyết các vấn đề trong lập trình

Nếu bạn là người mới bắt đầu vào làm quen với học lập trình, chắc hẳn bạn cũng biết về thứ được gọi là “thuật toán”. Với kinh nghiệm là một người đi trước trong việc giải kha khá các bài toán giải thuật trên hacker-rank, mình có đôi dòng chia sẻ về phương hướng giải quyết các bài toán ấy cho các newbie trong vấn đề này.

Trước tiên, nói một chút về thứ mà chúng ta nhắc đến:

Thuật toán là gì?

Thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn hay một dãy các quy tắc chặt chẽ của các chỉ thị, phương cách hay 1 trình tự các thao tác trên một đối tượng cụ thể được xác định và định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán trước.

Nói cách khác, thuật toán là một bộ các quy tắc hay quy trình cụ thể nhằm giải quyết một vấn đề nào đó trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào. (Theo wikipedia)

Chúng ta học thuật toán để làm gì?

Hmm….Thứ đầu tiên bạn cần nghĩ tới, đó là tư duy giải quyết vấn đề– thứ mà một lập trình viên nên có (không có cũng không sao, nhưng rất cần nếu bạn muốn gắn bó với nghề IT). Đừng coi thường, cũng đừng đánh giá cao việc bản thân có tốt thuật toán hay không. Bạn không cần thuật toán để có thể làm việc trong ngành IT, nhưng có những lĩnh vực đòi hỏi, thậm chí là đòi hỏi rất cao việc bạn có thể sử dụng tốt thuật toán như: machine learning, data mining, mã hóa dữ liệu,… Việc giỏi thuật toán cũng giúp chúng ta có tư duy giải quyết vấn đề tốt, tìm hướng giải quyết nhanh hơn, tìm được giải pháp tối ưu hơn cho bộ nhớ cũng như hiệu suất làm việc chương trình,…

Tiếp theo thì, để phỏng vấn, đúng vậy, để phỏng vấn và tìm cho mình một công ty, một công việc phù hợp đấy. Hiện tại thì có khá nhiều công ty IT tuyển các lập trình viên với các bài test về thuật toán. Họ test chúng ta khả năng giải quyết vấn đề, khả năng trình bày ý tưởng và kiến thức về các giải thuật cơ bản để đánh giá khả năng của chúng ta có phù hợp với công việc không. Và ngay cả khi họ không đánh giá chúng ta qua thuật toán, biết nó cũng là một điểm cộng.

Ok, vậy là đã xong bước giới thiệu. Sau đây là những thứ chúng ta cần thực hiện khi giải quyết 1 bài toán với giải thuật, kèm theo đó là những kinh nghiệm trong việc giải quyết những bài toán ấy mà mình đã thu được trong quá trình rèn luyện.

7 bước để giải quyết 1 bài toán

Chú ý các thông tin

Hãy thật sự, thật sự chú ý đến vấn đề được đưa ra. Mỗi bài toán luôn đưa ra cho chúng ta những thông tin cần thiết để có thể giải quyết nó, một trong số chúng (có thể) mang đến cho chúng ta định hướng để có thể có một thuật toán tối ưu nhất có thể. Vì thế, hãy đảm bảo rằng bản thân đã không bỏ qua bất cứ một chi tiết quan trọng nào được đưa ra, nếu cần, hãy đánh dấu chúng lại. Đặc biệt chú ý những ràng buộc về input và output, vì chúng cũng rất quan trọng. Có thể với một bài toán như nhau, nhưng với ràng buộc đầu vào khác nhau sẽ mang lại những cách giải quyết khác nhau cho bài toán ấy. Kiểu dữ liệu hay phạm vi của biến cũng thường khiến cho chương trình của chúng ta trục trặc hoặc không đạt được những gì chúng ta mong muốn.

Ví dụ, một bài toán đơn giản như tìm tổng, hiệu, tích, thương của 2 số. Bài toán có thể giải quyết đơn giản là return lại phép cộng, trừ, nhân, chia của 2 số mà thôi. Nhưng nếu như input là 2 số siêu siêu lớn, thứ mà chúng ta không thể dùng biến để lưu trữ nó dưới dạng số (trong ngôn ngữ lập trình bạn dùng) thì sao? Hoặc giả, kết quả của nó vượt qua giới hạn cho phép?

Không có thông tin nào dư thừa cả, chúng không phải là những câu đánh đố, những câu bẫy trong các bài thi mà bạn đã từng thi do hệ thống giáo dục của chúng ta mang lại, tin tưởng chúng. Và nếu như bạn giải quyết bài toán mà không cần dùng đến dữ liệu nào đấy, có thể, nó là chìa khóa để bạn có thể tối ưu thuật toán của mình.

Ví dụ, với bài toán: Cho 2 mảng đã được sắp xếp và các phần tử là duy nhất. Tìm các phần tử chung của cả 2 mảng?
Chắc chắn chúng ta có thể giải quyết nó mà không cần phải quan tâm chúng có được sắp xếp hay chưa (phần tử duy nhất thì có) bằng cách dùng 2 vòng lặp và so sánh lần lượt các phần tử của 2 mảng với nhau. Nhưng dữ kiện “mảng đã được sắp xếp” lại khá quan trọng để chúng ta có thể tối ưu thuật toán của mình.

<?php
define("FIRST_INDEX_ARRAY2", 0);

function findCommonElements($array1, $array2) {
    $indexFlag = FIRST_INDEX_ARRAY2;
    $commonElements = [];
    $lengthArray2 = count($array2);
    // O(m+n)
    foreach ($array1 as $elementArr1) {
        while($indexFlag < $lengthArray2 && 
              $array2[$indexFlag] <= $elementArr1) {
            if ($array2[$indexFlag] === $elementArr1) {
                array_push($commonElements, $elementArr1);
            }
            $indexFlag++;
        }
    }

    return $commonElements;
}

Hãy lắng nghe thật cẩn thận những gì vấn đề được đưa ra và suy nghĩ về chúng như cách mà bạn đón nhận những tin nhắn vàng ngọc của crush bạn vậy.

Đưa ra các ví dụ

Các ví dụ thường là cách bạn tiếp cận cách giải quyết bài toán nhanh nhất, theo đó đưa ra những thuật toán khả thi cho bài toán bạn có. Có 2 điều cần lưu ý khi tạo ra các ví dụ tốt cho các bài toán đó là: nó phải lớn và không trường hợp đặc biệt. Đừng tạo ra những ví dụ quá nhỏ vì không thể hiện được vấn đề trọng tâm của bài toán. Không phải là không được, nhưng là không nên. Và vì ví dụ của chúng ta nên là tổng quan nhất để có thể nắm được cốt lõi vấn đề, chúng ta nên hạn chế ví dụ có chứa các trường hợp đặc biệt của bài toán. Như là ví dụ chỉ chứa một trường hợp thỏa mãn, ví dụ đưa ra chỉ chứa trường hợp ngoại lệ,….

// Vẫn là bài toán tìm phần tử chung ở trên.
A = [3,5,7,14]    // dữ liệu quá nhỏ
B = [3,6,10,30]   // trường hợp đặc biệt với 2 mảng có số phần tử 
                  // như nhau và chỉ có 1 phần tử chung
=>
A = [3,5,7,10,15,25,30]
B = [3,6,8,10,13]

Vét cạn

Nếu như bạn đang không có một hướng giải quyết nào khả thi cho bài toán của mình, hoặc ý tưởng mà bạn đưa ra nó khá là tệ, chạy chậm, tốn tài nguyên,…hãy dùng thuật toán vét cạn. Thuật toán vét cạn là thuật toán sẽ liệt kê hết tất cả các trường hợp có thể xảy ra(dù phù hợp hay không).

// tiếp tục với bài toán ở trên
function findCommonElements($array1, $array2){
    $commonElements = [];
    //O(m*n)
    foreach($array1 as $elementArr1) {
        foreach($array2 as $elementArr2) {
            if ($elementArr1 === $elementArr2) {
                array_push($commonElements, $elementArr1);
            }
        }
    }
    return $commonElements;
}

Thường thì nó cũng vẫn sẽ khiến cho chương trình chạy rất chậm, nhưng “méo mó có hơn không”, ít ra nó sẽ giúp bạn giải quyết những input nhỏ chính xác. Và từ đấy, bạn sẽ lần mò theo phương hướng đã được vạch ra để có thể tiếp cận đến một hướng giải quyết sáng suốt và tôí ưu hơn. Nếu mới bắt đầu, các bạn có thể code nó, nhưng khi bạn đã làm quen dần với các bước mà mình đã chỉ, bước này nên chỉ ở mức nháp trên giấy hoặc suy nghĩ trong đầu để có thể tối ưu cũng như nghĩ ra phương hướng giải quyết cho bài toán, chứ đừng code ngay.

Tối ưu

Đây thường là bước mà bạn sẽ dành thời gian nhiều nhất trong quá trình “giải toán” của bạn. Hãy ghi nhớ luôn luôn quay lại bước này khi bạn đã code xong, và nếu bạn thực sự nghiêm túc trong chuyện rèn luyện. Nó giúp bạn có một thói quen tối ưu hóa các dòng code của mình, rất quan trọng và cần thiết cho sự nghiệp lập trình viên tương lai của bạn. Nghĩ xem, nó còn giúp bạn có thể tối ưu hóa ý tưởng của mình để khi gặp lại dạng bài này một lần nữa, bạn sẽ “xử đẹp” nó một cách gọn gàng và nhanh chóng nhất. THời gian bạn bỏ ra để tối ưu code và thuật toán của bạn sẽ bù đắp lại rất rất nhiều thời gian cho bạn sau này. Tất nhiên, cũng đừng nên quá sa đà mà bỏ quên những yếu tố quan trọng khác nữa, hãy từ bỏ đúng lúc và tìm sự trợ giúp cần thiết nếu mất quá nhiều thời gian cho nó.

Xem xét lại thuật toán 1 lần nữa

Hãy biết chính xác điều mà bạn muốn thực hiện với những dòng code của mình. Đừng có bỏ qua bước này rồi lao vào code luôn để rồi tạo ra một đống code hổ lốn, rác, bốc mùi và khiến bạn mắc kẹt trong đó. Nhớ rằng, bạn cần tạo nên thói quen nhỏ từng bước để có thể xây dựng nên những thói quen lớn trong tương lai. Lúc đầu sẽ mất thời gian, nhưng sau này nó sẽ trở thành bản năng như việc hít thở của bạn vậy, bạn không cố làm nó, mà là nó tự làm. Hãy xác định thật rõ ràng:

• Mình sử dụng những biến gì (chú ý cách đặt tên- rất quan trọng), cấu trúc dữ liệu nào?
• Cách và thời điểm chúng thay đổi (rất hữu dụng cho người mới để có thể nắm được luồng đi của chương trình)?
• Cấu trúc code mà bạn muốn trình bày nó như thế nào?
  Vd: mình sẽ tạo những hàm, method nào? Các vòng lặp như nào? Sử dụng vòng lặp gì?…

Hãy nhớ tìm hiểu thêm về những yếu tố như độ phức tạp thuật toán, phạm vi biến, bộ nhớ,… Những điều này có thể ảnh hưởng không nhỏ đến chương trình của bạn. Và nếu muốn có thể tối ưu tốt các thuật toán cũng như những dòng code của mình, kiến thức này là rất cần thiết.

Code

Khi đã làm xong những bước chuẩn bị thì còn chần chờ gì nữa mà không bắt tay vào code và tận hưởng thành quả. Nhưng bạn cần phải chú ý về coding convention. Có thể mới đầu bạn chưa biết gì về nó, nhưng hãy dành thời gian tìm hiểu và vân dụng nó ngay. Đừng nghĩ những thứ như mình vừa mới tiếp xúc, chắc để sau cũng được. Đừng! Dành thời gian để tìm hiểu về nó và áp dụng luôn và nó sẽ tiết kiệm công sức cho bạn sau này. Và vì sao nó quan trọng á? Hãy dành thời gian tìm hiểu, bài viết đã quá dài nên mình không muốn đi sâu vào nói về vấn đề này. Nhưng tin mình đi, không ai không đánh giá cao một người nắm chắc và sử dụng tốt coding convention cả. Đó đều là những lập trình viên đáng yêu và đáng được yêu quý nhất quả đất. Hơn nữa nếu bạn đang trong một cuộc phỏng vấn bạn sẽ có một điểm cộng to đùng đấy.

Test

Và sau khi bạn đã code xong, đương nhiên, bạn cần test với các test case để xem chương trình mình đã ngon nghẻ và đáp ứng yêu cầu chưa. Lúc này thì những ví dụ bạn đưa ra ở bước 2 sẽ trở nên quá đơn giản và tầm thường, nhường chỗ cho những test case vét hết tất cả các trường hợp và ngoại lệ có thể có trong bài toán. Nếu bạn đang rèn luyện trên các trang web về giải thuật, sẽ có hệ thống test giúp bạn.

Nếu có lỗi hay trục trặc xảy ra, lưu ý về cú pháp và lỗi chính tả bạn có thể có trong chương trình, xem xét từng dòng và xử dụng kiểu debug dò mìn nếu cần thiết để có thể giải quyết vấn đề đó. Nếu chỉ là những lỗi cơ bản như lỗi cú pháp thì hệ thống debug sẽ giúp bạn tìm ra được những lỗi sai đơn giản. Nhưng nếu nó là lỗi phát sinh trong quá trình chạy chương trình, hãy “dò mìn”. Phương pháp sử dụng thì bạn tìm hiểu thêm trên mạng, mình không nói nhiều ở đây.

Nếu bạn fail 1 vài test, hoặc thậm chí là fail hết, hãy kiểm tra lại với những test case nhỏ để xem vấn đề nằm ở đâu. Phân tích chương trình của bạn chạy như thế nào, xem xét từng dòng code một, bạn sẽ sớm tìm thấy vấn đề ở đâu đấy thôi. Đi từ những test case nhỏ dần lên các test case lớn, rồi các test case chứa các trường hợp đặc biệt. Phân tích và suy nghĩ cẩn thận để có thể giải quyết những vấn đề tồn đọng trong chương trình của bạn và giải quyết nó.

Nhớ rằng, hãy thực sự tập trung vào các test case. Và lúc test, là bạn đang test chương trình chứ không phải giải thuật mà bạn có. Nếu chương trình không vấn đề thì mới suy nghĩ đến thuật toán. Nếu lỗi thực sự nằm ở thuật toán không thích hợp, hãy suy nghĩ một thuật toán khác, một hướng đi mới, đừng “cố đấm ăn xôi” làm gì.

Một lưu ý nhỏ cuối cùng là bạn hãy fix bug bằng con tim. Đừng đối phó theo kiểu bạn thấy các test đều là true thì bạn return true cho chương trình của mình hoặc thứ gì đó tương tự. Điều đấy thể hiện rằng bạn đang quá hời hợt với công sức bỏ ra của bạn, hoặc do bạn không hiểu vấn đề. Hãy suy nghĩ thật kĩ về vấn đề tạo nên lỗi, đừng cố fix để thỏa mãn 1 hay 2 trường hợp, vì nó có thể làm fail các trường hợp khác. Luôn giữ đầu óc tỉnh táo và suy nghĩ một cách toàn diện nhất, tập trung vào vấn đề bạn hướng đến, đừng vì “bắt con săn sắt bỏ con cá rô”.

Nếu bạn gặp khó khăn và cảm thấy quá mất thời gian, hãy kiên trì, và nhớ rằng khi bạn đã quen với nó, bạn sẽ giải quyết nó nhanh hơn trong các lần sau mà thôi. Tất nhiên là nếu nó sinh ra bực dọc cho bạn và bạn thật sự mất rất nhiều thời gian cho nó, để nó ở đấy và quay lại khi đã sẵn sàng. Đừng từ bỏ.

Nữ thần may mắn sẽ luôn phù hộ cho những người cố gắng.