Hướng dẫn viết thuật toán giải quyết các vấn đề trong lập trình
Bạn đang tìm hiểu về trình bày chi tiết các cách viết thuật toán. Dưới đây là những nội dung hay nhất do nhóm thcsngogiatu.edu.vn tổng hợp và biên soạn, xem thêm ở chuyên mục Hỏi Đáp.
Thuật toán là gì?
Một thuật toán, còn được gọi là thuật toán, là một tập hợp hữu hạn hoặc tập hợp các quy tắc nghiêm ngặt về hướng dẫn, phương pháp hoặc chuỗi hoạt động trên một đối tượng được chỉ định và xác định rõ. rõ ràng để hoàn thành một số thứ từ một trạng thái ban đầu nhất định; khi những chỉ thị này được áp dụng đầy đủ sẽ dẫn đến kết quả cuối cùng như mong đợi.
Nói cách khác, thuật toán là một tập hợp các quy tắc hoặc quy trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn hoặc cung cấp kết quả từ một tập hợp dữ liệu đầu vào. (Theo wikipedia)
Chúng ta học thuật toán để làm gì?
Hmm… Điều đầu tiên bạn cần nghĩ đến, đó là tư duy giải quyết vấn đề – thứ mà một lập trình viên nên có (bạn không có cũng không sao, nhưng nó rất cần thiết nếu bạn muốn gắn bó với CNTT). Đừng đánh giá thấp, cũng không đánh giá quá cao liệu bạn có giỏi thuật toán hay không. Bạn không cần thuật toán để có thể làm việc trong CNTT, nhưng có những lĩnh vực đòi hỏi khắt khe, thậm chí rất khắt khe bạn mới có thể sử dụng tốt thuật toán như: học máy, khai thác dữ liệu, mã hóa dữ liệu… Giỏi thuật toán cũng giúp chúng ta có một tư duy giải quyết vấn đề tốt, tìm ra cách giải quyết nhanh hơn, tìm ra cách giải quyết tối ưu hơn cho bộ nhớ cũng như hiệu năng của chương trình, v.v.
Tiếp theo, để phỏng vấn, vâng, để phỏng vấn và tìm cho mình một công ty và công việc phù hợp. Hiện nay có khá nhiều công ty IT tuyển dụng lập trình viên test thuật toán. Họ kiểm tra khả năng giải quyết vấn đề, khả năng trình bày ý tưởng và kiến thức của chúng tôi về các thuật toán cơ bản để đánh giá mức độ phù hợp của chúng tôi với công việc. Và ngay cả khi họ không đánh giá chúng tôi bằng thuật toán, thì việc biết đó là một điểm cộng.
Ok, vậy là xong bước giới thiệu. Dưới đây là những công việc chúng ta cần làm khi giải một bài toán bằng thuật toán, cùng với những kinh nghiệm giải các bài toán đó mà chúng ta đã có được trong quá trình rèn luyện.
Chú ý thông tin
Hãy thực sự, thực sự chú ý đến vấn đề hiện tại. Mỗi bài toán luôn cho chúng ta những thông tin cần thiết để có thể giải nó, một số (có thể) sẽ cho chúng ta định hướng để có một thuật toán tối ưu nhất có thể. Vì vậy, hãy đảm bảo rằng bạn không bỏ qua bất kỳ chi tiết quan trọng nào được cung cấp và nếu cần, hãy kiểm tra chúng. Đặc biệt chú ý đến các ràng buộc đầu vào và đầu ra, vì chúng cũng rất quan trọng. Có thể cùng một vấn đề, nhưng với các ràng buộc đầu vào khác nhau sẽ mang đến những giải pháp khác nhau cho vấn đề đó. Kiểu dữ liệu hoặc phạm vi của biến cũng thường khiến chương trình của chúng ta bị treo hoặc không đạt được điều 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 và thương của hai số. Vấn đề có thể được giải quyết đơn giản bằng cách chỉ trả lại phép cộng, trừ, nhân và chia 2 số. Nhưng nếu đầu vào là 2 số siêu lớn, mà chúng ta không thể sử dụng biến để lưu nó dưới dạng số (trong ngôn ngữ lập trình của bạn) thì sao? Hay giả, kết quả của nó vượt giới hạn cho phép?
Không có thông tin thừa, chúng không phải là câu đố, cái bẫy trong các bài kiểm tra mà bạn đã lấy từ hệ thống giáo dục củ chuối của chúng tôi, hãy tin tưởng chúng. Và nếu bạn giải quyết vấn đề mà không sử dụng bất kỳ dữ liệu nào, có thể, đó là chìa khóa để có thể tối ưu hóa thuật toán của bạn.
Chẳng hạn với bài toán: Cho 2 mảng đã sắp xếp và các phần tử là duy nhất. Tìm các phần tử chung cho cả hai mảng? Chắc chắn chúng ta có thể giải quyết nó mà không cần quan tâm xem chúng có được sắp xếp hay không (các phần tử duy nhất) bằng cách sử dụng 2 vòng lặp và so sánh thời gian. biến các phần tử của hai mảng lại với nhau. Nhưng dữ liệu “mảng đã sắp xếp” khá quan trọng để chúng tôi tối ưu hóa thuật toán của mình.
Lắng nghe cẩn thận những gì xuất hiện và suy nghĩ về nó giống như cách bạn nhận được những tin nhắn vàng của người ấy.
Cho ví dụ
Các ví dụ thường là cách bạn tiếp cận một cách nhanh nhất để giải một bài toán, từ đó đưa ra các thuật toán khả thi cho bài toán mà bạn gặp phải. Có hai điều cần lưu ý khi tạo các ví dụ tốt cho các vấn đề: nó phải lớn và không đặc biệt. Đừng đưa ra những ví dụ quá nhỏ vì chúng không thể hiện được cốt lõi của vấn đề. Không phải là không nên, mà là không nên. Và vì ví dụ của chúng ta phải là ví dụ tổng quát nhất để đi đến cốt lõi của vấn đề, nên chúng ta nên giới hạn các ví dụ của mình để chứa các trường hợp đặc biệt của vấn đề. Vì ví dụ chỉ chứa một trường hợp thỏa mãn, ví dụ đã cho chỉ chứa các ngoại lệ, v.v.
Kiệt quệ
Nếu bạn không có giải pháp khả thi cho vấn đề của mình hoặc ý tưởng bạn nghĩ ra khá tệ, chạy chậm, tốn tài nguyên, v.v., hãy sử 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ê tất cả các trường hợp có thể xảy ra (dù chúng có khớp hay không).
Thông thường nó vẫn sẽ khiến chương trình chạy rất chậm, nhưng “có còn hơn không”, ít nhất nó sẽ giúp bạn xử lý các đầu vào nhỏ một cách chính xác. Và từ đó, bạn sẽ đi theo hướng đã vạch ra để có thể tiếp cận một giải pháp minh bạch hơn và tốt hơn. Mới bắt đầu bạn có thể code cũng được nhưng khi đã quen với các bước tôi chỉ ra thì bước này nên ở mức chỉ phác thảo ra giấy hoặc nghĩ trong đầu để bạn có thể tối ưu cũng như nghĩ về nó. giải pháp cho vấn đề, không phải mã ngay lập tức.
tối ưu
Đây thường là bước mà bạn sẽ dành nhiều thời gian nhất trong quá trình “giải toán” của mình. Hãy nhớ luôn quay lại bước này khi bạn viết mã xong và nếu bạn nghiêm túc với việc đào tạo. Nó giúp bạn có thói quen tối ưu hóa mã của mình, điều này rất quan trọng và cần thiết cho sự nghiệp lập trình viên sau này của bạn. Thử nghĩ xem, nó cũng giúp bạn tối ưu hóa ý tưởng của mình để khi gặp lại dạng bài này, bạn sẽ “xử lý” nó một cách gọn gàng và nhanh chóng nhất. Thời gian bạn dành để tối ưu hóa mã và thuật toán của mình sẽ mang lại rất nhiều thời gian cho bạn sau này. Tất nhiên, đừng quá mải mê mà quên mất những yếu tố quan trọng khác, hãy từ bỏ đúng lúc và nhận được sự trợ giúp cần thiết nếu mất quá nhiều thời gian.
Xem lại thuật toán 1 lần nữa
Biết chính xác những gì bạn muốn làm với mã của mình. Đừng bỏ qua bước này mà nhảy ngay vào code và kết thúc với một đống code lộn xộn, rác rưởi, hôi hám khiến bạn mắc kẹt trong đó. Hãy nhớ rằng, bạn cần tạo những thói quen nhỏ từng bước để có thể xây dựng những thói quen lớn trong tương lai. Lúc đầu sẽ mất thời gian, nhưng dần dần nó sẽ trở thành bản năng như hơi thở của bạn, bạn không cố gắng làm, nó sẽ tự làm. Hãy rất rõ ràng:
- Tôi sử dụng biến nào (chú ý cách đặt tên – rất quan trọng), cấu trúc dữ liệu gì?
- Làm thế nào và khi nào chúng thay đổi (rất hữu ích cho người mới hiểu quy trình của chương trình)?
- Cấu trúc của mã mà bạn muốn trình bày là gì? Ví dụ: tôi sẽ tạo những hàm và phương thức nào? Các vòng lặp như thế nào? Sử dụng vòng lặp nào?…
Hãy nhớ tìm hiểu thêm về các yếu tố như độ phức tạp của thuật toán, phạm vi biến, bộ nhớ, v.v. Những yếu tố này có thể có tác động lớn đến chương trình của bạn. Và nếu bạn muốn có thể tối ưu hóa tốt các thuật toán và dòng mã của mình thì kiến thức này là vô cùng cần thiết.
Mã số
Khi đã hoàn thành các bước chuẩn bị, bạn cò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 chú ý đến quy ước mã hóa. Có thể ban đầu bạn chưa biết gì về nó, nhưng hãy dành thời gian tìm hiểu và sử dụng nó ngay. Đừng nghĩ về những thứ như bạn vừa mới tiếp xúc, có thể sau này. Đừng! Hãy dành thời gian tìm hiểu về nó và áp dụng ngay sẽ đỡ tốn công sức về sau. Và tại sao nó lại quan trọng? Hãy dành thời gian tìm hiểu, bài viết đã quá dài nên tôi không muốn đi chi tiết về vấn đề này. Nhưng tin tôi đi, không ai không đánh giá cao một người biết và sử dụng tốt quy ước mã hóa. Đó đều là những lập trình viên đáng yêu và được yêu mến nhất quả đất. Hơn nữa nếu bạn có mặt trong buổi phỏng vấn bạn sẽ có một điểm cộng rất lớn.
KIỂM TRA
Và sau khi code xong, tất nhiên bạn cần test bằng các test case để xem chương trình của mình đã tốt và đáp ứng được yêu cầu chưa. Tại thời điểm này, các 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 các trường hợp thử nghiệm làm cạn kiệt tất cả các trường hợp có thể xảy ra và ngoại lệ trong bài toán. Nếu bạn đang luyện trên các trang web thuật toán, sẽ có hệ thống kiểm tra giúp bạn.
Nếu xảy ra lỗi hoặc sự cố, hãy lưu ý về cú pháp và lỗi chính tả mà bạn có thể mắc phải trong chương trình, xem xét từng dòng và sử dụng gỡ lỗi gỡ lỗi nếu cần để sự cố có thể được giải quyết. Nếu chỉ là những lỗi cơ bản như lỗi cú pháp, hệ thống gỡ lỗi sẽ giúp bạn tìm ra những lỗi đơn giản. Nhưng nếu đó là một lỗi phát sinh trong quá trình chạy chương trình, thì “của tôi”. Cách dùng thì các 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 trượt một số bài kiểm tra, hoặc thậm chí thất bại tất cả, hãy kiểm tra lại với các trường hợp kiểm tra nhỏ để xem vấn đề nằm ở đâu. Phân tích cách chương trình của bạn chạy, xem từng dòng mã, bạn sẽ sớm tìm ra vấn đề ở đâu đó. Đi từ các trường hợp thử nghiệm nhỏ đến các trường hợp thử nghiệm lớn, sau đó là các trường hợp thử nghiệm 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 vấn đề còn tồn tại trong chương trình của bạn và giải quyết nó.
Hãy nhớ rằng, thực sự tập trung vào các trường hợp thử nghiệm. Và khi bạn kiểm tra, bạn đang kiểm tra chương trình, không phải thuật toán mà bạn có. Nếu chương trình không có vấn đề, thì hãy nghĩ về thuật toán. Nếu lỗi thực sự nằm ở thuật toán không phù hợp, hãy nghĩ ra một thuật toán khác, một hướng đi mới, đừng “cố đấm ăn xôi”.
Một lưu ý nhỏ cuối cùng là hãy sửa lỗi bằng trái tim của bạn. Đừng đối phó với cách bạn xem các bài kiểm tra là đúng sau đó bạn trả về đúng cho chương trình của mình hoặc đại loại như thế. Nó cho thấy bạn đang quá hời hợt với những nỗ lực của mình, hoặc bạn chưa hiểu rõ vấn đề. Hãy suy nghĩ kỹ về vấn đề gây ra lỗi, đừng cố gắng sửa nó để thỏa mãn 1 hoặc 2 trường hợp, vì có thể lỗi các trường hợp khác. Hãy luôn giữ một đầ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 đề mà bạn đang hướng tới, đừng “con săn sắt bỏ con cá rô”.
Nếu bạn gặp khó khăn và cảm thấy nó mất quá nhiều thời gian, hãy kiên trì với nó và nhớ rằng khi bạn đã quen với nó, bạn sẽ giải quyết nó nhanh hơn vào lần sau. Tất nhiên, nếu nó làm bạn khó chịu và bạn thực sự dành nhiều thời gian cho nó, hãy để nó ở đó và quay lại khi nó sẵn sàng. Đừng bỏ cuộc.
Đó là điều chúng ta cần làm khi giải một bài toán bằng thuật toán, nhưng không có nghĩa là xong. Khi chúng ta nghiên cứu hay thực hành một điều gì đó, bao giờ cũng phải dành thời gian sau khi kết thúc để tổng kết lại những gì chúng ta đã làm cũng như đã nhận được. Đặt câu hỏi như:
- Tôi có thể tối ưu hóa thuật toán này nhiều hơn không?
- Tôi đã gặp vấn đề gì khi giải quyết nó?
- Có sai lầm nào mà tôi thường lặp đi lặp lại không? Làm thế nào để hạn chế tối đa những sai sót phát sinh trong tương lai?
- Làm thế nào có những người khác thực hiện bài này? Tôi có thể học được gì từ họ?
Chúng tôi luôn tích lũy kinh nghiệm từ những gì chúng tôi làm (và những người khác cũng vậy). Đó là một kho tàng vô cùng quý giá để bản thân khai thác và chuẩn bị cho sau này giúp bạn phát triển hơn nữa trong tương lai, vì vậy đừng lãng phí nó. Nếu bạn thực hành giải các bài toán “giải bài toán” trên các trang đào tạo thuật toán như hackerrank, leetcode hoặc geeksforgeek, v.v., thì luôn có một phần ban lãnh đạo gồm những người đã giải bài toán 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 hiểu code, vừa giúp bạn bao quát được những ý tưởng hay, 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. Bạn sẽ thấy mình học hỏi được rất nhiều điều từ những người này, và nó sẽ giúp bạn phát triển hơn cả về khả năng triển khai code, tư duy giải quyết vấn đề cũng như cách bạn chọn thuật toán và cách sử dụng chúng. Sử dụng các hàm có sẵn (bằng ngôn ngữ lập trình của bạn) để giải quyết vấn đề nhanh hơn và tiết kiệm nhiều công sức hơn.
Nhiều khi cách giải của bạn rất tối ưu và ngon lành, nhưng khi xem lại cách giải của người khác, bạn sẽ thường bất ngờ với những ý tưởng không thể ngờ tới của những “bộ óc thiên hạ” đó, bạn luôn có thể rút ra bài học cho mình từ họ, kiểu như có thể suy nghĩ từ nhiều hướng, từ nhiều phía, từ nhiều khả năng. Và nhớ là để hiểu code của họ thể hiện cái gì, bao hàm cái gì thì bạn phải hiểu nó trước đã. Và khi gặp bài toán có thể “mượn” ý tưởng đó từ những anh em đi trước giỏi, bạn có thể vận dụng nó theo cách của mình. Cover nhưng đừng sao chép, hãy là một nghệ sĩ thay vì một “pháp sư”.
Nhiều người khi tiếp cận với thuật toán đều nghĩ mình không có năng khiếu hoặc không làm được, nó khó nhớ đến nỗi mình thực sự không phù hợp với nó, nó quá khó đối với tôi. Tuy nhiên:
Đừng bao giờ nghĩ rằng bạn không có tài năng hay khả năng gì đó và từ bỏ, bạn luôn có thể tận hưởng nó khi bạn tiến bộ hơn, nếu bạn không có tài năng, bạn chỉ cần làm tốt công việc của mình. có thể được, và rồi bạn sẽ thấy nó thú vị. Hi vọng mọi người sẽ quan tâm hơn đến thuật toán. Hẹn gặp lại sau!
[TDLT] Nhập môn tư duy thuật toán (phần 1)
[TDLT] Nhập môn tư duy thuật toán (phần 1)
[TDLT] Nhập môn tư duy thuật toán (phần 1)
Thuật toán là một dãy hữu hạn các phép toán được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy phép toán đó, từ Đầu vào của bài toán, ta thu được Đầu ra cần tìm.
Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán, ta thu được Output cần tìm.
Văn phòng phẩm: thuật toán phải kết thúc sau một số hoạt động hữu hạn.
– Tính tất định: sau khi thực hiện 1 phép toán thì thuật toán kết thúc hoặc còn đúng 1 phép toán xác định được thực hiện tiếp theo.
– Định nghĩa: Số nguyên dương N là số nguyên tố nếu nó có đúng hai ước là 1 và N″.
– Bước 7: Nếu i = N thì thông báo ″N là số nguyên tố″, ngược lại thông báo ″N không phải là số nguyên tố″, kết thúc;
Chú ý: Nếu N = 4 và không có ước nào giữa 2 và căn bậc hai của N thì N là số nguyên tố.
– Với mỗi cặp số hạng kề nhau trong dãy, nếu số lớn hơn số liền nhau thì ta đổi chỗ chúng. (Các số lớn sẽ được đẩy về vị trí xác định ở cuối dãy).
– Việc này được lặp lại nhiều lần, mỗi lượt thực hiện nhiều phép so sánh cho đến khi không xảy ra hoán đổi nữa.
– Input: Dãy gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k (key)
– Dữ liệu ra: Vị trí i mà ai = k hoặc thông báo k không tìm thấy trong dãy. Vị trí của 2 trong dãy là 5 (không tìm thấy 6).
Việc tìm kiếm tuần tự được thực hiện một cách tự nhiên: Lần lượt từ số hạng đầu tiên, ta so sánh giá trị của số hạng đang xét với khóa cho đến khi gặp một số hạng bằng với khóa hoặc dãy đã xét mà không cần tìm. xem giá trị của khóa trên mảng.
– Bước 5: Nếu i N thì nhận thấy dãy A không có số hạng nào bằng k rồi chấm hết;
– Dữ liệu vào: Dãy A là một dãy tăng gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k.
– Dữ liệu ra: Vị trí i mà ai = k hoặc thông báo k không tìm thấy trong dãy số. Vị trí của 21 trong dãy số là 6 (không tìm thấy 25).
Sử dụng tính chất sắp xếp tăng dần của dãy A, ta tìm được cách thu hẹp nhanh vùng tìm bằng cách so sánh k với từ ở giữa dãy tìm (between) thì chỉ xảy ra một trong ba trường hợp sau:
Quá trình trên được lặp lại cho đến khi tìm thấy khóa k trên phạm vi A hoặc phạm vi tìm kiếm trống.
– Bước 7: Nếu Terminal, thông báo không tìm thấy phím k trên dãy, rồi chấm dứt;
- Câu 1 trang 44 SGK Tin học 10
- Câu 3 trang 44 SGK Tin học 10
- Câu 2 trang 44 SGK Tin học 10
- Câu 4 trang 44 SGK Tin học 10
- Câu 6 trang 44 SGK Tin học 10
- Câu 6 trang 162 SGK Tin học lớp 10
- Câu 2 trang 162 SGK Tin học 10
- Lý Thuyết Và Thực Hành Bài 10: Sử dụng trình duyệt Internet Explorer trang 152 SGK Tin Học 10
- Hướng dẫn thực hành 10: Sử dụng trình duyệt Internet Explorer trang 152 SGK Tin học 10
- Bài tập 11: Thư điện tử và máy tìm kiếm thông tin trang 155 SGK Tin học 10
