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

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

bởi CodeGym | 25/03/2024 15:28 | Blog

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:

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.

Đấy là những gì chúng ta cần làm khi giải quyết một bài toán với giải thuật, nhưng như vậy không có nghĩa là xong. Khi chúng ta học tập hay rèn luyện cái gì đấy, luôn luôn phải dành thời gian sau khi hoàn thành để tổng kết lại những gì mà chúng ta đã làm được cũng như đã nhận được. Hãy đưa ra những câu hỏi như là:

Chúng ta luôn luôn gặt hái được kinh nghiệm từ những gì mình làm (và cả người khác nữa). Đấy là một kho tàng rất quý giá để bản thân có thể khai thác và làm hành trang cho sau này giúp bạn có thể phát triển hơn nữa trong tương lai nên đừng lãng phí nó. Nếu bạn luyện tập giải các bài toán “solve prolem” trên các trang luyện thuật toán như hackerrank, leetcode hay geeksforgeeks,… luôn có một mục leader board gồm những người đã giải bài toán ấy từ trước bạn. Hãy dành thời gian để xem code của họ, điều này vừa giúp bạn khả năng đọc hiểu code, vừa giúp bạn có thể cover những ý tưởng hay, những thuật toán tối ưu hơn trong những trường hợp tương tự với bài toán ấy. Bạn sẽ nhận ra là mình học được rất nhiều điều từ những người ấy, và nó sẽ giúp bạn phát triển nhiều hơn trong cả khả năng triển khai code, tư duy giải quyết vấn đề cũng như cách bạn chọn lựa thuật toán cũng như cách sử dụng những hàm có sẵn (trong ngôn ngữ lập trình mà bạn dùng) để giải quyết bài toán một cách nhanh gọn và tiết kiệm công sức hơn.

Nhiều khi cách giải của bạn đã rất tối ưu và ngon nghẻ, nhưng khi bạn xem những cách giải của người khác, bạn nhiều khi sẽ bất ngờ với những ý tưởng không ngờ tới của các “bộ não thế giới” ấy, bạn luôn có thể gặt hái được những bài học riêng từ chúng, như là việc có thể suy nghĩ từ nhiều hướng, nhiều phía, nhiều khả năng chẳng hạn. Và nhớ rằng, phải hiểu những gì mà dòng code của họ thể hiện, muốn cover nó thì phải hiểu trước đã. Và khi bạn gặp một bài toán có thể “mượn nhờ” ý tưởng ấy từ những người anh em thiện lành đi trước ấy, bạn mới có thể sử dụng nó như là một cách của chính bạn được. Cover nhưng đừng copy, hãy là một nghệ sĩ thay vì một “đạo sĩ”.

Nhiều người khi tiếp cận với thuật toán thì nghĩ bản thân không có năng khiếu hay không thể làm được, khó thế nhở mình thực sự không hợp với nó, nó quá khó với mình. Tuy nhiên:

Những gì bạn thích chưa chắc bạn đã giỏi, nhưng khi bạn giỏi thì bạn sẽ thích.

Đừng bao giờ nghĩ mình không có năng khiếu hay khả năng về một thứ gì đó mà bỏ cuộc, bạn luôn có thể thích nó khi bạn trở nên giỏi hơn, nếu bạn không có tài năng, bạn chỉ cần giỏi ở mức độ mà bạn có thể là được rồi, và khi ấy bạn sẽ thấy nó thú vị thôi. Mong là mọi người sẽ trở nên thích thú hơn với thuật toán. See ya!

Author: Trần Văn Hải

(Bài chia sẻ gốc: https://medium.com/cg-dev/solve-algorithm-problems-9117e3784b68)

Xem thêm các bài chia sẻ, hướng dẫn học lập trình khác tại đây.

Tags:

2 Lời bình

  1. Ẩn danh

    Tác giả chưa kiểm soát được từ ngữ. “Cái hệ thống giáo dục củ chuối” là một phát ngôn thiếu tôn trọng ngành giáo dục và thiếu chuẩn mực.

    Hồi đáp
    • CodeGym

      Rất cảm ơn bạn đọc đã góp ý!
      CodeGym trích dẫn nguyên văn bài viết gốc của tác giả (có ghi nguồn). CodeGym xin được tiếp thu ý kiến và đã điều chỉnh lại từ ngữ cho phù hợp hơn.

      Hồi đáp

Gửi Lời bình

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

BÀI VIẾT LIÊN QUAN

BẠN MUỐN HỌC LẬP TRÌNH?

GỌI NGAY

098 953 44 58

Đăng ký tư vấn lộ trình học lập trình

Đăng ký tư vấn, định hướng lộ trình học và giải đáp các thắc mắc về ngành nghề – Miễn phí – Online.

3 + 7 =

TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM
TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM