Kiểm Thử Phần Mềm Là Gì ? Tại Sao Cần Kiểm Thử Phần Mềm

Trong xã hội hiện đại ngày nay, khi công nghệ thông tin lên ngôi và phát triển liên tục mạnh mẽ, sinh hoạt chúng ta hằng ngày đều gắn liền với việc sử dụng các thiết bị điện tử nhằm hỗ trợ cho công việc, sinh hoạt hay cả các hoạt động vui chơi giải trí. Hầu như bất kì thiết bị hay ứng dụng nào đều cũng phải trải qua một quá trình lập trình và được kiểm thử bởi tester trước khi sản phẩm đến tay người dùng.

Đó là một trong những công đoạn mà không một đội ngũ kỹ thuật, lập trình viên nào có thể bỏ qua. Để hiểu rõ hơn về kiểm thử phần mềm, chúng ta sẽ cùng tìm hiểu cụ thể thông qua bài viết dưới đây.

I. Kiểm Thử Phần Mềm Là Gì

Kiểm thử phần mềm là phương pháp kiểm tra xem sản phẩm phần mềm đó trên thực tế có phù hợp với các yêu cầu đã đặt ra hay không, và đảm bảo rằng không có lỗi hay khiếm khuyết. Nó bao gồm việc kiểm tra, phân tích, quan sát và kiểm tra những khía cạnh khác nhau của sản phẩm.

Người kiểm thử phần mềm (Tester) sử dụng kết hợp các công cụ thủ công và tự động. Sau khi tiến hành kiểm thử, Tester báo cáo kết quả cho team phát triển. Mục đích là xác định các lỗi, khiếm khuyết hoặc các yêu cầu còn thiếu so với yêu cầu thực tế.

Cần hiểu được tầm quan trọng của việc kiểm thử đối với mỗi công ty phát triển phát mềm. Với kiểm thử phần mềm, nếu có bất kỳ lỗi nào, nó có thể được xác định sớm và giải quyết trước khi giao sản phẩm.

Nhiều công ty phát triển phần mềm thường bỏ qua bước này vì ngân sách eo hẹp và cho rằng nó sẽ không dẫn đến hậu quả lớn. Nhưng để tạo những trải nghiệm tốt nhất cho khách hàng, chất lượng sản phẩm cần phải được đặt lên hàng đầu. Và vì vậy, việc kiểm thử sản phẩm để tìm lỗi là điều gần như bắt buộc.

Doanh nghiệp chỉ có thể mang đến giá trị cho khách hàng khi sản phẩm cung cấp được coi là lý tưởng. Và để đạt được điều đó, các công ty phải bảo đảm rằng người dùng không gặp phải bất kỳ vấn đề nào lúc dùng sản phẩm của mình. Cách tốt nhất để làm điều đó là tạo ra sản phẩm không có lỗi.

Thêm nữa, khi khách hàng sử dụng sản phẩm, họ rất có thể phải tiết lộ một số thông tin cá nhân. Để ngăn chặn tin tặc nắm được dữ liệu này, việc kiểm tra bảo mật là điều bắt buộc trước khi phần mềm đến tay người dùng. Sản phẩm phần mềm được kiểm thử kỹ càng qua quy trình phù hợp sẽ đảm bảo độ tin cậy, bảo mật, giúp tiết kiệm thời gian, chi phí, mang đến sự hài lòng cho khách hàng.

Một lý do nữa khiến việc kiểm thử ngày càng trở nên quan trọng đó là phát hiện khả năng tương thích với các thiết bị và nền tảng khác nhau. Giả sử khi phát triển một trang web, Tester phải kiểm tra xem trang web có chạy trên độ phân giải thiết bị khác nhau, các trình duyệt khác nhau hay không?

Những gì hoạt động tốt trên Chrome có thể không chạy tốt trên Safari hoặc Internet Explorer. Điều này làm phát sinh nhu cầu kiểm tra trình duyệt chéo, bao gồm kiểm tra tính tương thích của ứng dụng trên các trình duyệt khác nhau.

II. Tại Sao Cần Kiểm Thử Phần Mềm

Dù đối với bất kì dự án lập trình phần mềm thì kiểm thử phần mềm là khâu đóng một vai trò quan trọng không thể bỏ qua bởi việc phát hiện lỗi sớm và tìm hướng khắc phục nó chính là cách nhanh nhất và hiệu quả để hoàn thiện sản phẩm trước lúc tới tay người dùng.

Việc kiểm thử phần mềm sẽ giúp đánh giác được hiệu quả chức năng của một ứng dụng phần mềm nhằm mục đích phát hiện những lỗi sai, hay rủi ro, nguy cơ tìm ẩn, ảnh hưởng đến danh tiếng thường, giúp phần mềm đáp ứng được những yêu cầu thiết yếu cụ thể để bảo toàn chất lượng sản phẩm

Một sản phẩm sau khi trải qua quá trình kiểm thử sẽ bảo đảm được độ tin cậy, uy tín, tính bảo mật, hiệu suất cao cũng như giúp tiết kiệm thời gian và chi phí cho khách hàng và người sử dụng. Nếu như sơ sài trong quá trình kiểm thử để xảy ra một lỗi nhỏ hay một thiếu sót cũng có thể gây ra các thiệt hại lớn về kinh tế cũng như con người,…

III. Mục Đích Của Kiểm Thử Phần Mềm

Kiểm thử là 1 quá trình thực thi chương trình với mục đích là tìm ra lỗi/các yếu điểm của chương trình.
Một trường hợp kiểm thử tốt là 1 trường hợp có khả năng lớn trong việc tìm ra những lỗi chưa được phát hiện.
Một trường hợp kiểm thử không tốt ( không thành công) là một trường hợp mà khả năng tìm thấy những lỗi chưa biết tới là rất ít.

Mục tiêu của kiểm thử phần mềm là thiết kế các trường hợp kiểm thử để có thể phát hiện một cách có hệ thống các loại lỗi khác nhau và thực hiện việc đó với lượng thời gian và tài nguyên ít nhất có thể.

IV. Các Phương Pháp Kiểm Thử Phần Mềm

Có nhiều phương pháp kiểm thử khác nhau có thể được các testers sử dụng trong kiểm thử phần mềm. Bài viết này sẽ mô tả ngắn gọn các phương pháp truyền thống, đó là các phương pháp: Kiểm thử hộp đen (Black-Box Testing), Kiểm thử hộp trắng (White-Box Testing) và Kiểm thử hộp xám (Grey-Box Testing).

+ Kiểm thử hộp đen

Khi thực hiện kỹ thuật kiểm thử này, tester không cần quan tâm bên trong hệ thống hoạt động ra sao, không cần hiểu source code thế nào. Thông thường, trong khi thực hiện kiểm thử hộp đen, tester sẽ tương tác với giao diện người dùng của hệ thống bằng cách cung cấp đầu vào và kiểm tra kết quả đầu ra mà không cần biết cách thức làm việc bên trong của hệ thống.
Bảng sau đây liệt kê những ưu điểm và nhược điểm của kiểm thử hộp đen:

Ưu điểm	Nhược điểm
Phù hợp và hiệu quả khi số lượng các dòng lệnh của hệ thống là lớn.	Bị giới hạn bởi độ bao phủ của các trường hợp kiểm thử
Không cần truy cập mã nguồn.	Kiểm thử không hiệu quả, do thực tế tester bị hạn chế kiến thức về hệ thống.
Phân biệt rõ ràng quan điểm của người dùng với quan điểm của nhà phát triển thông qua các vai trò được xác định rõ ràng.	Không có độ bao phủ, vì người kiểm thử không thể kiểm tra các đoạn mã nguồn hoặc tập trung vào các đoạn mã bị lỗi.
Một số lượng lớn tester có kỹ năng vừa phải có thể kiểm tra ứng dụng mà không cần có nhiều kiến thức, ngôn ngữ lập trình hoặc hệ điều hành.	Rất khó để thiết kế được đầy đủ các trường hợp kiểm thử cho hệ thống.

+ Kiểm thử hộp trắng

Kiểm thử hộp trắng là kiểm tra chi tiết về logic luồng hoạt động cũng như source code. Kiểm thử hộp trắng cũng được gọi là Glass testing hay open-box testing. Để thực hiện kiểm thử hộp trắng trên một phần mềm, tester cần phải nghiên cứu hoạt động bên trong của phần mềm cũng như source code để tìm ra đơn vị / đoạn mã nào đang hoạt động không thích hợp.
Bảng sau đây liệt kê những ưu điểm và nhược điểm của kiểm thử hộp trắng:

Ưu điểm	Nhược điểm
Khi tester có kiến thức về mã nguồn cũng như ngôn ngữ lập trình, sẽ trở nên rất dễ dàng để tìm ra loại dữ liệu nào có thể giúp kiểm thử phần mềm một cách hiệu quả.	Do thực tế, tester có tay nghề cao là cần thiết để thực hiện kiểm thử hộp trắng, chi phí được tăng lên.
Giúp tối ưu hóa source code trong hệ thống.	Đôi khi không thể khả thi khi kiểm tra chi tiết từng dòng source code để tìm ra các lỗi tiềm ẩn có thể gây ra vấn đề cho hệ thống, vì nhiều luồng sẽ không được kiểm tra.
Các dòng lệnh không cần thiết hoặc những dòng lệnh có khả năng gây ra các lỗi tiềm ẩn có thể được gỡ bỏ.	Rất khó để duy trì kiểm thử hộp trắng, vì nó đòi hỏi các công cụ chuyên biệt như phân tích source code và công cụ sửa lỗi.
Tester có kiến thức về ngôn ngữ lập trình sẽ dễ dàng để đạt được độ bao phủ cao nhất trong quá trình viết kịch bản kiểm thử.

+ Kiểm thử hộp xám

Kiểm thử hộp màu xám là một kỹ thuật để kiểm thử phần mềm đòi hỏi tester có kiến thức nhất định về các luồng hoạt động bên trong của phần mềm.

Nắm vững domain của 1 hệ thống luôn mang lại cho tester một lợi thế lớn hơn một tester có kiến thức về domain hạn chế. Không giống như kiểm thử hộp đen, phương pháp mà tester quan tâm duy nhất là kiểm thử thông qua giao diện người dùng thì trong kiểm thử hộp xám, tester có quyền truy cập vào tài liệu thiết kế và cơ sở dữ liệu.

Do đó, một tester có thể chuẩn bị dữ liệu kiểm thử cũng như chuẩn bị các kịch bản kiểm thử tốt hơn trong quá trình thực hiện kế hoạch kiểm thử hệ thống.

Ưu điểm	Nhược điểm
Là sự kết hợp của kiểm thử hộp đen và kiểm thử hộp trắng nên có được ưu điểm của cả hai phương pháp này.	Vì không dựa trên việc truy cập vào mã nguồn của hệ thống nên độ bao phủ của các trường hợp kiểm thử bị giới hạn.
Kiểm thử hộp xám không dựa vào mã nguồn; thay vào đó chúng dựa vào tài liệu thiết kế giao diện và các tài liệu đặc tả chức năng.	Các trường hợp kiểm thử có thể bị dư thừa nếu nhà thiết kế phần mềm đã chạy một số trường hợp kiểm thử.
Một tester kiểm thử hộp xám có thể thiết kế các kịch bản kiểm thử thông qua các giao thức kết nối và các kiểu dữ liệu khác nhau.	Kiểm thử mọi luồng đầu vào là không thể bởi vì nó sẽ mất một khoảng thời gian lớn; do đó, nhiều luồng hoạt động sẽ không được kiểm thử.
Việc kiểm thử được thực hiện từ quan điểm của người dùng chứ không phải người thiết kế.

V. Công Cụ Kiểm Thử Phần Mềm

+ Selenium

Selenium là một công cụ kiểm thử phần mềm tự động mã nguồn mở miễn phí cho các ứng dụng web trên nhiều trình duyệt và nền tảng khác nhau như Windows, Mac và Linux. Selenium giúp Tester thực hiện kiểm thử bằng nhiều ngôn ngữ lập trình khác nhau như Java, PHP, C#, Python, Groovy, Ruby và Perl.

Selenium hiện có 3 loại: Selenium Webdriver, Selenium IDE, Selenium Grid. Tùy vào kỹ năng, nền tảng và yêu cầu mà bạn có thể lựa chọn sử dụng loại Selenium phù hợp.

Công cụ này phổ biến với tất cả các trình duyệt nổi tiếng hiện tại như Chrome, Mozila Firefox, Microsoft Edge, Apple Safari, Opera. Vì vậy, Selenium chắc chắn là nền tảng cho hầu hết các công cụ kiểm thử phần mềm khác.

+ TestingWhiz

TestingWhiz là công cụ kiểm thử phần mềm tự động với phiên bản Enterprise cung cấp một gói hoàn chỉnh gồm nhiều giải pháp test tự động khác nhau. Trong đó bao gồm: test web, test phần mềm, test database (cơ sở dữ liệu), test API, test ứng dụng di dộng, bảo trì bộ kiểm tra hồi quy, tối ưu hóa và tự động hóa cũng như kiểm thử trên nhiều trình duyệt.

Ngoài ra, TestingWhiz cung cấp nhiều tính năng quan trọng khác nhau như:

Kiểm thử theo hướng từ khóa (key-word driven), theo hướng dữ liệu (data driven) và kiểm thử phân tán (distributed)
Kiểm thử tiện ích mở rộng trong trình duyệt
Object Eye Internal Recorder
SMTP Integration
Tích hợp với các công cụ theo dõi lỗi như Jira, Mantis, TFS và FogBugz
Tích hợp với các công cụ quản lý kiểm thử như HP Quality Center, Zephyr, TestRail và Microsoft VSTS
Centralized Object Repository (Kho lưu trữ đối tượng tập trung)
Version Control System Integration (Tích hợp hệ thống kiểm soát phiên bản)
Customized Recording Rule (Quy tắc ghi tùy chỉnh)

+ HPE Unified Functional Testing (HP – UFT formerly QTP)

HPE UFT cung cấp tính năng tự động hóa kiểm thử để kiểm thử chức năng và kiểm thử hồi quy cho các ứng dụng phần mềm. Ngôn ngữ script Visual Basic Scripting Edition được ứng dụng bởi công cụ này để đăng ký các quá trình kiểm thử và vận hành các đối tượng và điều khiển khác nhau trong việc test các ứng dụng.

Ngoài ra, QTP cung cấp các tính năng khác như:

Tích hợp với Mercury Business Process Testing và Mercury Quality Center
Nhận dạng Unique Smart Object
Cơ chế xử lý lỗi
Tạo các tham số cho đối tượng, checkpoint và bảng điều hướng dữ liệu
Tài liệu tự động

+ TestComplete

TestComplete là một nền tảng kiểm thử chức năng cung cấp các giải pháp khác nhau để tự động kiểm thử. Công cụ này sử dụng cho máy tính để bàn, web và các ứng dụng di động.

TestComplete cung cấp các tính năng sau:
GUI testing
Hỗ trợ ngôn ngữ test – JavaScript, Python, VBScript, JScript, DelphiScript, C++ Script & C# Script
Kiểm thử trình hiển thị
Kiểm thử theo script (Scripted testing)
Kiểm thử ghi và phát lại (Test recording and playback)

+ Ranorex

Ranorex Studio cung cấp các công cụ tự động hóa testing khác nhau bao gồm việc test tất cả các ứng dụng máy tính để bàn, web và thiết bị di động.

Cụ thể hơn, Ranorex cung cấp các tính năng sau:

Kiểm thử GUI
Có thể tái sử dụng test code
Phát hiện bug
Tích hợp với nhiều công cụ khác nhau
Ghi và phát lại

+ Sahi

Sahi là một công cụ kiểm thử phần mềm tự động hóa áp dụng cho việc test các ứng dụng web. Mã nguồn mở Sahi được viết bằng ngôn ngữ lập trình Java và JavaScript.

Sahi cung cấp các tính năng sau:

Thực hiện kiểm thử nhiều trình duyệt cùng lúc
Hỗ trợ các framework ExtJS, ZK, Dojo, YUI, v.v.
Ghi lại và phát lại khi test trình duyệt

+ Watir

Watir là một công cụ kiểm thử mã nguồn mở được tạo thành từ các thư viện Ruby để tự động kiểm thử ứng dụng web.

Công cụ này cung cấp các tính năng sau:

Kiểm thử bất kỳ ứng dụng web dựa trên ngôn ngữ nào
Kiểm thử trên nhiều trình duyệt
Tương thích với các công cụ phát triển theo định hướng kinh doanh như RSpec, Cucumber và Test / Unit
Kiểm thử các nút, biểu mẫu, liên kết và phản hồi của chúng trên trang web

+ Tosca Testsuite

Tosca Testsuite là một công cụ phần mềm để thực hiện tự động kiểm thử phần mềm chức năng và hồi quy. Ngoài chức năng tự động hóa thử nghiệm, TOSCA bao gồm quản lý kiểm thử tích hợp, giao diện người dùng đồ họa (GUI), giao diện dòng lệnh (CLI) và giao diện lập trình ứng dụng (API).

Tosca Testsuite đi kèm với các tính năng sau:

Lập kế hoạch và thiết kế trường hợp thử nghiệm
Kiểm tra cung cấp dữ liệu
Dịch vụ mạng ảo hóa
Kiểm tra ứng dụng di động
Quản lý tích hợp
Bảo hiểm rủi ro

+ Telerik TestStudio

Telerik TestStudio cung cấp giải pháp để tự động kiểm thử ứng dụng trên máy tính để bàn, web và thiết bị di động bao gồm kiểm thử giao diện người dùng, load và hiệu suất.

Công cụ này cung cấp nhiều khả năng tương thích khác nhau như:

Hỗ trợ các ngôn ngữ lập trình như HTML, AJAX, ASP.NET, JavaScript, Silverlight, WPF và MVC
Tích hợp với Visual Basic Studio 2010 và 2012
Ghi và phát lại
Kiểm thử trên nhiều trình duyệt
Kiểm thử thủ công
Tích hợp với các công cụ theo dõi bug

+ Katalon Studio

Katalon Studio là một công cụ kiểm thử phần mềm tự động hóa miễn phí được phát triển bởi Katalon LLC. Công cụ này được xây dựng dựa trên các framework tự động hóa mã nguồn mở Selenium, Appium với giao diện IDE chuyên biệt để kiểm tra API, web và thiết bị di động. Công cụ này bao gồm một gói đầy đủ các tính năng mạnh mẽ giúp dễ dàng tự động hóa kiểm thử giao diện người dùng web.

Katalon Studio bao gồm các tính năng sau:

Kho lưu trữ đối tượng tích hợp, XPath, nhận dạng lại đối tượng
Hỗ trợ các ngôn ngữ script Java / Groovy
Hỗ trợ tích hợp cho kiểm thử dựa trên hình ảnh
Hỗ trợ các công cụ Tích hợp liên tục như Jenkins & TeamCity
Hỗ trợ Duel-editor Interface
Quy trình thực thi có thể tùy chỉnh

VI. Trắc Nghiệm Kiểm Thử Phần Mềm Có Đáp Án

Câu 1: Mô hình kiểm thử phần mềm TMM là viết tắt của từ tiếng anh nào sau đây?

Chọn một câu trả lời

A) Testing Maturity Model Đúng

B) Testing Model Manufactory Sai

C) Testing Manufactory Model Sai

D) Testing Manual Machanic Sai

Đáp án đúng là: A) “Testing Maturity Model”.Vì: Mô hình kiểm thử phần mềm TMM là viết tắt của từ tiếng Anh: “Testing Maturity Model”.

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp.

Câu 2: Phát biểu nào sau đây là sai về thiết kế kiểm thử?

Chọn một câu trả lời

A) Thực thi sau khi có bản kế hoạch kiểm thử Sai

B) Chỉ định các test case cũng như các bước kiểm thử Sai

C) Có thể dùng cho mọi phiên bản phần mềm Đúng

D) Bảo đảm tất cả các tình huống kiểm thử được quét hết Sai

Đáp án đúng là: C) “Có thể dùng cho mọi phiên bản phần mềm”.Vì: Mỗi phiên bản phần mềm sẽ phải có một bản thiết kế kiểm thử riêng, nó có thể kế thừa từ phiên bản trước đó.

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp.

Câu 3: Đâu là thứ tự thực hiện các bước kiểm thử cơ bản?

Chọn một câu trả lời

Xác định và mô tả test case
Mô tả các bước chi tiết kiểm thử
Xem xét và khảo sát độ bao phủ của việc kiểm thử
Xem xét test case và các bước kiểm thử Đúng

Xác định và mô tả test case
Mô tả các bước chi tiết kiểm thử
Xem xét test case và các bước kiểm thử
Xem xét và khảo sát độ bao phủ của việc kiểm thử Sai

Mô tả các bước chi tiết kiểm thử
Xác định và mô tả test case
Xem xét test case và các bước kiểm thử
Xem xét và khảo sát độ bao phủ của việc kiểm thử Sai

Xem xét test case và các bước kiểm thử
Mô tả các bước chi tiết kiểm thử
Xác định và mô tả test case
Xem xét và khảo sát độ bao phủ của việc kiểm thử Sai

Đáp án đúng là: A

“Xác định và mô tả test case
Mô tả các bước chi tiết kiểm thử
Xem xét và khảo sát độ bao phủ của việc kiểm thử
Xem xét test case và các bước kiểm thử”.

Vì: Các bước thiết kế kiểm thử cơ bản là: ”Xác định và mô tả test case, mô tả các bước chi tiết kiểm thử, xem xét và khảo sát độ bao phủ của việc kiểm thử, xem xét test case và các bước kiểm thử”

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp

Câu 4: Một quy trình kiểm thử phần mềm thì có … test case?

Chọn một câu trả lời

A) Nhiều Đúng

B) Một Sai

C) Có thể không cần Sai

D) Phải luôn là hai Sai

Đáp án đúng là: A) “Nhiều”.Vì: Trong quy trình kiểm thử phần mềm có khâu thiết kế test. Trong khâu thiết kế test này nhằm chỉ định các test case và các bước kiểm tra chi tiết cho mỗi phiên bản phần mềm.

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp”

Câu 5: Phát biểu nào sau đây về test script là sai?

Chọn một câu trả lời

A) Một Test Script là một nhóm mã lệnh dạng đặc tả kịch bản dùng để tự động hóa một trình tự kiểm tra. Sai

B) Giúp cho việc kiểm tra nhanh hơn Sai

C) Cho những trường hợp mà kiểm tra bằng tay sẽ rất khó khăn hoặc không khả thi Sai

D) Test script là kiểm thử bằng tay Đúng

Đáp án đúng là: D) “Test script là kiểm thử bằng tay” Vì: Một Test Script là một nhóm mã lệnh dạng đặc tả kịch bản dùng để tự động hóa một trình tự kiểm tra, giúp cho việc kiểm tra nhanh hơn, hoặc cho những trường hợp mà kiểm tra bằng tay sẽ rất khó khăn hoặc không khả thi.

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp”

Câu 6: Trong các bước sau, đâu không phải là thành phần của test case?

Chọn một câu trả lời

A) Mô tả Sai

B) Nhập Sai

C) Kết quả mong chờ Sai

D) Xuất Đúng

Đáp án đúng là: D) “Xuất”. Vì: Các thành phần cơ bản của một test case là: mô tả, nhập và kết quả mong chờ

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp”

Câu 7: Lập kế hoạch kiểm thử để làm gì?

Chọn một câu trả lời

A) Để chỉ định và mô tả các loại kiểm thử sẽ được triển khai và thực hiện Đúng

B) Để lập kế hoạch cho test case Sai

C) Để lập kế hoạch cho test script Sai

D) Để lập kiểm định dự án phần mềm Sai

Đáp án đúng là: A) “Để chỉ định và mô tả các loại kiểm thử sẽ được triển khai và thực hiện”. Vì: Lập kế hoạch kiểm thử để nhằm mục đích chỉ định và mô tả các loại kiểm thử sẽ được triển khai và thực hiện

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp

The post Kiểm Thử Phần Mềm Là Gì ? Tại Sao Cần Kiểm Thử Phần Mềm first appeared on Techacademy.

source https://techacademy.edu.vn/kiem-thu-phan-mem-la-gi/

Kiểm Thử Phần Mềm Là Gì ? Tại Sao Cần Kiểm Thử Phần Mềm

I. Kiểm Thử Phần Mềm Là Gì

II. Tại Sao Cần Kiểm Thử Phần Mềm

III. Mục Đích Của Kiểm Thử Phần Mềm

Kiểm thử là 1 quá trình thực thi chương trình với mục đích là tìm ra lỗi/các yếu điểm của chương trình.
Một trường hợp kiểm thử tốt là 1 trường hợp có khả năng lớn trong việc tìm ra những lỗi chưa được phát hiện.
Một trường hợp kiểm thử không tốt ( không thành công) là một trường hợp mà khả năng tìm thấy những lỗi chưa biết tới là rất ít.

IV. Các Phương Pháp Kiểm Thử Phần Mềm

+ Kiểm thử hộp đen

Ưu điểm	Nhược điểm
Phù hợp và hiệu quả khi số lượng các dòng lệnh của hệ thống là lớn.	Bị giới hạn bởi độ bao phủ của các trường hợp kiểm thử
Không cần truy cập mã nguồn.	Kiểm thử không hiệu quả, do thực tế tester bị hạn chế kiến thức về hệ thống.
Phân biệt rõ ràng quan điểm của người dùng với quan điểm của nhà phát triển thông qua các vai trò được xác định rõ ràng.	Không có độ bao phủ, vì người kiểm thử không thể kiểm tra các đoạn mã nguồn hoặc tập trung vào các đoạn mã bị lỗi.
Một số lượng lớn tester có kỹ năng vừa phải có thể kiểm tra ứng dụng mà không cần có nhiều kiến thức, ngôn ngữ lập trình hoặc hệ điều hành.	Rất khó để thiết kế được đầy đủ các trường hợp kiểm thử cho hệ thống.

+ Kiểm thử hộp trắng

Ưu điểm	Nhược điểm
Khi tester có kiến thức về mã nguồn cũng như ngôn ngữ lập trình, sẽ trở nên rất dễ dàng để tìm ra loại dữ liệu nào có thể giúp kiểm thử phần mềm một cách hiệu quả.	Do thực tế, tester có tay nghề cao là cần thiết để thực hiện kiểm thử hộp trắng, chi phí được tăng lên.
Giúp tối ưu hóa source code trong hệ thống.	Đôi khi không thể khả thi khi kiểm tra chi tiết từng dòng source code để tìm ra các lỗi tiềm ẩn có thể gây ra vấn đề cho hệ thống, vì nhiều luồng sẽ không được kiểm tra.
Các dòng lệnh không cần thiết hoặc những dòng lệnh có khả năng gây ra các lỗi tiềm ẩn có thể được gỡ bỏ.	Rất khó để duy trì kiểm thử hộp trắng, vì nó đòi hỏi các công cụ chuyên biệt như phân tích source code và công cụ sửa lỗi.
Tester có kiến thức về ngôn ngữ lập trình sẽ dễ dàng để đạt được độ bao phủ cao nhất trong quá trình viết kịch bản kiểm thử.

+ Kiểm thử hộp xám

Kiểm thử hộp màu xám là một kỹ thuật để kiểm thử phần mềm đòi hỏi tester có kiến thức nhất định về các luồng hoạt động bên trong của phần mềm.

Ưu điểm	Nhược điểm
Là sự kết hợp của kiểm thử hộp đen và kiểm thử hộp trắng nên có được ưu điểm của cả hai phương pháp này.	Vì không dựa trên việc truy cập vào mã nguồn của hệ thống nên độ bao phủ của các trường hợp kiểm thử bị giới hạn.
Kiểm thử hộp xám không dựa vào mã nguồn; thay vào đó chúng dựa vào tài liệu thiết kế giao diện và các tài liệu đặc tả chức năng.	Các trường hợp kiểm thử có thể bị dư thừa nếu nhà thiết kế phần mềm đã chạy một số trường hợp kiểm thử.
Một tester kiểm thử hộp xám có thể thiết kế các kịch bản kiểm thử thông qua các giao thức kết nối và các kiểu dữ liệu khác nhau.	Kiểm thử mọi luồng đầu vào là không thể bởi vì nó sẽ mất một khoảng thời gian lớn; do đó, nhiều luồng hoạt động sẽ không được kiểm thử.
Việc kiểm thử được thực hiện từ quan điểm của người dùng chứ không phải người thiết kế.

V. Công Cụ Kiểm Thử Phần Mềm

+ Selenium

+ TestingWhiz

Ngoài ra, TestingWhiz cung cấp nhiều tính năng quan trọng khác nhau như:

Kiểm thử theo hướng từ khóa (key-word driven), theo hướng dữ liệu (data driven) và kiểm thử phân tán (distributed)
Kiểm thử tiện ích mở rộng trong trình duyệt
Object Eye Internal Recorder
SMTP Integration
Tích hợp với các công cụ theo dõi lỗi như Jira, Mantis, TFS và FogBugz
Tích hợp với các công cụ quản lý kiểm thử như HP Quality Center, Zephyr, TestRail và Microsoft VSTS
Centralized Object Repository (Kho lưu trữ đối tượng tập trung)
Version Control System Integration (Tích hợp hệ thống kiểm soát phiên bản)
Customized Recording Rule (Quy tắc ghi tùy chỉnh)

+ HPE Unified Functional Testing (HP – UFT formerly QTP)

Ngoài ra, QTP cung cấp các tính năng khác như:

Tích hợp với Mercury Business Process Testing và Mercury Quality Center
Nhận dạng Unique Smart Object
Cơ chế xử lý lỗi
Tạo các tham số cho đối tượng, checkpoint và bảng điều hướng dữ liệu
Tài liệu tự động

+ TestComplete

TestComplete cung cấp các tính năng sau:
GUI testing
Hỗ trợ ngôn ngữ test – JavaScript, Python, VBScript, JScript, DelphiScript, C++ Script & C# Script
Kiểm thử trình hiển thị
Kiểm thử theo script (Scripted testing)
Kiểm thử ghi và phát lại (Test recording and playback)

+ Ranorex

Ranorex Studio cung cấp các công cụ tự động hóa testing khác nhau bao gồm việc test tất cả các ứng dụng máy tính để bàn, web và thiết bị di động.

Cụ thể hơn, Ranorex cung cấp các tính năng sau:

Kiểm thử GUI
Có thể tái sử dụng test code
Phát hiện bug
Tích hợp với nhiều công cụ khác nhau
Ghi và phát lại

+ Sahi

Sahi cung cấp các tính năng sau:

Thực hiện kiểm thử nhiều trình duyệt cùng lúc
Hỗ trợ các framework ExtJS, ZK, Dojo, YUI, v.v.
Ghi lại và phát lại khi test trình duyệt

+ Watir

Watir là một công cụ kiểm thử mã nguồn mở được tạo thành từ các thư viện Ruby để tự động kiểm thử ứng dụng web.

Công cụ này cung cấp các tính năng sau:

Kiểm thử bất kỳ ứng dụng web dựa trên ngôn ngữ nào
Kiểm thử trên nhiều trình duyệt
Tương thích với các công cụ phát triển theo định hướng kinh doanh như RSpec, Cucumber và Test / Unit
Kiểm thử các nút, biểu mẫu, liên kết và phản hồi của chúng trên trang web

+ Tosca Testsuite

Tosca Testsuite đi kèm với các tính năng sau:

Lập kế hoạch và thiết kế trường hợp thử nghiệm
Kiểm tra cung cấp dữ liệu
Dịch vụ mạng ảo hóa
Kiểm tra ứng dụng di động
Quản lý tích hợp
Bảo hiểm rủi ro

+ Telerik TestStudio

Công cụ này cung cấp nhiều khả năng tương thích khác nhau như:

Hỗ trợ các ngôn ngữ lập trình như HTML, AJAX, ASP.NET, JavaScript, Silverlight, WPF và MVC
Tích hợp với Visual Basic Studio 2010 và 2012
Ghi và phát lại
Kiểm thử trên nhiều trình duyệt
Kiểm thử thủ công
Tích hợp với các công cụ theo dõi bug

+ Katalon Studio

Katalon Studio bao gồm các tính năng sau:

Kho lưu trữ đối tượng tích hợp, XPath, nhận dạng lại đối tượng
Hỗ trợ các ngôn ngữ script Java / Groovy
Hỗ trợ tích hợp cho kiểm thử dựa trên hình ảnh
Hỗ trợ các công cụ Tích hợp liên tục như Jenkins & TeamCity
Hỗ trợ Duel-editor Interface
Quy trình thực thi có thể tùy chỉnh

VI. Trắc Nghiệm Kiểm Thử Phần Mềm Có Đáp Án

Câu 1: Mô hình kiểm thử phần mềm TMM là viết tắt của từ tiếng anh nào sau đây?

Chọn một câu trả lời

A) Testing Maturity Model Đúng

B) Testing Model Manufactory Sai

C) Testing Manufactory Model Sai

D) Testing Manual Machanic Sai

Đáp án đúng là: A) “Testing Maturity Model”.Vì: Mô hình kiểm thử phần mềm TMM là viết tắt của từ tiếng Anh: “Testing Maturity Model”.

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp.

Câu 2: Phát biểu nào sau đây là sai về thiết kế kiểm thử?

Chọn một câu trả lời

A) Thực thi sau khi có bản kế hoạch kiểm thử Sai

B) Chỉ định các test case cũng như các bước kiểm thử Sai

C) Có thể dùng cho mọi phiên bản phần mềm Đúng

D) Bảo đảm tất cả các tình huống kiểm thử được quét hết Sai

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp.

Câu 3: Đâu là thứ tự thực hiện các bước kiểm thử cơ bản?

Chọn một câu trả lời

Xác định và mô tả test case
Mô tả các bước chi tiết kiểm thử
Xem xét và khảo sát độ bao phủ của việc kiểm thử
Xem xét test case và các bước kiểm thử Đúng

Xác định và mô tả test case
Mô tả các bước chi tiết kiểm thử
Xem xét test case và các bước kiểm thử
Xem xét và khảo sát độ bao phủ của việc kiểm thử Sai

Mô tả các bước chi tiết kiểm thử
Xác định và mô tả test case
Xem xét test case và các bước kiểm thử
Xem xét và khảo sát độ bao phủ của việc kiểm thử Sai

Xem xét test case và các bước kiểm thử
Mô tả các bước chi tiết kiểm thử
Xác định và mô tả test case
Xem xét và khảo sát độ bao phủ của việc kiểm thử Sai

Đáp án đúng là: A

“Xác định và mô tả test case
Mô tả các bước chi tiết kiểm thử
Xem xét và khảo sát độ bao phủ của việc kiểm thử
Xem xét test case và các bước kiểm thử”.

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp

Câu 4: Một quy trình kiểm thử phần mềm thì có … test case?

Chọn một câu trả lời

A) Nhiều Đúng

B) Một Sai

C) Có thể không cần Sai

D) Phải luôn là hai Sai

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp”

Câu 5: Phát biểu nào sau đây về test script là sai?

Chọn một câu trả lời

A) Một Test Script là một nhóm mã lệnh dạng đặc tả kịch bản dùng để tự động hóa một trình tự kiểm tra. Sai

B) Giúp cho việc kiểm tra nhanh hơn Sai

C) Cho những trường hợp mà kiểm tra bằng tay sẽ rất khó khăn hoặc không khả thi Sai

D) Test script là kiểm thử bằng tay Đúng

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp”

Câu 6: Trong các bước sau, đâu không phải là thành phần của test case?

Chọn một câu trả lời

A) Mô tả Sai

B) Nhập Sai

C) Kết quả mong chờ Sai

D) Xuất Đúng

Đáp án đúng là: D) “Xuất”. Vì: Các thành phần cơ bản của một test case là: mô tả, nhập và kết quả mong chờ

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp”

Câu 7: Lập kế hoạch kiểm thử để làm gì?

Chọn một câu trả lời

A) Để chỉ định và mô tả các loại kiểm thử sẽ được triển khai và thực hiện Đúng

B) Để lập kế hoạch cho test case Sai

C) Để lập kế hoạch cho test script Sai

D) Để lập kiểm định dự án phần mềm Sai

Tham khảo: giáo trình “Kiểm thử và bảo đảm chất lượng phần mềm”, chương 7, mục “Kiểm thử phần mềm trong công nghiệp

The post Kiểm Thử Phần Mềm Là Gì ? Tại Sao Cần Kiểm Thử Phần Mềm first appeared on Techacademy.

source https://techacademy.edu.vn/kiem-thu-phan-mem-la-gi-tai-sao-can-kiem-thu-phan-mem/

Học Tester Mất Bao Lâu?

Học tester là 1 cách rất hay nếu như bạn đang làm hay đang học ở lĩnh vực khác mà muốn lấn sân sang công nghệ thông tin. Nhưng không phải ai cũng biết điều này hay biết làm thế nào để việc này trở nên thuận lợi. Học tester mất bao lâu là câu hỏi mà bạn nào có ý định đi theo nghề Software Tester đều thắc mắc. Vậy hãy cùng tìm câu trả lời nhé!

I. Học Tester Mất Bao Lâu?

Kiến thức căn bản: Giai đoạn này sẽ mất 3-6 tháng hoặc hơn thế nữa tùy vào khả năng tiếp thu kiến thức của bạn. Bạn sẽ được học tri thức căn bản về máy tính, về tin học văn phòng, cài đặt phần mềm, sử dụng internet. Sau đó là kiến thức về lập trình: SQL, HTML, CSS và kiến thức tổng quan về test bao gồm việc hiểu định nghĩa cơ bản, những thuật ngữ, quy trình phần mềm, quy trình test…

Phần kiến thức riêng: Giai đoạn này sẽ ngắn hơn mất khoảng 2-3 tháng.

– Manual Test:

Đây là danh sách những kiến thức bạn nên tìm hiểu sâu thêm nếu sẽ làm test theo hướng manual.

Create a Test Plan: Các thành phần cần có trong một test plan cơ bản, cách viết test plan.

Design Test case: Cách tạo và viết 1 testcase thông dụng.

Test Design Techniques: Các kỹ thuật thiết kế testcase, giúp cho testcase hiệu quả và tối ưu hơn.

Test reporting, Daily status reports – cách viết report để báo cáo kết quả test của mình.

Defect management: Finding defects, Logging defects, Tracking and managing defects – Học cách report & quản lý một bug cũng như sử dụng tools tracking thông dụng như Jira, Mantis, Bugzilla, Application Lifecycle Management (ALM).

Mobile application testing (iOS, Android, Windows Phone): Cách cài đặt và test ứng dụng mobile, cách giả lập thiết bị điện thoại trên máy tính.

Windows, Website testing & Tools support: Cách test 1 ứng dụng desktop, một trang web và giả lập các trình duyệt khác nhau trên máy tính.

Risk based testing process and implementation: Đánh giá rủi ro trong kiểm thử, đây là phần nâng cao nhưng cũng nên tìm hiểu qua.

Coding: SQL, HTML, CSS.

– Automation Test:

Học thêm về lập trình: Java, C# (.Net) là hai ngôn ngữ căn bản mà những người làm automation hay sử dụng, ngoài ra có các ngôn ngữ khác dùng để hỗ trợ như AutoIT, Python.

Học về các Automation Tool/Framework phổ biến như: Ranorex, Selenium, Appium, TestComplete.

Các Tools khác như: Jmeter, SoapUI.

II. Học Tester Như Thế Nào Để Trở Thành Kiểm Thử Viên Giỏi?

Bài viết này chia sẻ với những bạn sinh viên có dự định học Tester và đi làm trong tương lai, hy vọng sẽ cung cấp thêm thông tin giúp các bạn dễ dàng có được định hướng cho con đường của mình

+ Học Tester sau sẽ làm những công việc gì?

Nhìn chung công việc chính của tester là đảm bảo chất lượng của phần mềm, kiểm tra để phát hiện các lỗi đang tồn tại trước lúc giao sản phẩn cho khách hàng, tùy thuộc vào dự án cũng như công ty mà vai trò của tester tham gia sâu đến mức nào. Tester thường chia ra làm 2 hướng chính là Manual test và Automation test.

Manual testing: đây là lựa chọn của đa số các bạn bắt đầu làm test, với lựa chọn này bạn không cần nhiều kiến thức về lập trình cũng như sẽ ít đụng vào code trong lúc làm, tuy nhiên cần phải nắm khá vững về các định nghĩa, kỹ thuật test manual và có tư duy tìm lỗi tốt.
Automation testing: đây thường là lựa chọn của các bạn đang làm Developer mà muốn chuyển sang làm Tester, hoặc các bạn làm manual lâu năm muốn học hỏi thêm cái gì đó mới mẻ và nâng cao trình độ của mình. Automation test có thể nói là Dev trong Test, công việc chính là sẽ viết code để thực hiện việc kiểm tra một cách tự động và phần lớn thời gian sẽ làm việc với code như một developer.
Người làm automation sẽ không cần thiết phải nắm sâu về các kiến thức test manual nhưng thay vào đó phải biết rõ về các automation tools & frameworks cũng như có thể làm việc được trên nhiều ngôn ngữ lập trình khác nhau như Java, C#, AutoIT, Python, C++ v.v, tùy theo yêu cầu dự án.

Automation không phải là nâng cao của manual vì nó là hai nhánh khác nhau, cả hai đều quan trọng cũng như có độ khó nhất định nếu phải học và tìm hiểu sâu. Người làm manual tốt không chắc có thể viết code được và người làm automation cũng chưa chắc sẽ có được tư duy, khả năng quan sát & kiến thức kiểm thử manual nên bạn cứ chọn một hướng phù hợp với khả năng và bắt đầu học, không nên tìm hiểu cùng lúc cả hai trong giai đoạn mới vào sẽ tốn rất nhiều thời gian.

+ Tester cần những kiến thức gì?

– Đầu tiên, tester cũng giống như bất cứ ngành nào khác trong lĩnh vực phần mềm là cần 1 nền tảng căn bản về máy tính. Kiến thức căn bản này bạn có thể học được trong chương trình cao đẳng, đại học. Hiện nay giáo trình đào tạo cao đẳng, đại học về công nghệ thông tin của các trường cũng khá đầy đủ, bao quát nhiều kiến thức như hệ điều hành, database, lập trình, mạng….

Những kiến thức này tuy có vẻ không ứng dụng được gì trong lúc học nhưng sẽ rất hữu ích cho việc học test và đi làm sau này, nếu bạn tập trung học trong giai đoạn sinh viên thì sau khi ra trường việc học thêm một khóa về kiểm thử là khá nhanh và đơn giản hơn nhiều.

– Nếu bạn học ngành khác nhưng muốn chuyển sang làm test (chưa học gì nhiều về công nghệ thông tin trong trường) thì sẽ khó khăn và tốn nhiều thời gian hơn vì bạn phải học lại căn bản, cũng như sẽ bị sót nhiều kiến thức nếu chỉ đăng ký một khóa học test ngắn hạn.

Nhưng nói vậy không có nghĩa là không thể, cũng có nhiều bạn đang làm test và khá thành công nhưng xuất phát từ các ngành khác như sư phạm, kinh tế. Nếu bạn cũng đang học trái ngành thì có 2 bước cần thực hiện đó là dành thời gian học cách sử dụng tốt máy tính, tin học văn phòng, đọc thêm các sách căn bản về máy tính, lập trình (có thể mượn từ các bạn đang học CNTT).

Giai đoạn này sẽ tốn khoảng 3 tới 6 tháng (hoặc hơn), tuy hơi dài nhưng sẽ rất có giá trị. Tiếp theo bạn cần học thêm về các kiến thức chuyên ngành testing, giai đoạn này sẽ ngắn hơn, thường là khoảng 2 đến 3 tháng, chi tiết học gì tôi sẽ nói ở phần sau.

– Tiếng Anh, cái này không liên quan test nhưng rất quan trọng, tiếng Anh tốt bạn có nhiều cơ hội để đậu vào các công ty hơn cũng như dễ dàng học thêm về test sau này vì tài liệu đa số là tiếng Anh.

Vậy tóm tắt lại, có 3 kiến thức tester cần trang bị là Nền tảng về máy tính + Kiến thức Test căn bản + Tiếng Anh

+ Học gì để trở thành tester?

*Kiến thức chung: (dù bạn chọn theo hướng nào thì cũng nên nắm các kiến thức này).

– Kiến thức căn bản về máy tính, tin học văn phòng căn bản, cài đặt phần mềm, sử dụng internet.

– Kiến thức về lập trình: Căn bản SQL, HTML, CSS. Đây là 3 món tôi nghĩ rất cần thiết khi làm test, bạn không cần phải học sâu để viết code nhưng ít ra phải đọc hiểu được và có thể chỉnh sửa code đơn giản.

– Kiến thức tổng quan về test, bao gồm việc hiểu các định nghĩa cơ bản, các thuật ngữ, quy trình phát triển phần mềm, quy trình test. Bạn có thể học theo cuốn ISTQB Foundation hoặc tham khảo các mục gợi ý sau:

What is Software Testing? – Tìm hiểu phần này để biết được testing là gì? các định nghĩa, khái niệm căn bản về kiểm thử phần mềm.
Why is Software Testing Important? – Tại sao testing lại quan trọng và cần thiết? nếu không có tester thì sản phẩm sẽ ra sao?
Software Development life cycle: Vòng đời phát triển phần mềm, vị trí của testing trong các giai đoạn phát triển sản phẩm.
Software Test life cycle: Vòng đời của kiểm thử, thứ tự các công việc kiểm thử.
Defect Life Cycle: Vòng đởi của lỗi và trạng thái qua các giai đoạn.
Quality Assurance vs. Quality control, Verification vs Validation: Phân biêt sự giống nhau và khác nhau giữa một số khái niệm.
Software Testing Levels: Các mức độ trong kiểm thử, đi từ nhỏ nhất đến các mức độ cao nhất.
Software Testing types: Các loại testing thư Functional testing, Non-functional testing, Structural testing, Change related testing.

*Phần kiến thức riêng:

Manual Test:

Đây là danh sách các kiến thức bạn nên tìm hiểu sâu thêm nếu sẽ làm test theo hướng manual:

Create a Test Plan: Các thành phần cần có trong một test plan cơ bản, cách viết test plan.
Design Test case: Cách tạo và viết một testcase thông dụng.
Test Design Techniques: Các kỹ thuật thiết kế testcase, giúp cho testcase hiệu quả và tối ưu hơn.
Test reporting, Daily status reports – cách viết report để báo cáo kết quả test của mình.
Defect management: Finding defects, Logging defects, Tracking and managing defects – Học cách report & quản lý một bug cũng như sử dụng tools tracking thông dụng như Jira, Mantis, Bugzilla, Application Lifecycle Management (ALM).
Mobile application testing (iOS, Android, Windows Phone): Cách cài đặt và test ứng dụng mobile, cách giả lập thiết bị điện thoại trên máy tính.
Windows, Website testing & Tools support: Cách test một ứng dụng desktop, một trang web và giả lập các trình duyệt khác nhau trên máy tính.
Risk based testing process and implementation: Đánh giá rủi ro trong kiểm thử, đây là phần nâng cao nhưng cũng nên tìm hiểu qua.
Coding: SQL, HTML, CSS.

Một số trang để tự học các kiến thức về manual testing căn bản, các trang này cung cấp đầy đủ các kiến thức bên trên cũng như mở rộng thêm khá nhiều kiến thức liên quan đến test khác:

Software Testing Tutorial – Guru99
Software Testing Tutorial – Tutorials Point
Software Testing Class
Software Testing Help
W3Schools (HTML, CSS)
SQL Tutorial – W3Schools
SQL Tutorial – TutorialsPoint

Automation Test:

Học về các Automation Tool/Framework phổ biến như: Ranorex, Selenium, Appium, TestComplete.
Các Tools khác như: Jmeter, SoapUI.

Các địa chỉ học về Automation & Lập trình:

Selenium User Guide
Selenium Tutorials – Guru99
Selenium Training Tutorials – Software Testing Help
Ranorex User Guide
Jmeter
SoapUI
Java2S
Python tutorial – TutorialsPoint
C# Tutorial – TutorialsPoint

Nếu chưa biết nên bắt đầu từ đâu bạn có thể bắt đầu với bộ tools Selenium (thường dùng Java) hoặc Ranorex (C# hoặc .Net nói chung). Với Selenium (miễn phí) bạn có thể làm được automation cho website còn Ranorex thì có thể làm được trên website, mobile application và desktop application nhưng có tốn phí khá cao.

+ Học test ở đâu?

Có ba cách cơ bản để học test là tự học, học ở trung tâm và học nhóm. Đa số các tester thuộc thế hệ 8x hay 9x đời đầu đều tự học mà làm vì giai đoạn đó testing chưa phát triển và cũng chưa có trung tâm chuyên đào tạo, các trường đại học cũng chưa đưa vào chương trình dạy. Đa số tester ở giai đoạn này thường xuất thân từ CNTT nên việc tự học và học thêm về test cũng khá nhanh. Để tự học test bạn có thể vào các nguồn tôi cung cấp ở phần bên trên, nó khá đầy đủ kiến thức căn bản.

Thứ hai là có thể đi học ở trung tâm hay một nhóm nào đó, các trung tâm thường có các khóa đào tạo ngắn hạn trong khoảng 3 tháng đỗ lại, một số trung tâm thì có chương trình dài hơn nhưng thường không quá 6 tháng. Stanford là trung tâm đào tạo bài bản và chất lượng về kiểm thử phần mềm bạn sẽ được thực hành qua dự án thực tế để có thể đi làm ngay sau khóa học.

Ngoài ra còn một cách học khác là học nhóm, dạy kèm test, phương pháp này khá hiệu quả vì nó vừa linh động về thời gian và số lượng học viên thường giới hạn ít nên sẽ dễ tiếp thu hơn, thời gian học khoảng 1 đến 2 tháng.

Học Tester Như Thế Nào Để Trở Thành Kiểm Thử Viên Giỏi?

III. Học Gì Để Trở Thành Một Tester?

Trong lĩnh vực phần mềm Tester hay còn gọi là Engineer là nghề kiểm tra chất lượng phần mềm. Tester sẽ là người kiểm tra những sản phẩm (phần mềm hay ứng dụng) mà các lập trình viên đã làm ra. Vậy học gì để trở thành tester?

+ Kiến thức chung

Kiến thức căn bản về máy tính, tin học văn phòng căn bản, cài đặt phần mềm, dùng internet.
Kiến thức về lập trình: Căn bản SQL, HTML, CSS. Đây là 3 món tôi nghĩ rất cần thiết lúc làm test, bạn không cần phải học sâu để viết code nhưng ít ra phải đọc hiểu được và có thể chỉnh sửa code đơn giản.
Kiến thức tổng quan về test, bao gồm việc hiểu những định nghĩa cơ bản, các thuật ngữ, quy trình phát triển phần mềm, quy trình test. Bạn có thể học theo cuốn ISTQB Foundation hoặc tham khảo các mục gợi ý sau:
What is Software Testing? – Tìm hiểu phần này để biết được testing là gì? các định nghĩa, khái niệm căn bản về kiểm thử phần mềm.
Why is Software Testing Important? – Tại sao testing lại quan trọng và cần thiết? giả dụ không có tester thì sản phẩm sẽ ra sao?
Software Development life cycle: Vòng đời phát triển phần mềm, vị trí của testing trong các giai đoạn phát triển sản phẩm.
Software Test life cycle: Vòng đời của kiểm thử, thứ tự các công việc kiểm thử.
Defect Life Cycle: Vòng đởi của lỗi và trạng thái qua các giai đoạn.
Quality Assurance vs. Quality control, Verification vs Validation: Phân biêt sự giống nhau và khác nhau giữa một số khái niệm.
Software Testing Levels: Các mức độ trong kiểm thử, đi từ nhỏ nhất tới các mức độ cao nhất.
Software Testing types: Các loại testing thư Functional testing, Non-functional testing, Structural testing, Change related testing.

+ Phần kiến thức bổ sung

Manual Test:

Đây là danh sách các kiến thức bạn nên tìm hiểu sâu thêm nếu sẽ làm test theo hướng manual.

Create a Test Plan: Các thành phần cần có trong một test plan cơ bản, cách viết test plan.
Design Test case: Cách tạo và viết một testcase thông dụng.
Test Design Techniques: Các kỹ thuật thiết kế testcase, giúp cho testcase hiệu quả và tối ưu hơn.
Test reporting, Daily status reports – cách viết report để báo cáo kết quả test của mình.
Defect management: Finding defects, Logging defects, Tracking and managing defects – Học cách report & quản lý một bug cũng như sử dụng tools tracking thông dụng như Jira, Mantis, Bugzilla, Application Lifecycle Management (ALM).
Mobile application testing (iOS, Android, Windows Phone): Cách cài đặt và test ứng dụng mobile, cách giả lập thiết bị điện thoại trên máy tính.
Windows, Website testing & Tools support: Cách test một ứng dụng desktop, một trang web và giả lập các trình duyệt khác nhau trên máy tính.
Risk based testing process and implementation: Đánh giá rủi ro trong kiểm thử, đây là phần nâng cao nhưng cũng nên tìm hiểu qua.
Coding: SQL, HTML, CSS.

Automation Test:

Học thêm về lập trình: Java, C# (.Net) là hai ngôn ngữ căn bản mà những người làm automation hay sử dụng, ngoài ra có các ngôn ngữ khác dùng để hỗ trợ như AutoIT, Python.
Học về các Automation Tool/Framework phổ biến như: Ranorex, Selenium, Appium, TestComplete.
Các Tools khác như: Jmeter, SoapUI.

IV. Chi Phí Học Tester Bao Nhiêu Tiền, Có Đắt Không?

Hiện nay, do nhu cầu của các bạn trẻ khá nhiều nên rất nhiều trung tâm đào tạo Tester đã được mở ra với nhiều mức chi phí khác nhau. Chính điều này đã khiến cho mọi người hoang mang không biết chi phí học Tester bao nhiêu tiền?

Theo như tìm hiểu của chúng tôi thì chi phí học Tester hiện nay không cố định, tại một trung tâm lại có mức chi phí khác nhau. Cụ thể mức chi phí học hiện nay thường dao động từ hơn 3 triệu – 7 triệu đồng.

Bên cạnh đó, có rất nhiều địa chỉ không uy tín mở ra những khóa học rẻ tiền để lôi kéo học viên nhưng khi học viên tham gia khóa học thì sẽ không được giảng dạy chu đáo. Bởi vậy, khi lựa chọn khóa học thì các bạn nên đến các địa chỉ uy tín để tránh mất tiền oan nhé.

Techacademy – Trung tâm đào tạo Tester hàng đầu với chi phí phải chăng

Là một trong số các trung tâm đào tạo Tester hàng đầu hiện nay Techacademy đang trở thành sự lựa chọn của rất nhiều học viên.

Hiện tại, khóa học Tester tại Techacademy gồm có lộ trình học đầy đủ và học trong vòng 1 tới 1,5 tháng với mức học phí là khoảng 3 triệu đồng.

Khi đến với Techacademy bạn sẽ được:

– Trang bị đầy đủ kiến thức với lộ trình phù hợp

Các khóa học tester mà Techacademy xây dựng từ các khóa học tester cho người mới bắt đầu tới những kiến thức chuyên sâu để giúp bạn nắm được kiến thức và thực hành thành thạo trong thời gian nhanh nhất.

Đặc biệt, Techacademy còn rèn luyện cho học viên các kỹ năng kiểm thử thông qua các tình huống thực tế. Điều này sẽ giúp các học viên có thể thích nghi nhanh với công việc này khi làm việc tại các doanh nghiệp.

– Kiến thức được chia sẻ kinh nghiệm từ giảng viên lâu năm

Các giảng viên của Techacademy đều là các chuyên gia Tester. Với phương pháp giáo dục tiên tiến và không ngừng sáng tạo, các giảng viên sẽ mang đến môi trường học với nhiều kiến thức bổ ích lý thú. Điều này giúp các học viên cảm thấy tiết học luôn cuốn hút để tiếp thu đầy đủ kiến thức.

Không chỉ vậy, các giảng viên còn chia sẻ những kinh nghiệm thực tế tại từ các dự án thực tế để giúp các học viên có thêm những kỹ năng mềm cho quá trình làm việc tại các doanh nghiệp.

– Cấp chứng chỉ cho học viên sau lúc hoàn thành khóa học tester.

Sau khi kết thúc khóa học, trung tâm sẽ cấp chứng chỉ cho các học viên. Đồng thời, trung tâm còn hỗ trợ giới thiệu thông tin việc làm cho các học viên có thành tích xuất sắc ngay sau khóa học với các doanh nghiệp liên kết với trung tâm.

Chi Phí Học Tester Bao Nhiêu Tiền, Có Đắt Không?

The post Học Tester Mất Bao Lâu? first appeared on Techacademy.

source https://techacademy.edu.vn/hoc-tester-mat-bao-lau/

Học Tester Cho Người Trái Ngành

Công nghệ thông tin trong những năm gần đây liên tục phát triển. Thị trường nhân lực của ngành này cũng vì thế mà rầm rộ và nhộn nhịp hơn cả. Nhắc tới công nghệ thông tin là người ta nghĩ đầu tiên đến lập trình viên (Developer), quản trị, an ninh mạng, thiết kế phần mềm, quản lý hệ thống, kĩ sư cầu nối… Đó là những vị trí quen thuộc, phổ biến. Ở bài viết hôm nay, mình xin chia sẻ cụ thể Tester là gì, những điều cần thiết để trở thành 1 Tester, học tester cho người trái ngành.

I. Tester Là Làm Gì? Học Trái Ngành Có Làm Được Tester

Nhắc tới ngành CNTT thông thường các bạn chỉ nghĩ đến nhân viên lập trình, quản trị, bảo trì mạng chứ nhiều người không biết đến tester hay nhân viên kiểm thử. Tuy nhiên trong những năm gần đây thì tester lại là từ khóa được tìm kiếm phổ biến vậy tester là làm gì. Vì sao tester lại là một ngành hot như vậy trong những năm gần đây.

– Tester là làm gì

Tester là người kiểm thử phần mềm người thực hiện bới lông tìm vết để tìm kiếm các lỗi, sai sót, hay bất cứ vấn đề nào mà có thể tác động tới chất lượng phần mềm trước lúc bàn giao phần mềm đến tay khách hàng.

+ Các hướng đi của nghề kiểm thử:

Thông thường ngành tester sẽ có 2 con đường để bạn lựa chọn đó là Manual testing và Automation testing.

Manual testing: Đối với các bạn sinh viên mới ra trường hoặc mới chuyển sang ngành kiểm thử thủ công sẽ là sự lựa chọn đầu tiên, bạn sẽ tự động vào code khi làm, nhưng bạn phải nắm vững các khái niệm, kỹ thuật test manual và có tư duy tìm lỗi tốt.
Automation testing: Kiểm thử tự động là một kỹ thuật tự động hóa, trong đó người kiểm sử dụng các công cụ, script và phần mềm kiểm thử tự viết các tập code và sử dụng phần mềm phù hợp để kiểm thử phần mềm. Automation testing không cần nắm sâu kiến thức test manual nhưng thay vào đó họ phải biết rõ về các automation tools & frameworks cũng như có thể làm việc được trên nhiều ngôn ngữ lập trình khác nhau như Java, C#, AutoIT, Python, C++ v.v, tùy theo yêu cầu dự án.

+ Công việc của tester là gì?

Công việc của tester đó là tham gia quá trình kiểm thử các dự án phần mềm.
Tìm kiếm các lỗi của hệ thống phần mềm hoặc dựa vào những yêu cầu nghiệp vụ, kỹ thuật, mục đích sử dụng của phần mềm được đưa ra trong dự án nhân viên kiểm thử trực tiếp thẩm định, xác minh xem thử hệ thống phần mềm này có đáp ứng các yêu cầu kỹ thuật của dự án chưa.
Thiết kế và thực hiện test plan, test case, test report, tạo dữ liệu kiểm thử, thiết lập môi trường kiểm thử.
Thực hiện kiểm thử theo tính năng, hiệu năng của sản phẩm.
Tạo lỗi, kiểm soát lỗi, phối hợp với các developer để sửa lỗi, theo dõi kết quả kiểm thử để đảm bảo chất lượng dự án.
Tổng hợp các vấn đề phát sinh trong quá trình thực hiện dự án và đưa ra các đề xuất cải tiến.

+ Quy trình kiểm thử:

Nhận yêu cầu của khách hàng và phân tích yêu cầu
Lập kế hoạch kiểm thử, viết script cho trường hợp kiểm thử
Thực thi script
Debug lỗi
Báo cáo lỗi, Báo cáo kết quả kiểm thử
Báo cáo kết quả chạy Automation Test.

Tester Là Làm Gì? Học Trái Ngành Có Làm Được Tester

II. Trái Ngành Học Tester Có Khó Không

Trái nghành học tester có khó không là phân vân của không ít bạn khi muốn theo đuổi ngành này với hi vọng về một mức lương cao hơn so với mặt bằng chung các ngành khác mà không cần kiến thức quá chuyên sâu về lập trình. Vậy trái ngành học tester có thực sự dễ hoặc khó khăn như nhiều người vẫn nghĩ hay không?

+ Rất dễ để có thể theo đuổi nghề tester

Nếu bạn có một trình độ ngoại ngữ thành thạo, đặc biệt là kĩ năng đọc hiểu để có thể hiểu được yêu cầu và Test case thì bạn sẽ có thể trở thành một tester ( ví dụ như nếu bạn đang làm việc cho 1 công ty bắt buộc về trình độ tiếng anh thì trình độ đọc hiểu tiếng Anh của bạn phải tốt ).

Nội dung công việc của bạn sẽ bao gồm những gì? Công việc của bạn là đọc Test case và thực hành theo các đề nghị trong đó, công việc của bạn có vẻ sẽ không mấy thú vị. Nhiều bạn sau lúc hoàn thành khóa học Fresher Tester tại những trung tâm, rồi bắt đầu đi làm tại các công ty, họ than thở rằng: “Làm tester chán quá, với những dự án bảo trì hệ thống, ngày nào cũng làm đi làm lại chỉ có bấy nhiêu case. Khi thì test chỗ này, lúc lại test chỗ kia“.

+ Làm tester cũng không hề dễ

Khi mới bắt đầu đi làm, nhiều bạn nói rằng họ cảm thấy công việc quá khó khăn, họ không hiểu được nhóm dev nói gì, hay những nội dung về code mà các Dev nói ra họ không tài nào hiểu được. Với những trường hợp này thì công việc của tester không hề dễ chút nào.

Tuy nhiên bạn cũng không nên quá sợ hay e ngại mà bỏ qua cơ hội để học ngành Tester này, rất nhiều bạn sợ khó không biết có nên làm Tester hay không để rồi mãi vẫn chưa thể bắt đầu sẽ là rất đáng tiếc vì đây là một công việc rất tốt và nhiều cơ hội ở thời điểm hiện tại

+ Rốt cuộc làm nghề tester khó hay dễ?

Có thể nói làm nghề tester dễ là bởi vì bạn muốn test thì test, dù là test kĩ hay không, test nhiều hay ít thì bạn đều có thể thể làm được hết. Nếu đối với một người làm Dev, họ phải làm cho đến khi hoàn thành và ra mắt sản phẩm, chứ không thể nói là họ đã code xong trong khi chưa cho ra một sản phẩm hoàn chỉnh nào. Thì với mội Tester, bạn có thể nói bạn đã test xong.

Trong điều thứ 2 của nguyên tắc kiểm thử ISTQB nói rằng: Việc kiểm thử hết tất cả các kết hợp của giá trị đầu vào của một hệ thống là điều không thể. Vì vậy, khi test, bạn sẽ phải thực hiện dựa trên độ ưu tiên và rủi ro để có thể thực hiện test một cách hiệu quả.

Chính vì bạn không thể kiểm thử hết tất cả các trường hợp nên bạn phải biết mình cần test gì và không cần test gì. Để làm được như vậy thì bạn cần hiểu được đối tượng mà bạn đang test được làm ra như thế nào, hay nói cách khác bạn phải hiểu về sản phẩm. Chỉ khi bạn hiểu rõ về uqá trình vá cách làm ra sản phẩm thì bạn mới nhận ra được những rủi ro và thấy được khi nào thì sản phẩm đó không hoạt động được.

Và để làm được như thế, yếu cầu dành cho bạn là phải có một chút kiến thức về lập trình, về quá trình phát triển của phần mềm và nhiều kiến thức liên quan đến công nghệ thông tin khác.

Nói chung là, làm tester có khó không? việc dễ hay khó nó còn tuỳ thuộc vào thể loại sản phẩm, vào dự án, và kiến thức của người đang làm công việc test đó. Công việc tester thể dễ với người này, nhưng lại khó với người kia. Có thể nhàm chán với người này nhưng lại thú vị với người khác. Dù khó hay dễ thì Tester vẫn là một nghề rất HOT ở thời điểm hiện tại với mức thu nhập không hề thấp và được xem là nhẹ nhàng so với các công việc khác trong lĩnh vực công nghệ thông tin

III. Học Tester Cho Người Trái Ngành Bắt Đầu Từ Đâu

Tương tự với những người trái ngành học phần mềm tester thì các tester cần phải có là một nền tảng tốt về máy tính. Vậy học tester cho người trái ngành bắt đầu từ đâu? Đầu tiên là các bạn phải nắm được các kiến thức chung về phần mềm và máy tính. Ngoài ra bạn cũng cần bổ sung những kiến thức chuyên sâu để có thể đáp ứng được nhu cầu công việc khi đi làm thực tế.

+ Kiến thức chung

Về cơ bản, bạn cần phải nắm những kiến thức chung sau để có thể nghiên cứu chuyên sâu ngành nghề này:

Kiến thức căn bản về máy tính
Kiến thức tin học văn phòng căn bản
Biết cài đặt phần mềm, sử dụng internet thành thạo
Kiến thức về lập trình căn bản là SQL, HTML, CSS
Kỹ năng, kiến thức tổng quan về test: hiểu những định nghĩa, các thuật ngữ, quy trình phát triển phần mềm, quy trình test,…

+ Kiến thức chuyên sâu

Nếu bạn đi theo hướng Manual hoặc muốn phát triển hơn thì bắt buộc học thêm những kiến thức sau:

Create a Test Plan: phương pháp viết test plan
Design Test case: cách viết testcase thông dụng
Test Design Techniques: kỹ thuật thiết kế test case
Test reporting, Daily status report: cách viết báo cáo test case
Defect management: Finding defects, Logging defects, Tracking and managing defects – Report & quản lý bug, sử dụng tools tracking thông dụng như Jira, Mantis, Bugzilla, Application Lifecycle Management (ALM)
Mobile application testing: Cài đặt và test ứng dụng trên mobile
Windows, Website testing & Tools support: Test ứng dụng desktop, web, giả lập các trình duyệt khác nhau trên máy tính
Risk based testing process and implementation: Đánh giá rủi ro trong kiểm thử
Coding: SQL, HTML, CSS

Nếu bạn theo hướng Automation thì ngoài những kiến thức trên, bạn cần nắm thêm:

Lập trình: Java, C# (.Net) và ngôn ngữ khác sử dụng để hỗ trợ như AutoIT, Python
Automation Tool/Framework phổ biến như: Ranorex, Selenium, Appium, TestComplete
Các Tools khác như: Jmeter, SoapUI

Học Tester Cho Người Trái Ngành Bắt Đầu Từ Đâu

IV. Học Tester Cho Người Trái Ngành Cần Những Gì

Dân trái ngành nên bắt đầu từ đâu

Đây là câu hỏi mà bất kỳ bạn nào trái ngành cũng hỏi và sẽ cảm thấy hoang mang không biết nên bắt đầu như thế nào? Cần học những gì? Bắt đầu học cái gì? Có nên đi học ở trung tâm không hay xin đi học việc, lộ trình thăng tiến như thế nào và đây chỉ là một số vấn đề mà hầu hết các bạn đều quan tâm.

Có thể do chưa có cái nhìn tổng quan về nghề nên bạn vẫn còn băn khoăn, đây cũng là vấn đề bình thường đối với những bạn trái ngành mà đôi lúc đúng chuyên ngành cũng gặp phải.

Học 1 khoá cơ bản trước để biết được bạn có phù hợp với nghề này hay không.
Tham gia chương trình đào tạo Tester căn bản chuyên sâu dành cho Tester. Chương trình đáng tham gia nhất dành cho mọi Tester, bạn sẽ sở hữu tất cả kỹ năng cần thiết của 1 Tester như: Phân tích dự án, Test Plan, Test Scenario, Test Case, Bug và cách dùng các công cụ hỗ trợ cho việc kiểm thử.

Học Tester Cho Người Trái Ngành Cần Học Tester Cho Người Trái Ngành Cần Những GìNhững Gì

V. Lộ Trình Học Tester Cho Người Trái Ngành

Lộ trình phát triển của nghề Tester cho người trái nghành cũng vô cùng rõ ràng và đầy tiềm năng, được chia theo các level sau:

Level 1: Fresher. Là những bạn mới tốt nghiệp các khóa đào tạo Tester cơ bản và bắt đầu đi làm Tester. Ở level này, những bạn Tester hoàn toàn là các bạn mới học xong các khóa học về Kiểm thử phần mềm, mới tiếp xúc môi trường doanh nghiệp, hoặc có thể là những người đã đi làm trái ngành mới thay đổi công việc sang Tester.

Level 2: Junior. Ở level junior, bạn Tester đã hiểu thực thi các test case, thêm vào đó, có thể báo cáo các bugs nếu có.

Level 3: Senior. Đây là những chuyên gia thành thạo về công nghệ testing, nắm rõ các yêu cầu kiểm thử phần mềm cho các doanh nghiệp với các ứng dụng phức tạp như tài chính, sức khỏe, thương mại điện tử…

Level 4: Test Leader. Thông thường, sau khoảng 5 năm kinh nghiệm trở lên, tester có thể nắm giữ vai trò quản lý. Những người này chịu trách nhiệm tổ chức công việc cần được thực hiện và phân công nhiệm vụ cụ thể cho các Tester trong team dự án. Tương ứng với số năm kinh nghiệm Test Leader có sẽ là quy mô lớn, nhỏ khác nhau mà các đội họ sẽ được quản lý.

Level 5: Test Manager. Là những người tổ chức và điều phối các nhóm kiểm thử (test team): quản lý metrics, lập kế hoạch chiến lược và đưa ra dự đoán.

Level 6: Senior Test Manager. Tùy thuộc vào độ cứng và số năm kinh nghiệm, Test Manager có thể đạt được vị trí Senior Test Manager.

Bên cạnh việc trở thành chuyên gia trong nghề Tester, Sau lúc có đủ kiến thức và kinh nghiệm ở level 4, bạn có thêm các hướng đi mới như: trở thành BA (Business Analyst) hoặc PM (Project Manager- quản lý dự án). Đây đều là các hướng phát triển rất tiềm năng cho các bạn Tester.

Lộ Trình Học Tester Cho Người Trái Ngành

VI. Người Trái Ngành Nên Học Tester Ở Trung Tâm Nào

Tester hay còn gọi là kiểm thử phần mềm đang là 1 ngành nghề hot hiện nay trong lĩnh vực IT. Do nhu cầu nhân lực ngày càng tăng cao vậy nên các trung tâm đào tạo tester ngày càng phổ biến. Chính vì điều đó mà nhiều bạn trái nghành không biết mình nên học Tester ở đâu tốt nhất bởi có nhiều trung tâm đào tại Tester kém uy tín khiến bạn cảm thấy lo lắng khi đưa ra quyết định lựa chọn.

Và trong bài viết ngày hôm nay, Techacademy xin gửi đến bạn danh sách những địa chỉ đào tạo Tester hàng đầu Việt Nam được rất nhiều bạn học viên đánh giá cao để các bạn có thể tham khảo.

+ Trung Tâm Đào Tạo Techacademy

Techacademy là 1 trong các cơ sở đào tạo Tester có mặt tại địa bàn TP. Hà Nội. Các giảng viên của Techacademy đều là các Test Leader tới từ các công ty công nghệ như Viettel, FPT Software,… với nhiều năm kinh nghiệm trong nghề truyền tải cho học viên những kiến thức kiểm thử phần mềm chuyên nghiệp thực hành từ những dự án thật, các kỹ năng mềm cần thiết lúc làm việc tại các công ty phần mềm.

Áp dụng các cách dạy học tiên tiến, sáng tạo giúp buổi học trở nên sôi động với nhiều kiến thức bổ ích. Giúp học viên sau lúc học xong thi tuyển, phỏng vấn và làm việc tốt tại các tập đoàn và các công ty.

Vì sao bạn nên lựa chọn Trung tâm Techacademy?

Chương trình học phù hợp với tất cả đối tượng.
Hỗ trợ việc làm cho tất cả học viên.
Giáo trình bản quyền.
Giảng viên là Manager/ Leader Công ty nước ngoài và Tập Đoàn lớn trong nước có nhiều năm kinh nghiệm.
Học phí siêu siêu ưu đãi.
Hình thức học linh hoạt kết hợp online và offline (Phù hợp cả với các bạn tỉnh xa và nước ngoài)

Học các khóa học tại Techacademy, bạn sẽ được cung cấp đầy đủ các kiến thức căn bản từ cơ bản đến nâng cao để trở thành chuyên viên kiểm thử phần mềm chuyên nghiệp với phương pháp thực hành thực chiến trên dự án thật giúp học viên có cái nhìn về nghề tester, hiểu rõ nó không còn bỡ ngỡ thích nghi được với công việc khi làm việc tại các công ty phần mềm.

Với các khóa học tester cho người mới bắt đầu, bạn sẽ nắm chắc các kiến thức căn bản cùng như thành thạo các kỹ năng kiểm thử trong thực tế mà không chỉ có các khóa học offline tại trung tâm mà còn các khóa học tester Online đều được xây dựng lộ trình rõ ràng từ các chuyên gia.

Những năm qua, Techacademy vẫn luôn tự hào là cầu nối thành công giữa Nhà tuyển dụng và Học viên, giúp tạo cơ hội cho các bạn sinh viên ra trường, các nhân viên phần mềm nâng cao trình độ và cung cấp nguồn nhân lực chất lượng cho các Tập Đoàn và các Công Ty Phần Mềm.

Tham gia các khóa học tester tại Techacademy chính là nắm bắt cơ hội việc làm tốt, lương cao dành cho các bạn học CNTT, Hệ Thống Thông Tin, Toán Tin, An Toàn Thông Tin… và các bạn trái ngành muốn chuyển ngành. Hiện trung tâm có rất nhiều ưu đãi hấp dẫn mà bạn không thể bỏ lỡ. Vì thế hãy nhanh tay đăng ký ngay từ bây giờ bạn nhé!

+ Testing VN

Nếu bạn là dân IT về Tester chắc bạn không còn xa lạ gì với Testing VN (testing.vn), đây là một trong những trung tâm đi đầu trong lĩnh vực đào tester tại TP. HCM. Với nhiều năm kinh nghiệm trong việc đào tạo tester, khi đến với trung tâm chắc chắn bạn sẽ nhận lại được lượng kiến thức tận dụng trong khi làm việc.

Đến với khóa đào tạo tester tại Testing VN, có thể áp dụng được trong công việc, không giảng dạy truyền đạt những nội dung mang tính lý thuyết thiếu thực tế. Một khóa đào tạo tester sẽ giúp bạn nắm vững kiến thức hơn, đối với những người chưa biết gì thì có thể tìm hiểu rõ hơn về công việc này và hoàn toàn có thể tự tin ứng tuyển vào các công ty khi vừa hoàn thành khóa đào tạo.

Giới thiệu việc làm cho học viên, khi hoàn thành xong khóa đào tạo, học viên sẽ được trung tâm giới thiệu đến các tập đoàn các công ty liên kết với trung tâm, bạn sẽ không phải đau đầu về vấn đề tìm việc làm.

Tại sao nên học đào tạo tester tại Testing VN?

Đội ngũ nhân viên giảng dạy đẳng cấp nhiều năm kinh nghiệm có kiến thức chuyên sâu, kiến thức giảng dạy tốt giúp học viên tiếp thu một cách nhanh nhất.
Kiến thức không sáo rỗng, chú trọng vào thực tế không lan man những lý thuyết suông không thực tế.
Đội ngũ tư vấn nhiệt tình, sẵn sàng giải đáp mọi thắc mắc của học viên cho dù ngoài giờ học, chỉ cần bạn khúc mắc ở đâu cần giải thích chúng tôi sẽ hỗ trợ hết mình.
Phòng họp mới, hiện đại, rộng rãi, giúp học viên cảm thấy thỏa mái nhất khi đi học.
Học phí tham khảo: 3.250.000 đồng

Nếu bạn chưa biết lựa chọn đơn vị nào thì trung tâm đào tạo Tester Hà Nội sẽ là một lựa chọn đúng đắn và không khiến bạn thất vọng.

+ FPT Software Academy

Bạn đang muốn tham gia một khóa đào tạo bài bản, từ đầu về CNTT và nghề kiểm thử phần mềm – tester? Bạn muốn học kiểm thử phần mềm nhưng không thể tự học được ở nhà? Và đang băn khoăn với các khóa đào tạo Tester đắt đỏ ở Hà Nội? Bạn đang là sinh viên năm cuối ngành ngoại ngữ, kinh tế…. và vẫn loay hoay chưa định hướng được công việc tương lai?

Bạn muốn thử sức mình & theo đuổi lĩnh vực công nghệ thông tin – ngành đang có nhu cầu nhân lực nóng bỏng nhất trên thị trường lao động nhưng lo sợ kiến thức của mình không đủ? Bạn tự tin với khả năng ngoại ngữ của mình và sẵn sàng dấn thân vào thử thách tại lĩnh vực CNTT?

Nếu bạn đã quá mệt mỏi với những câu hỏi đó, thì FPT Software Academy là sự lựa chọn hoàn hảo dành cho bạn – nơi bạn có thể vừa được củng cố kiến thức, vừa được “thực chiến” lại vừa có “tiền”.

Tại đây, bạn sẽ được đào tạo từ đầu các kiến thức từ căn bản đến nâng cao về:

Tổng quan ngành phần mềm – CNTT, quy trình phát triển phần mềm
Các kiến thức, khái niệm cơ bản về kiểm thử phần mềm
Các giai đoạn kiểm thử trong dự án
Các loại & kỹ thuật kiểm thử căn bản.
Hệ quản trị cơ sở dữ liệu SQL dùng trong kiểm thử
Các kiến thức về: Concept Test, Test Process, Test level, Test Type, Test Plan…

Đặc biệt, bạn sẽ có cơ hội tham gia On-job-training tại các dự án phát triển phần mềm cho nhóm các thiết bị trên Ô tô hạng sang và trải nghiệm môi trường làm việc toàn cầu với các khách hàng lớn tại Đức, Nhật Bản và Hàn Quốc… Rèn luyện các kỹ năng mềm: Viết email, kỹ năng phỏng vấn, thuyết trình, kỹ năng phân tích giải quyết vấn đề. Nâng tầm khả năng ngoại ngữ: đọc dịch tài liệu chuyên ngành, giao tiếp thường xuyên tại Câu lạc bộ Tiếng Anh của Frehser Academy.

Học phí tham khảo: 8.900.000 đồng cho một khóa học Software Testing (2 tháng) tại FPT Software Academy, bạn sẽ nhận được: 03 khóa học chuyên sâu từ cơ bản đến nâng cao cùng hệ thống các bài thực hành Lab/mini Project để trở thành Chuyên viên Kiểm thử phần mềm chuyên nghiệp.

Người Trái Ngành Nên Học Tester Ở Trung Tâm Nào

VII. Cách Viết CV Tester Cho Người Trái Ngành

Những ai là fan của IT chắc hẳn hiểu rất rõ về việc làm Tester và vai trò của nó trong đời sống hiện nay. Tuy nhiên, ngay cả những người dày mình kinh nghiệm cũng chưa chắc sở hữu việc làm bởi vì đây là công việc không chỉ đòi hỏi chuyên môn trình độ cao mà ứng viên cần phải chỉn chu khi tham gia ứng tuyển.

Chuẩn bị một mẫu CV Tester đầy đủ, chuẩn xác và hấp dẫn chắc chắn cơ hội của bạn sẽ được gia tăng hơn nhiều. Nếu chưa biết trình bày mẫu CV ngành nghề này vậy thì hãy tham khảo ngay bài viết sau đây do techacademy.edu.vn chia sẻ nhé.

Mỗi danh mục trong CV Tester đều có vai trò nhất định, ngoài ra nhà tuyển dụng thường dựa vào những thông tin chính yếu, lấy chúng làm căn cứ để đưa ra quyết định tuyển dụng cuối cùng. Bạn có biết những thông tin này là gì không?

+ Thông tin cá nhân trong CV Tester

Không có gì thay đổi và khác biệt so với những mẫu CV ngành nghề khác, ở CV Tester bạn vẫn cần cung cấp đủ thông tin cơ bản như Họ tên, năm sinh, giới tính, quê quán, địa chỉ liên hệ gồm có số điện thoại và email.

Lưu ý, số điện thoại và địa chỉ email tuyệt đối không viết sai, sau chọn lọc rất có thể bạn sẽ là ứng viên sáng giá bước vào vòng trong. Tuy nhiên nếu như bạn cho thông tin sai thì dù có chuyên nghiệp nữa thì nhà tuyển dụng cũng không thể liên lạc với bạn được, đành nhường cơ hội đấy cho người khác.

+ Học vấn trong CV Tester trình bày ra sao?

Học vấn hay còn gọi là Trình độ học vấn, ở mục này hãy ghi rõ hệ tốt nghiệp của bạn là Trung cấp, cao đẳng hay đại học; Chuyên ngành; Các khóa học ngắn hạn khác,…

Trong trường hợp bạn có thành tích xuất sắc, từng được khen thưởng hay sở hữu bằng tốt nghiệp loại giỏi thì đừng ngại ghi thông tin chi tiết vào để gia tăng cơ hội cho bản thân mình nhé.

Một Tester có thể tốt nghiệp ở 1 số trường uy tín như Học viện Công nghệ Bưu chính Viễn thông – Khoa Viễn thông, trường Đại học Công nghệ thông tin,…

+ Kỹ năng chuyên môn của Tester trong CV xin việc

Kỹ năng chuyên môn của Tester sẽ bao gồm tất cả những gì bạn sở hữu có thể phục vụ cho công việc của mình.

Một số kỹ năng mà bạn có thể kể đến như sau:

– Biết test API với Rest Client

– Làm tài liệu SRS, có khả năng tư duy và phân tích tốt, hỗ trợ tham gia phân tích nghiệp vụ

– Có khả năng viết Testcase tốt và dùng thành thạo

– Có thể test hiệu năng cơ bản với Tool JMeter

– …

Nói chung những kỹ năng nào mà bạn cảm thấy phù hợp và có liên quan trực tiếp tới công việc Tester thì có thể liệt kê vào mục này.

+ Kinh nghiệm nghề nghiệp trong CV Tester

Kinh nghiệm nghề nghiệp trong CV Tester có thể được viết theo nhiều trình tự khác nhau, nhưng chủ yếu vẫn ưu tiên cho công việc gần nhất sau đó mới tới những công việc xa hơn.

Tuy nhiên, khi liệt kê bạn cần ghi nhớ rằng những việc làm đó phải thực sự liên quan và phục vụ cho công việc Tester hiện tại. Đương nhiên để thuyết phục hơn thì bạn cần nêu ra thành quả mình đạt được trong quá trình làm việc đó, thành quả càng cao thì CV của bạn càng có giá trị.

Kinh nghiệm trong CV Tester bạn có thể trình bày theo ví dụ sau đây:

“10/2016 làm việc tại Trung tâm Đào tạo Tester XYZ, trong đó một số công việc đã làm cụ thể như sau:

– Tìm hiểu nghiệp vụ hệ thống sau đó viết testcase

– Thực hiện công việc test dự án, đôn đốc Dev fix khi có lỗi này xuất hiện

– Thực hiện làm test Report cho QTDA

– Có thể làm Performance testing với Tool JMeter

+ Trình bày Các dự án trong CV Tester

Đối với một Tester, thông tin dự án rất quan trọng, nó cho thấy năng lực thực sự của ứng viên khi đứng trước nhà tuyển dụng. Bạn nên ghi dự án như thế nào, hãy xem gợi ý dưới đây:

“Bạn tham gia dự án mang tên Hệ thống Quản lý Nhân sự với vai trò là Tester, trong đó:

– Thực hiện công tác tìm hiểu nghiệp vụ Đặc tả yêu cầu, biết lập test plan và viết testcase

– Thực hiện test dự án thường xuyên, đồng thời phối hợp với Developer để báo lỗi Bug hoặc defect

Nếu có thêm kinh nghiệm nào nữa thì bạn hãy viết theo gợi ý này nhé, hãy đưa ra khoảng 3 dự án để chứng minh bạn có thể làm tốt vai trò này.

The post Học Tester Cho Người Trái Ngành first appeared on Techacademy.

source https://techacademy.edu.vn/hoc-tester-cho-nguoi-trai-nganh/

Virtual Trong C++

Ở bài này, chúng ta sẽ tìm hiểu virtual trong C++. Từ khoá virtual có một số đặc tính khá thú vị mà mình muốn chia sẻ với các bạn qua bài viết ngày hôm nay. Hãy cùng Techacademy tìm hiểu nhé.

1. Virtual Trong C++ Là Gì ? Tác Dụng Của Virtual Trong C++

Một số tài liệu có viết công dụng của Virtual Function như sau:

“Virtual Function là để khai báo một function ở class cha (base class) mà sau đó các class kế thừa (derived class) có thể override function đó”

Nhưng chờ đã, có gì không ổn ở chỗ này, nếu chỉ là để override thôi thì mình hoàn toàn có thể khai báo function ở base class mà không cần virtual thì vẫn được cơ mà. Vậy ko lẽ đồng chí Virtual Function này vô dụng? Để làm rõ vấn đề cũng như hạn chế buồn ngủ vì phải đọc quá nhiều chữ, chúng ta thử xét ví dụ nhỏ sau:

class Buffalo {
public:
    void  action(){printf("I'm eating grass\n");};
}; 

class YoungBuffalo : public Buffalo {
    void action(){printf("I'm typing keyboard\n");};
};

int main()
{
  Buffalo *elon = new Buffalo();
  YoungBuffalo *andy = new YoungBuffalo();

  elon->action();
  andy->action();
}

Output sẽ ra như thế này:

I'm eating grass
I'm typing keyboard

Nếu chỉ xét đến đây thì cậu virtual chắc sẽ hơi buồn vì mọi chuyện có vẻ vẫn ổn mà không cần đến sự có mặt của nó. Vì vậy chúng ta thử xét tiếp 1 ví dụ khác để làm chỗ cho virtual toả sáng một chút.

class Buffalo {
public:
    void  action(){printf("I'm eating grass\n");};
}; 

class YoungBuffalo : public Buffalo {
public:
    void action(){printf("I'm typing keyboard\n");};
};

int main()
{
  Buffalo *elon = new Buffalo();
  Buffalo *andy = new YoungBuffalo(); // khác với lúc nãy là YoungBuffalo *andy = new YoungBuffalo();

  elon->action();
  andy->action();
}

Lần này output sẽ là như thế này:

I'm eating grass
I'm eating grass

Đến đây thì chắc không cần phải quá tinh mắt bạn cũng đã nhận ra vấn đề rồi đúng không. Mặc dù andy được tạo ra từ constructor của class YoungBuffalo thế nhưng nó hành xử lại như thể nó là một Buffalo. Thế nhưng ví dụ này trông hơi bị thiếu thông minh vì chả mấy ai khai báo Buffalo *andy = new YoungBuffalo(); như này để tự làm khó mình cả. Mình sẽ xét một ví dụ thực tế hơn chút nữa.

class Buffalo {
public:
    void  action(){printf("I'm eating grass\n");};
}; 

class YoungBuffalo : public Buffalo {
public:
    void action(){printf("I'm typing keyboard\n");};
};

void takeAnBuffalo(Buffalo* buffalo){
    buffalo->action();
}

int main()
{
  Buffalo *elon = new Buffalo();
  Buffalo *andy = new YoungBuffalo(); 
  takeAnBuffalo(elon);
  takeAnBuffalo(andy);
}

Output sẽ vẫn lại là:

I'm eating grass
I'm eating grass

Lúc này thì vấn đề thực sự đã rõ rồi, vì vậy chúng ta sẽ fix với vấn đề này với virtual như sau:

class Buffalo {
public:
    virtual void  action(){printf("I'm eating grass\n");}; // thêm virtual vào chỗ này
}; 

class YoungBuffalo : public Buffalo {
public:
    void action(){printf("I'm typing keyboard\n");};
};

void takeAnBuffalo(Buffalo* buffalo){
    buffalo->action();
}

int main()
{
  Buffalo *elon = new Buffalo();
  Buffalo *andy = new YoungBuffalo();
  takeAnBuffalo(elon);
  takeAnBuffalo(andy);
}

Output:

I'm eating grass
I'm typing keyboard

Virtual Trong C++ Là Gì ? Tác Dụng Của Virtual Trong C++

2. Pure Virtual Function Trong C++ Là Gì

Hàm thuần ảo (pure virtual function) được sử dụng khi:

Không cần sử dụng hàm này trong lớp cơ sở, chỉ phục vụ cho lớp dẫn xuất
Lớp dẫn xuất bắt buộc phải định nghĩa lại hàm thuần ảo

Ví dụ, chúng ta có 1 lớp cơ sở là Shape. Các lớp dẫn xuất của lớp Shape là Triangle, Square và Circle. Chúng ta muốn tính diện tích của các hình này.

Chúng ta có thể tạo ra một hàm thuần ảo có tên là calculateArea() trong lớp Shape. Các lớp Triangle, Square và Circle phải định nghĩa lại hàm calculateArea() với công thức tính diện tích khác nhau cho mỗi hình.

Hàm thuần ảo không có thân hàm và bắt buộc phải kết thúc với “= 0”.

class Shape{
public:
   // creating a pure virtual function
   virtual void calculateArea() = 0;
};

Lưu ý: Cú pháp “= 0” không phải là gán hàm thuần ảo có giá trị bằng 0. Nó chỉ là cú pháp cho biết đó là hàm thuần ảo (pure virtual function).

3. Virtual Destructor Trong C++

Trong một lớp thì Destructor có thể được đánh dấu làm hàm ảo còn Constructor thì không được đánh dấu là hàm ảo.

virtual Product();   // illegal
virtual ~Product();  // legal

Xét một vài ví dụ để làm rõ Virtual Destructor. Giả sử có lớp cha Base và một lớp con Derived được hiện thực như dưới đây.

Trường hợp 1: Phương thức lớp cha không đánh dấu Virtual

Phương thức hủy lớp cha không được đánh dấu là hàm ảo:

class Base
{
public:
   Base() {};
   ~Base() { cout << "Destructor Base\n"; };
};


class Derived : public Base
{
public:
   Derived() {};
   ~Derived() { cout << "Destructor Derived\n"; }
};

int main()
{
   Base *b = new Derived();
   delete b;

   return 0;
}

Sau khi Build và Debug, chỉ có dòng “Destructor Base” được xuất ra, có nghĩa là chỉ phương thức lớp cha được gọi nhưng phương thức của lớp con không được gọi. Dẫn đến có thể gây nên thiếu sót như không thu hồi bộ nhớ các cấp phát động của lớp cha hoặc các thủ tục cần thực hiện trước khi đối tượng được thu hồi.

Xét tiếp ví dụ dưới đây, tương tự như ví dụ trên nhưng có sửa đổi ở lớp Derived

class Base
{
public:
   Base() {};
   ~Base() { cout << "Destructor Base\n"; };
};


class Derived : public Base
{
private:
   int* m_array;
public:
   Derived() { this->m_array = new int[1024]; };
   ~Derived()
   {
      cout << "Destructor Derived\n";
      delete this->m_array;
   }
};

int main()
{
   Base *b = new Derived();
   delete b;
   return 0;
}

Với lớp con như trên, mặc dù định nghĩa phương thức để giải phóng m_array nhưng phương thức của lớp con không được gọi. Có nghĩa là chương tình đã rò rỉ 1024*4 bytes bộ nhớ.

Trường hợp 2: Phương thức lớp cha có đánh dấu Virtual

Phương thức lớp cha được đánh dấu là phương thức ảo:

class Base
{
public:
   Base() {};
   virtual ~Base() { cout << "Destructor Base\n"; };
};


class Derived : public Base
{
public:
   Derived() {};
   ~Derived() { cout << "Destructor Derived\n"; }
};

int main()
{
   Base *b = new Derived();
   delete b;
   return 0;
}

Bulid và Debug thì chương trình xuất ra hai dòng là

Destructor Derived
Destructor Base

Như vậy phương thức hủy của lớp con được gọi trước sau đó mới gọi phương thức hủy lớp cha và các thủ tục cần thiết trước khi hủy các đối tượng đã được thực hiện đầy đủ.

4. Nhược Điểm Của Các Hàm Ảo

Vì hầu hết thời gian bạn sẽ muốn các hàm của mình là ảo, tại sao không làm cho tất cả các hàm trở nên ảo? Câu trả lời là bởi vì nó không hiệu quả – việc giải quyết một cuộc gọi hàm ảo mất nhiều thời gian hơn là giải quyết một cuộc gọi thông thường. Hơn nữa, trình biên dịch cũng phải cấp phát một con trỏ phụ cho mỗi đối tượng lớp có một hoặc nhiều hàm ảo.

5. Tại Sao Không Nên Gọi Các Hàm Ảo Từ Các Hàm Tạo Hoặc Hàm Hủy

Ở đây, Bạn không nên gọi các hàm ảo từ các hàm tạo hoặc hàm hủy. Tại sao?

Hãy nhớ rằng khi một lớp Derived được tạo, phần Base được xây dựng trước. Nếu bạn đã gọi một hàm ảo từ hàm tạo cơ sở và phần lớp Derived thậm chí chưa được tạo, thì nó không thể gọi hàm của Derived vì không có đối tượng Derived được khởi tạo để gọi hàm. Trong C ++, nó sẽ gọi hàm trong class Base thay thế.

Một vấn đề tương tự tồn tại cho hàm huỷ. Nếu bạn gọi một hàm ảo trong hàm hủy của lớp Cơ sở, nó sẽ luôn gọi hàm của lớp Cơ sở, bởi vì phần Derived của lớp đã bị hủy.

Quy tắc: Không bao giờ gọi các hàm ảo từ các hàm tạo hoặc hàm hủy.

Tại Sao Không Nên Gọi Các Hàm Ảo Từ Các Hàm Tạo Hoặc Hàm Hủy

6. Tại Sao Bạn Nên Khai Báo Một Hàm Hủy Là Ảo

Giả sử có class Parent và class Child kế thừa từ Parent.

Ta định nghĩa con trỏ: Parent * p = new Child();

Lúc này để tạo ra Child(), thì Parent() phải được tạo ra trước. Khi chúng ta delete p, thì cả 2 đối tượng này cũng phải được gọi Destructor. Vậy nếu không khai báo virtual cho hàm Destructor của Parent, thì chỉ Destructor của Parent được gọi, đối tượng Child() vẫn còn đó.

Tại Sao Bạn Nên Khai Báo Một Hàm Hủy Là Ảo

The post Virtual Trong C++ first appeared on Techacademy.

source https://techacademy.edu.vn/virtual-trong-c/

Các Thuật Toán Tìm Kiếm Trong C++

Trong hầu hết các hệ quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin khác nhau. Bởi vậy, khi xây dựng một hệ quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong những chủ đề được quan tâm hàng đầu. Hãy cũng mình tìm hiểu về thuật toán tìm kiếm phổ biến nhé.

1. Thuật Toán Tìm Kiếm Là Gì

Tìm kiếm là quá trình tìm một phần tử nằm trong một tập hợp nhiều phần tử dựa vào một miêu tả nào đó. Ví dụ bạn cần tìm đồng 10k trong một đống tiền từ 10k đến 100k thì quá trình đó ta gọi là tìm kiếm.

Nếu một tập hợp đã được sắp xếp thì quá trình tìm kiếm trong tập hợp đó sẽ nhanh hơn. Ở thí dụ trên nếu đống tiền từ 10k đến 100k đã được sắp xếp tăng dần hoặc giảm dần thì ta cực kỳ dễ dàng tìm kiếm tờ 10k. Nhưng nếu đó là 1 đống tiền lộn xộn thì bạn sẽ mất nhiều thời gian để xử lý chúng.

Vậy thuật toán tìm kiếm là thuật toán dùng để kiếm tìm phần tử trong 1 danh sách cho trước theo một tiêu chí nhất định. Chúng ta thường sử dụng hai thuật toán đó là thuật toán tìm kiếm tuyến tính và thuật toán tìm kiếm nhị phần.

Thuật toán tìm kiếm tuyến tính là quá trình tìm kiếm trong một tập hợp chưa sắp xếp, giống với đống tiền chưa được sắp xếp ở ví dụ trên. Còn thuật toán tìm kiếm nhị phân là quá trình tìm kiếm trong một dãy đã được sắp xếp. Cả hai thuật toán đều có những ưu và nhược điểm khác nhau.

2. Các Thuật Toán Tìm Kiếm Trong C++

Trong bài viết này, mình sẽ giới thiệu đến các bạn các thuật toán tìm kiếm trong C ++ phổ biến nhất. Giờ hãy bắt đầu tìm hiểu về các thuật toán tìm kiếm này nhé!

+ Thuật Toán Tìm Kiếm Tuyến Tính

Thuật toán tìm kiếm tuyến tính (linear search) hay còn gọi là thuật toán tìm kiếm tuần tự (Sequential search) là một phương pháp tìm kiếm một phần tử cho trước trong một danh sách bằng cách duyệt lần lượt từng phần tử của danh sách đó cho đến lúc tìm thấy giá trị mong muốn hay đã duyệt qua toàn bộ danh sách.

Tìm kiếm tuyến tính là một giải thuật rất đơn giản khi hiện thực. Giải thuật này tỏ ra khá hiệu quả khi cần tìm kiếm trên một danh sách đủ nhỏ hoặc một danh sách chưa sắp thứ tự đơn giản. Trong trường hợp cần tìm kiếm nhiều lần, dữ liệu thường được xử lý một lần trước khi tìm kiếm: có thể được sắp xếp theo thứ tự, hoặc được xây dựng theo một cấu trúc dữ liệu đặc trưng cho giải thuật hiệu quả hơn,…

Bài toán: Cho một mảng mảng [] gồm n phần tử, hãy viết hàm để tìm kiếm một phần tử x đã cho trong mảng [].

Ví dụ:

Đầu vào: mảng A[] = {10, 20, 80, 30, 60, 50, 
                     110, 100, 130, 170}
          x = 110;
Đầu ra: 6
Phần tử x có mặt ở vị trí số 6

Đầu vào: mảng A[] = {10, 20, 80, 30, 60, 50, 
                     110, 100, 130, 170}
           x = 175;
Đầu ra: -1
Phần tử x không có trong mảng A[].

Mã giả

Phiên bản lặp tự nhiên

Đây là phiên bản hay gặp nhất của giải thuật này, kết quả trả về sẽ là vị trí của phần tử cần tìm hoặc một giá trị Δ thể hiện việc không tìm thấy phần tử trong danh sách đó.

1. For each item in the list:
    1. if that item has the desired value,
        1. stop the search and return the item's location.
2. Return 'Δ'

Nếu danh sách được lưu trữ dưới dạng mảng, vị trí của phần tử cần tìm có thể là chỉ số của nó trong mảng, còn giá trị Δ có thể là chỉ số nằm trước phần tử đầu tien (0 hoặc -1 tùy vào danh sách).

Nếu danh sách là một danh sách liên kết, vị trí của phần tử được trả về có thể nằm dưới dạng địa chỉ của no, còn giá trị Δ có thể là giá trị null.

Phiên bản đệ quy

Đây là phiên bản đệ quy khi hiện thực giải thuật tìm kiếm tuần tự.

1. if the list is empty, return Λ;
2. else
   1. if the first item of the list has the desired value
      1. return its location;
   2. else 
      1. search the value in the remainder of the list, and return the result.

Sử dụng phần tử cầm canh

Một phương pháp được sử dụng để cải thiện hiệu quả của giải thuật là chèn phần tử muốn tìm kiếm và cuối danh sách như một phần tử cầm canh (sentinel) như được trình bày dưới đây:\

1. Set A[n + 1] to x. 
2. Set i to 1.
3. Repeat this loop:
    1. If A[i] = x, 
       1. exit the loop.
    2. Set i to i + 1.
4. Return i.

Việc thêm phần tử cầm canh giúp giảm bớt việc so sánh chỉ số hiện tại i với số các phần tử n ở mỗi vòng lặp. Tuy nhiên, điều này chỉ có thể được sử dụng khi vị trí cuối cùng của danh sách tồn tại nhưng chưa được sử dụng.

Viết thuật toán tìm kiếm tuyến tính với ngôn ngữ lập trình C, C++, Java, Python3

Tìm kiếm tuyến tính với C++:

#include <iostream> 
using namespace std; 
  
int search(int arr[], int n, int x) 
{ 
    int i; 
    for (i = 0; i < n; i++) 
        if (arr[i] == x) 
            return i; 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = search(arr, n, x); 
   (result == -1)? cout<<"Element is not present in array" 
                 : cout<<"Element is present at index " <<result; 
   return 0; 
}

Tìm kiếm tuyến tính với C:

#include <stdio.h> 
  
int search(int arr[], int n, int x) 
{ 
    int i; 
    for (i = 0; i < n; i++) 
        if (arr[i] == x) 
            return i; 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = search(arr, n, x); 
    (result == -1) ? printf("Element is not present in array") 
                   : printf("Element is present at index %d", 
                            result); 
    return 0; 
}

Tìm kiếm tuyến tính với Python3:

def search(arr, n, x): 
  
    for i in range (0, n): 
        if (arr[i] == x): 
            return i; 
    return -1; 
  
# Driver Code 
arr = [ 2, 3, 4, 10, 40 ]; 
x = 10; 
n = len(arr); 
result = search(arr, n, x) 
if(result == -1): 
    print("Element is not present in array") 
else: 
    print("Element is present at index", result);

Tìm kiếm tuyến tính với Java:

class GFG  
{  
public static int search(int arr[], int x) 
{ 
    int n = arr.length; 
    for(int i = 0; i < n; i++) 
    { 
        if(arr[i] == x) 
            return i; 
    } 
    return -1; 
} 
  
public static void main(String args[]) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 };  
    int x = 10; 
      
    int result = search(arr, x); 
    if(result == -1) 
        System.out.print("Element is not present in array"); 
    else
        System.out.print("Element is present at index " + result); 
} 
}

Tìm kiếm tuyến tính với PHP:

<?php 
  
function search($arr, $x) 
{ 
    $n = sizeof($arr); 
    for($i = 0; $i < $n; $i++) 
    { 
        if($arr[$i] == $x) 
            return $i; 
    } 
    return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40);  
$x = 10; 
      
$result = search($arr, $x); 
if($result == -1) 
    echo "Element is not present in array"; 
else
    echo "Element is present at index " , 
                                 $result; 
?>

Tìm kiếm tuyến tính với C#:

using System;  
  
class GFG  
{  
    public static int search(int[] arr, int x) 
    { 
        int n = arr.Length; 
        for(int i = 0; i < n; i++) 
        { 
            if(arr[i] == x) 
                return i; 
        } 
        return -1; 
    } 
      
    public static void Main() 
    { 
        int[] arr = { 2, 3, 4, 10, 40 };  
        int x = 10; 
          
        int result = search(arr, x); 
        if(result == -1) 
            Console.WriteLine("Element is not present in array"); 
        else
            Console.WriteLine("Element is present at index "+ result); 
    } 
}

Chạy thử và xem kết quả:

Element is present at index 3

+ Thuật Toán Tìm Kiếm Nhị Phân

Thuật toán tìm kiếm nhị phân là một trong các thuật toán sắp xếp được sử dụng rất nhiều trong thực tế. Hãy cùng mình đi tìm hiểu thuật toán tìm kiếm này nhé.

Tìm kiếm là một phần không thể thiếu của mọi ứng dụng, website hay phần mềm. Tính năng tìm kiếm cho phép người sử dụng nhanh chóng truy vấn và tìm kiếm các bản ghi theo mong muốn. Và một công cụ tìm kiếm nổi tiếng nhất hàng ngày chúng ta vẫn thường sử dụng đó là Google search.

Bài viết ngày hôm nay Techacademy sẽ giới thiệu cho độc giả một thuật toán tìm kiếm tối ưu áp dụng đối với trường hợp dữ liệu số đã sắp xếp.

Phát biểu thuật toán tìm kiếm nhị phân(Binary search)

Cho một mảng đã sắp xếp arr[] có n phần tử, viết một hàm tìm kiếm trả về chỉ số của phần tử có giá trị x trong arr[].

Giải thuật đơn giản nhất cho bài toán này là sử dụng linear search(tìm kiếm tuyến tính). Tức là bạn sẽ phải đi qua từng phần tử của mảng để đối chiếu với x cần tìm. Thuật toán này trong trường hợp xấu nhất cho độ phức tạp là O(n). Mình cũng sẽ minh họa code của thuật toán này dưới đây.

Đây là code C/C++ sử dụng linear search.

 
// Code from https://techacademy.edu.vn
 
#include <stdio.h>
 
int search(int arr[], int n, int x)
{
  int i;
  for (i = 0; i < n; i++)
    if (arr[i] == x)
      // Trả về chỉ số khi tìm thấy
      return i;
  // Nếu không tìm thấy trả về -1. Vì chỉ số mảng >= 0
  return -1;
}
 
int main() {
  int arr[] = {2, 3, 4, 10, 40};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = search(arr, n, x);
  if (result != -1) {
    printf("%d xuat hien tai chi so %d", x, result);
  } else {
    printf("%d khong co trong mang", x);
  }
  return 0;
}

Ý tưởng của thuật toán tìm kiếm nhị phân

Chú ý: Trong bài viết tôi giả sử mảng đang sắp xếp tăng dần. Với trường hợp mảng sắp xếp giảm dần, bạn đọc sau khi hiểu thuật toán sẽ có thể tự làm.

Do tính chất mảng đã sắp xếp, công việc tìm kiếm phần tử x có thể triển khai như sau:

Xét đoạn mảng arr[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:
Nếu phần tử arr[mid] = x. Kết luận và thoát chương trình.
Nếu arr[mid] < x. Chỉ thực hiện tìm kiếm trên đoạn arr[mid+1…right].
Nếu arr[mid] > x. Chỉ thực hiện tìm kiếm trên đoạn arr[left…mid-1].

Bằng cách áp dụng thuật toán tìm kiếm nhị phân, độ phức tạp cho trường hợp xấu nhất là O(log(n)).

Minh họa code cho thuật toán tìm kiếm nhị phân

Trong phần này, mình sẽ minh họa code sử dụng giải thuật đệ quy dùng Java và C/C++. Ngoài ra, tôi sẽ áp dụng thêm giải thuật khử đệ quy với C/C++.

Code minh họa C/C++ sử dụng đệ quy

 
// Code from https://nguyenvanhieu.vn
 
#include <stdio.h>
 
// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int binarySearch(int arr[], int l, int r, int x) {
  if (r >= l) {
    int mid = l + (r - l) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn
 
    // Nếu arr[mid] = x, trả về chỉ số và kết thúc.
    if (arr[mid] == x)
      return mid;
 
    // Nếu arr[mid] > x, thực hiện tìm kiếm nửa trái của mảng
    if (arr[mid] > x)
      return binarySearch(arr, l, mid - 1, x);
 
    // Nếu arr[mid] < x, thực hiện tìm kiếm nửa phải của mảng
    return binarySearch(arr, mid + 1, r, x);
  }
 
  // Nếu không tìm thấy
  return -1;
}
 
int main(void) {
  int arr[] = {2, 3, 4, 10, 40};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1)
    printf("%d xuat hien tai chi so %d", x, result);
  else
    printf("%d xuat hien tai chi so %d", x, result);
  return 0;
}

Code minh họa sử dụng đệ quy Java

 
// Code from https://nguyenvanhieu.vn
 
class BinarySearch {
  
  int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
      int mid = l + (r - l) / 2;
 
      // Nếu arr[mid] = x, trả về chỉ số và kết thúc
      if (arr[mid] == x)
        return mid;
 
      // Nếu arr[mid] > x, gọi đệ quy tìm kiếm bên trái
      if (arr[mid] > x)
        return binarySearch(arr, l, mid - 1, x);
 
      // Ngược lại, nếu arr[mid] < x, gọi đệ quy tìm kiếm bên phải
      return binarySearch(arr, mid + 1, r, x);
    }
 
    // Trong trường hợp không tìm thấy
    return -1;
  }
 
 
  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int arr[] = {2, 3, 4, 10, 40};
    int n = arr.length;
    int x = 10;
    int result = ob.binarySearch(arr, 0, n - 1, x);
    if (result == -1)
      System.out.println("Không tìm thấy phần tử " + x);
    else
      System.out.println("Phần tử " + x + " được tìm thấy tại chỉ số " +
                         result);
  }
}

Code khử đệ quy sử dụng C/C++

 
// Code from https://nguyenvanhieu.vn
 
#include <stdio.h>
 
// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int binarySearch(int arr[], int n, int x) {
  int r = n - 1; // chỉ số phần tử cuối
  int l = 0; // Chỉ số phần tử đầu tiên
  while (r >= l) {
    int mid = l + (r - l) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn
 
    // Nếu arr[mid] = x, trả về chỉ số và kết thúc.
    if (arr[mid] == x)
      return mid;
 
    // Nếu arr[mid] > x, cập nhật lại right
    if (arr[mid] > x)
      r = mid - 1;
    // Nếu arr[mid] < x, cập nhật lại left
    if (arr[mid] < x)
      l = mid + 1;
  }
 
  // Nếu không tìm thấy
  return -1;
}
 
int main(void) {
  int arr[] = {
    2,
    3,
    4,
    10,
    40
  };
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, n, x);
  if (result == -1)
    printf("%d xuat hien tai chi so %d", x, result);
  else
    printf("%d xuat hien tai chi so %d", x, result);
  return 0;
}

+ Thuật Toán Tìm Kiếm Nội Suy

Thuật toán tìm kiếm nội suy là một sự cải tiến của tìm kiếm nhị phân Binary Search. Nó có xu hướng tiến gần đến vị trí, giá trị tìm kiếm. Do đó tốc độ tìm kiếm được tối ưu rất cao và nhanh hơn nhiều so với Binary Search.

Cách thức hoạt động của nó dựa trên Binary Search, nhưng có sự cải tiến hơn. Đó chính là nó tìm ra phần tử gần với giá trị tìm kiếm nhất và bắt đầu từ đó để tìm.

Ví dụ:

Chúng ta có danh sách các sinh viên trong một lớp. Nếu chúng ta muốn tìm một bạn tên Tiến, thì chúng ta sẽ ưu tiên việc tìm kiếm từ cuối danh sách. Chứ không nên tìm kiếm từ đầu danh sách vì điều đó rất mất thời gian.

Với Interpolation Search nó sẽ linh hoạt hơn rất nhiều trong lúc tìm kiếm

Giả xử chúng ta có:

Left, right là hai vị trí đầu và cuối.
T là tập.
X là giá trị cần tìm.

Giải thích thuật toán

Bước 1:Chúng ta sẽ sử dụng công thức tìm phần tử chính giữa của tập theo cách tìm kiếm Binary Search:

Search = left + (right - left) * 1/2

Trong công thức trên chúng ta sẽ thay giá trị 1/2 bằng biểu thức sau:

(X - T[left]) / (T[right] - T[left])

Sau khi thay biểu thức vào công thức sẽ được công thức mới như sau:

Search = left + (X- T[left]) * (right – left) / (T[right] – T[left])

Bước 2: Bây giờ chúng ta sẽ kiểm tra T[Search] nếu bằng X thì Search chính là vị trí cần tìm.

Nếu Search < X thì tăng left lên một đơn vị rồi quay lại bước 1.
Nếu Search > X thì giảm right xuống một đơn vị rồi quay lại bước 1.

Thuật toán tìm kiếm Interpolation Search

int InterPolationSearch(int arr[], int n, int x)
{
  int left = 0;
  int right = n-1;
  while (left <= right && x >= arr[left] && x <= arr[right])
  {
    double val1 = (double) (x - arr[left]) / (arr[right]-arr[left]);
    int val2 = (right-left);
    int Search = left + val1*val2;
  
    if (arr[Search] == x)
      return Search;
  
    if (arr[Search] < x)
      left = Search + 1;
    else
      right = Search - 1;
  }
  return -1;
}

+ Thuật Toán Ternary Search

Tương tự với thuật toán tìm kiếm nhị phân, Ternary Search – Tìm kiếm tam phân là một kỹ thuật trong khoa học máy tính dùng để tìm kiếm giá trị lớn nhất (maximum) hay nhỏ nhất (minimum) của một unimodal function, và đây cũng là một ví dụ ứng dụng lớp thuật toán Chia để trị (divide and conquer).

Độ phức tạp thời gian: O (log [n]) trong đó cơ số của log = 3

Độ phức tạp của không gian: O (1) để thực hiện lặp lại trong khi O (log [n]) để thực hiện đệ quy

Ví dụ:

#include<iostream>
using namespace std;

int ternaryI(int a[], int target, int n) 
{
    int l = 0;
    int r = n-1;

    while( r-l>=0 ) {
        int partiton = (r-l)/3;
        int mid1 = l + partiton;
        int mid2 = r - partiton;

        if ( target == a[mid1])
            return mid1;
        else if ( target == a[mid2]) 
            return mid2;
        else if ( target < a[mid1] ) 
            r = mid1-1;
        else if ( target > a[mid2] )
            l = mid2+1;
        else {
            l = mid1+1;
            r = mid2-1;
        } 
    } // while ends

    return -1;
} // function ends

int main() 
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = 10;
    int target = 7;

    int tsi = ternaryI(arr, target, n);
    cout << "Result of TSI = " << tsi << endl;

    return 0;
} // main ends

+ Thuật Toán Jump Search

Bài hôm nay chúng ta cùng tìm hiểu về thuật toán Jump Search (Thuật toán tìm kiếm nhảy)

Nguyên lý cơ bản của Jump Search

Cũng giống như giải thuật Binary Search. Jump Search cũng yêu cầu danh sách đã cho phải là một danh sách đã được sắp xếp theo thứ tự đã biết.

Ví dụ là tăng dần.

Cơ chế của Jump Search đó là tìm ra một hệ số nhảy được tính bằng : Căn bậc hai của số phần tử.

Từ hệ số tìm được, Jump Search sẽ thực hiện nhảy phần tử theo hệ số để tìm ra phần từ lớn hơn giá trị tìm kiếm.

=> Phần tử tìm kiếm sẽ nằm trong khoảng của nhảy mà chứa phần từ lớn hơn giá trị tìm kiếm ở trên.

Minh Họa hình vẽ như sau:

Tôi có tập 9 phần từ đã được sắp xếp theo thứ tự tăng dần.

Tôi xác định giá trị nhảy là step = √9 = 3 .

Giả sử giá trị cần tìm là 33.

Sử dụng một biến prev để lưu vị trí bắt đầu.

Một biến jump để nhảy.

Step 1:

Gán prev = jump = 6

Nhảy jump = jump + step = 9 (bằng số phần tử, nếu jum lớn hơn n thì gán jum = n)

Lại kiểm tra T[jump – 1] => T[8] = 44 > 33 => Đã tìm được khoảng chứa giá trị cần tìm.

Khoảng chứa giá trị cần tìm là từ prev = 6 , jump = 9.

Lúc này chúng ta chỉ việc kiểm tra tuyến tính tệp từ vị trí prev đến jump để tìm ra giá trị cần tìm.

Sử dụng for hoặc while để duyệt phần tử trong khoảng prev – jump.

Các tính chất thuật toán.

– Tập cần tìm kiếm là phải được xắp xếp trước và biết rõ theo chiều tăng giảm.

– ĐỘ PHỨC TẠP HAY THỜI GIAN THỰC THI CỦA THUẬT TOÁN LÀ: O = √(n)

Thực hành Jump Search

Bây giờ từ nguyên lý ở trên chúng ta sẽ cùng thực hành với code c++

Hàm JumpSearch

 
 
// Techacademy.edu.vn
#include <iostream>
#include <conio.h>
#include <math.h>
 
int JumpSearch(int arr[], const int& n, const int& x)
{
  int step = sqrt(1.0*n);
  int prev = 0;
 
  int jump = step;
  //Find element > x
  while(arr[jump - 1] < x)
  {
    prev = jump;
    jump +=  step;
    if (jump > n)
      jump = n;
    if (prev > n)
      return -1;
  }
 
  // When found element > x.
  while(arr[prev] < x)
  {
    prev ++;
    if (prev == jump)
    {
      return -1;
    }
  }
 
  if (arr[prev] == x)
    return prev;
  return -1;
}

Hàm Main

 
 
int main(int argc, _TCHAR* argv[])
{
  int arr[] = {0, 1, 4, 7, 8, 9, 14, 16, 18, 19, 30, 34, 46, 48, 50, 55, 58};
  int s_val = 55;
  unsigned int num = sizeof(arr)/sizeof(arr[0]);
  int ret1 = JumpSearch(arr, num, s_val);
 
  if (ret1 != -1)
    std::cout << "Vi tri cua " << s_val <<  "la : " << ret1;
  else 
    std::cout << "Khong tim dc";
 
  _getch();
  return 0;
}

+ Thuật Toán Exponential Search

Bài hôm nay chúng ta cùng tìm hiểu về thuật toán Exponential Search (Thuật toán tìm kiếm theo số mũ)

Nguyên lý Exponential Search

+ Cũng yêu cầu dãy số đầu vào là một dãy đã được xắp xếp cho sẵn.

+ Kết hợp với việc tìm kiếm theo kiểu nhị phân.

+ Tìm ra khoảng con chứa giá trị cần tìm kiếm, và sau đó sử dụng tìm kiếm nhị phân cho khoảng con đó.

Độ phức tạp thời gian mà nó đạt được là: Log2(n).

Step 1:

+ Kiểm tra phần tử 0 của tập để xem nó có phải là phần tử tìm kiếm hay không.

+ Nếu không thì bắt đầu giá trị chạy từ 1 và kiểm tra nó < giá trị cần tìm hay không.

=> Nếu có, thì tiếp tục tăng giá trị chạy lên theo công thức : i = i*2;

=> Nếu không, thì chứng tỏ giá trị cần tìm đang năm trong khoảng từ i/2 đến i

Vì a[i] > X và vòng lặp trước đó là a[i/2] < X.

Do đó ta tìm được khoảng con chứa giá trị X cần tìm

Step 2:

Áp dụng Binary Search cho khoảng con vừa tìm được.

Thực hành

 
 
// Techacademy.edu.vn
#include <iostream>
#include <conio.h>
 
int BinarySearch(int arr[], const int&, const int&, const int&);
 
int ExponentialSearch(int arr[], int n, int x)
{
  if (arr[0] == x)
    return 0;
 
  int i = 1;
  while (i < n && arr[i] <= x)
    i = i*2;
  return BinarySearch(arr, i/2, std::min(i, n), x);
}
 
int BinarySearch(int arr[], const int& l, const int& r, const int& x)
{
  if (r >= l)
  {
    int mid = l + (r - l)/2;
 
    if (arr[mid] == x)
      return mid;
 
    if (arr[mid] > x)
      return BinarySearch(arr, l, mid-1, x);
 
    return BinarySearch(arr, mid+1, r, x);
  }
  return -1;
}
 
 
int main(int argc, _TCHAR* argv[])
{
  int arr[] = {1, 3, 6, 7, 9, 11, 14, 33, 36};
  int n = sizeof(arr)/ sizeof(arr[0]);
  int x = 14;
  int ret = ExponentialSearch(arr, n, x);
  if (ret == -1)
    std::cout << "Khong tim dc";
  else
     std::cout << "Gia tri can tim tai vi tri: " << ret;
  _getch();
    return 0;
}

+ Phù hợp cho việc tìm kiếm các mảng có số lượng phần tử lớn, hoặc phần từ tìm kiếm nằm gần đầu danh sách, (Nhanh tìm ra tập còn chứa giá trị tìm kiếm).

3. Bài Tập Về Thuật Toán Tìm Kiếm Trong C++

Sau đây là các bước triển khai thuật toán, các bước thực hiện đều được comment ở từng đoạn.

#include <bits/stdc++.h>
using namespace std;
 
//Hàm tìm kiếm nhi phân
int binarySearch(int arr[], int left, int right, int x) {
    int middle;
 
    while(left <= right) {
        // Lấy vị trí ở giữa left và right
        middle = (left + right) / 2;
 
        // Nếu phần từ ở giữa bằng x thì trả về
        // vị trí
        if (arr[middle] == x)
            return middle;
 
        // Nếu x lớn hơn phần tử ở giữa thì
        // chắc chắn nó nằm bên phải.
        // Chỉ định left phần từ ở giữa + 1
        if (x > arr[middle])
            left = middle + 1;
        else
            //Ngược lại
            right = middle - 1;
    }
 
    //Trả về -1 nếu không tìm thấy gía trị trong mảng.
    return -1;
}
int main() {
    int arr[] = {15, 20, 25, 30, 31, 44, 66};
 
    //Lấy ra độ dài của mảng
    int n = sizeof(arr) / sizeof(arr[0]);
    //Phần từ cần tìm
    int x = 25;
     
    // n -1 là vị trí cuối cùng trong mảng.
    int result = binarySearch(arr, 0, n-1, x);
 
    cout << result;
}

Khởi chạy chươn trình chúng ta sẽ nhận được kết quả là vị trí của 25 trong mảng.

Bài Tập Về Thuật Toán Tìm Kiếm Trong C++

The post Các Thuật Toán Tìm Kiếm Trong C++ first appeared on Techacademy.

source https://techacademy.edu.vn/cac-thuat-toan-tim-kiem-trong-c/

Thuật Toán Sắp Xếp Trong C++

Sắp xếp là 1 định nghĩa cơ bản nhưng khá quan trọng đối với mỗi lập trình viên. Việc sắp xếp sẽ giúp chúng ta dễ dàng hơn trong việc giải quyết những vấn đề khác như tìm kiếm một phần tử, tìm phần tử lớn nhất, nhỏ nhất,…Trong bài viết này, hãy cùng Techacademy đi tìm hiểu kĩ hơn về thuật toán sắp xếp trong C++ nhé!

1. Sắp Xếp Mảng 1 Chiều Tăng Dần Trong C++

Cách sắp xếp mảng một chiều theo thứ tự tăng dần trong C / C++. Cách sắp xếp dãy số thực char, mảng số nguyên n nhập vào từ bàn phím.

Nếu bạn đang tìm cách sắp xếp các kí tự kiểu char, bạn cũng có thể sử dụng các này nhé!

Ở đây mình sẽ viết thành hàm cho dễ sử dụng nhé. hàm swap do mình viết ra có tác dụng đổi chỗ hai phần tử cho nhau.

// Ham doi vi tri hai phan tu
void swap(int &a, int &b){
    int temp =a;
    a=b;
    b=temp;
}
// Ham sap xep tang
void sortArrTang(int a[], int n){
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++){
            if(a[i]>a[j]){
                swap(a[i], a[j]);
            }
        }
}

Giải thích: Nếu cần sắp xếp mảng có n phần tử. Ta chỉ cần thực hiện n-1 lần chọn, bởi vì phần tử cuối cùng đã tự đúng vị trí nên trong vòng lặp for đầu tiên i<n-1.

Trong vòng lặp thứ 2: Ta sẽ chạy từ vị trí j = i+1 đến cuối mảng, tức là từ sau i đến hết mảng. Nếu có phần từ nào nhỏ hơn a[i] thì ta đổi chỗ. Như vậy sau vòng lặp đầu tiên ta sẽ tìm được phần từ nhỏ nhất của mảng. Cứ như vậy

2. Sắp Xếp Giảm Dần Trong C++

Để sắp xếp phần tử trong mảng C++ theo thứ tự giảm dần dần bằng hàm qsort, chúng ta đơn giản chỉ cần thay đổi hàm so sánh như dưới đây là xong:

int compareIntDesc(const void* a, const void* b){
    int aNum = *(int*)a;
    int bNum = *(int*)b;

    return bNum - aNum;
}

Sự khác biệt giữa 2 hàm so sánh này là ở giá trị mà nó trả về. Với hàm compareIntAsc() ở sắp xếp tăng dần thì chúng ta trả về return aNum – bNum, và với hàm compareIntDesc() ở sắp xếp giảm dần thì chúng ta trả về giá trị ngược lại là return bNum – aNum.

Và chúng ta sử dụng hàm qsort để viết chương trình sắp xếp phần tử trong mảng C++ theo thứ tự giảm dần như sau:

#include <iostream>
#include <cstdlib>
using namespace std;

/*Định nghĩa macro SIZE_OF_ARRAY để lấy độ dài (số phần tử) trong mảng chỉ định*/
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

/*Tạo hàm in phần tử trong mảng*/
void show_array(int array[], int length){
    for(short i = 0; i < length; i++)  cout << array[i] <<' ';   
    cout << endl;
}

/*Tạo hàm so sánh giảm dần sử dụng trong hàm qsort*/
int compareIntDesc(const void* a, const void* b){
    int aNum = *(int*)a;
    int bNum = *(int*)b;

    return bNum - aNum;
}

int main(){
    int array1[] = {5, 4, 7, 2, 8, 7, 3};
    int array2[] = {99, 4, 5, 2, 80, 7, 3};

    /*Sử dụng hàm qsort để sắp xếp mảng giảm dần*/
    qsort(array1, SIZE_OF_ARRAY(array1), sizeof(int), compareIntDesc);
    qsort(array2, SIZE_OF_ARRAY(array2), sizeof(int), compareIntDesc);

    /*Xem kết quả sắp xếp mảng*/
    show_array(array1, SIZE_OF_ARRAY(array1));
    show_array(array2, SIZE_OF_ARRAY(array2));

    return 0;
}

Kết quả của phép sắp xếp mảng giảm dần trong C++ như dưới đây. Bạn hãy thử chạy chương trình và kiểm tra nhé.

8 7 7 5 4 3 2 
99 80 7 5 4 3 2

3. Sắp Xếp Chuỗi Tăng Dần Trong C++

Trong bài tập này chúng ta sẽ thực hiện chương trình C++ để sắp xếp các số trong mảng theo thứ tự tăng dần, đây là 1 bài tập căn bản thường gặp trong khi học ngôn ngữ C++.

Chương trình sau đây người dùng sẽ nhập vào n số, sau khi người dùng nhập xong các số đó, chương trình này sẽ sắp xếp và hiển thị chúng theo thứ tự tăng dần.

Ở đây mình đã tạo ra một hàm do người dùng định nghĩa sort_numbers_asceinating() cho mục đích sắp xếp.

Sau khi chúng ta tạo một hàm sắp xếp sort_numbers_asceinating() để thực hiện công việc sắp xếp theo thứ tự tăng dần thì chúng ta gọi nó ở hàm main() để sử dụng và hiển thị kết quả ra màn hình bằng câu lệnh cout, cin

#include <iostream>
using namespace std;
void sort_numbers_ascending(int number[], int count)
{
   int temp, i, j, k;
   for (j = 0; j < count; ++j)
   {
      for (k = j + 1; k < count; ++k)
      {
         if (number[j] > number[k])
         {
            temp = number[j];
            number[j] = number[k];
            number[k] = temp;
         }
      }
   }
   cout<<"Các số sau khi được sắp xếp tăng dần:\n";
   for (i = 0; i < count; ++i)
      cout<<"\n"<< number[i];
}
int main()
{
   int i, count, number[20];
  
   cout<<"Nhập số lương phần tử trong mảng:";
   cin>>count;
   cout<<"\nNhập giá trị cho từng phần tử trong mảng:\n";
    
   for (i = 0; i < count; ++i)
      cin>>number[i];
  
   sort_numbers_ascending(number, count);
}

Kết quả:

4. Hàm Sắp Xếp Trong C++

+ Bài toán sắp xếp

Thuật toán sắp xếp là lời giải của bài toán sắp xếp, vậy thì trước tiên, ta hãy tìm hiểu xem bài toán sắp xếp là gì trước đã.

Bài toán sắp xếp chắc chắn không còn xa lạ gì với mỗi chúng ta, nó là 1 trong những bài toán được bắt gặp phổ biến nhất trong thực tế. Ví dụ như sắp xếp danh sách lớp học, sắp xếp quyển sách, sắp xếp tiền… Vậy thì bài toán sắp xếp là gì?

Bài toán sắp xếp là chúng ta sẽ sắp xếp lại các phần tử của một danh sách theo chiều tăng hoặc giảm dần theo một tiêu chí nào đó của phần tử trong danh sách.

Ví dụ như bạn sắp xếp danh sách lớp học theo điểm trung bình từ cao đến thấp, sắp những quyển sách theo kích cỡ từ nhỏ đến lớn, sắp xếp những tờ tiền theo mệnh giá từ thấp đến cao…

Mục đích của việc sắp xếp chính là giúp ta có cái nhìn tổng quan hơn về những dữ liệu mà ta có, dễ dàng tìm kiếm những phần tử đứng nhất về một tiêu chí nào đó như mình đã nói trong Thuật toán kiếm tìm trong C++, hầu như đa số bài toán đều quy về bài toán tìm kiếm. Ví dụ:

Bạn có một danh sách lớp học chưa được sắp xếp, bạn muốn biết được là mức độ đề thi có khó đối với học sinh hay không, top 3 học sinh có điểm trung bình cao nhất. Vậy thì sau khi bạn thực hiện việc sắp xếp giảm theo điểm trung bình, bạn sẽ dễ dàng kiểm tra được mức độ của đề đối với học sinh là dễ hay khó thông qua việc nhìn vào đầu và cuối danh sách, đầu danh sách điểm không cao lắm và cuối danh sách điểm thấp thì chắc chắn đề này khó đối với học sinh và ngược lại.

Trong lập trình, sắp xếp không chỉ đơn giản là để tìm một hoặc nhiều phần tử đứng đầu về một tiêu chí nào đó hay để có cái nhìn tổng quan về dữ liệu, sắp xếp còn làm cơ sở cho các giải thuật nâng cao với hiệu suất cao hơn.

Ví dụ như khi thực hiện tìm kiếm, thuật toán tìm kiếm nhị phân có độ phức tạp thời gian là O(log(n)) và ổn định, nhưng thuật toán này chỉ áp dụng được với dãy đã được sắp xếp. Vậy khi này, bạn có thể thực hiện sắp xếp trước sau đó áp dụng thuật toán tìm kiếm nhị phân.

Bài toán sắp xếp chỉ đơn giản có vậy, bây giờ mình sẽ giới thiệu đến các bạn một số giải thuật tìm kiếm phổ biến nhất mà lập trình viên nào cũng nên biết. Hãy cùng bắt đầu thôi!

Lưu ý trước khi đọc bài: bạn cần có kỹ năng lập trình C++ cơ bản, hiểu về độ phức tạp của thuật toán. Trong bài viết có sử dụng từ thuật toán sắp xếp ổn định, thuật toán sắp xếp ổn định nghĩa là thứ tự của các phần tử có cùng giá trị sẽ không thay đổi so với ban đầu. Ví dụ như 1 5 3 3 4, sau khi sắp xếp cũng là 1 3 3 4 5.

+ Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp nổi bọt hay bubble sort là thuật toán sắp xếp đầu tiên mà mình giới thiệu đến các bạn và cũng là thuật toán đơn giản nhất trong các thuật toán mà mình sẽ giới thiệu, ý tưởng của thuật toán này như sau:

Duyệt qua danh sách, làm cho các phần tử lớn nhất hoặc nhỏ nhất dịch chuyển về phía cuối danh sách, tiếp tục lại làm phần tử lớn nhất hoặc nhỏ nhất kế đó dịch chuyển về cuối hay chính là làm cho phần tử nhỏ nhất (hoặc lớn nhất) nổi lên, cứ như vậy cho đến hết danh sách Cụ thể các bước thực hiện của giải thuật này như sau:

Gán i = 0
Gán j = 0
Nếu A[j] > A[j + 1] thì đối chỗ A[j] và A[j + 1]
Nếu j < n – i – 1:
- Đúng thì j = j + 1 và quay lại bước 3
- Sai thì sang bước 5
Nếu i < n – 1:
- Đúng thì i = i + 1 và quay lại bước 2
- Sai thì dừng lại

Thật đơn giản đúng không nào, chúng ta hãy cùng cài đặt thuật toán này trong C++ nha.

+ Sắp xếp chọn (Selection Sort)

Sắp xếp chọn hay selection sort sẽ là thuật toán thứ hai mà mình giới thiệu đến các bạn, ý tưởng của thuật toán này như sau: duyệt từ đầu đến phần tử kề cuối danh sách, duyệt tìm phần tử nhỏ nhất từ vị trí kế phần tử đang duyệt đến hết, sau đó đổi vị trí của phần tử nhỏ nhất đó với phần tử đang duyệt và cứ tiếp tục như vậy.

Cho mảng A có n phần tử chưa được sắp xếp. Cụ thể các bước của giải thuật này áp dụng trên mảng A như sau:

Gán i = 0
Gán j = i + 1 và min = A[i]
Nếu j < n:
- Nếu A[j] < A[min] thì min = j
- j = j + 1
- Quay lại bước 3
Đổi chỗ A[min] và A[i]
Nếu i < n – 1:
- Đúng thì i = i + 1 và quay lại bước 2
- Sai thì dừng lại

Đối với thuật toán sắp xếp chọn, do sử dụng 2 vòng lặp lồng vào nhau, độ phức tạp thời gian trung bình của thuật toán này là O(n2). Thuật toán sắp xếp chọn mình cài đặt là thuật toán sắp xếp không ổn định, nó còn có một phiên bản khác cải tiến là thuật toán sắp xếp chọn ổn định.

+ Sắp xếp chèn (Insertion Sort)

Sắp xếp chèn hay insertion sort là thuật toán tiếp theo mà mình giới thiệu, ý tưởng của thuật toán này như sau: ta có mảng ban đầu gồm phần tử A[0] xem như đã sắp xếp, ta sẽ duyệt từ phần tử 1 đến n – 1, tìm cách chèn những phần tử đó vào vị trí thích hợp trong mảng ban đầu đã được sắp xếp.

Giả sử cho mảng A có n phần tử chưa được sắp xếp. Các bước thực hiện của thuật toán áp dụng trên mảng A như sau:

Gán i = 1
Gán x = A[i] và pos = i – 1
Nếu pos >= 0 và A[pos] > x:
- A[pos + 1] = A[pos]
- pos = pos – 1
- Quay lại bước 3
A[pos + 1] = x
Nếu i < n:
- Đúng thì i = i + 1 và quay lại bước 2
- Sai thì dừng lại

+ Sắp xếp trộn (Merge Sort)

Sắp xếp trộn (merge sort) là một thuật toán dựa trên kỹ thuật chia để trị, ý tưởng của thuật toán này như sau: chia đôi mảng thành hai mảng con, sắp xếp hai mảng con đó và trộn lại theo đúng thứ tự, mảng con được sắp xếp bằng cách tương tự.

Giả sử left là vị trí đầu và right là cuối mảng đang xét, cụ thể các bước của thuật toán như sau:

Nếu mảng còn có thể chia đôi được (tức left < right)
1. Tìm vị trí chính giữa mảng
2. Sắp xếp mảng thứ nhất (từ vị trí left đến mid)
3. Sắp xếp mảng thứ 2 (từ vị trí mid + 1 đến right)
4. Trộn hai mảng đã sắp xếp với nhau

+ Sắp xếp nhanh (Quick Sort)

Sắp xếp nhanh (quick sort) hay sắp xếp phân đoạn (Partition) là là thuật toán sắp xếp dựa trên kỹ thuật chia để trị, cụ thể ý tưởng là: chọn một điểm làm chốt (gọi là pivot), sắp xếp mọi phần tử bên trái chốt đều nhỏ hơn chốt và mọi phần tử bên phải đều lớn hơn chốt, sau khi xong ta được 2 dãy con bên trái và bên phải, áp dụng tương tự cách sắp xếp này cho 2 dãy con vừa tìm được cho đến khi dãy con chỉ còn 1 phần tử.

Cụ thể áp dụng thuật toán cho mảng như sau:

Chọn một phần tử làm chốt
Sắp xếp phần tử bên trái nhỏ hơn chốt
Sắp xếp phần tử bên phải nhỏ hơn chốt
Sắp xếp hai mảng con bên trái và bên phải pivot

Phần tử được chọn làm chốt rất quan trọng, nó quyết định thời gian thực thi của thuật toán. Phần tử được chọn làm chốt tối ưu nhất là phần tử trung vị, phần tử này làm cho số phần tử nhỏ hơn trong dãy bằng hoặc sấp xỉ số phần tử lớn hơn trong dãy. Tuy nhiên, việc tìm phần tử này rất tốn kém, phải có thuật toán tìm riêng, từ đó làm giảm hiệu suất của thuật toán tìm kiếm nhanh, do đó, để đơn giản, người ta thường sử dụng phần tử chính giữa làm chốt.

5. Sắp Xếp Mảng 2 Chiều Tăng Dần Trong C++

Bắt đầu ở đây, để cho ngắn gọn bài viết. Mình sẽ chỉ đưa ra hàm con giải quyết phần đề bài của bài tập mảng 2 chiều tương ứng. Các bạn sẽ tự thêm nó vào hàm main nhé.

BT1. Viết hàm tính tổng các số chẵn trong ma trận

 
int TongCacSoChan(int a[][100], int m, int n)
{
   int sum = 0;
   for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
         if(a[i][j]%2==0)
            sum += a[i][j];
   return sum;
}

BT2. Viết hàm liệt kê các số nguyên tố trong ma trận, đếm các số nguyên tố có trong ma trận

 
bool SoNguyenTo(int soA)
{
    if (soA < 2)
    {
        return false;
    }
    else
    {
        for (int i = 2; i <= sqrt((float)soA); i ++)
        {
            if (soA%i==0)
            {
                return false;
            }
        }
    }
    return true;
}
 
int DemSoLuongSNT(int a[][100], int m, int n)
{
   int dem = 0;
   for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
         if(SoNguyenTo(a[i][j])) dem++;
   return dem;
}
 
void LietKeSNT(int a[][100], int m, int n)
{
   int dem = 0;
   for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
         if(SoNguyenTo(a[i][j])) printf("%d\t", a[i][j]);
}

BT3. Viết hàm xóa một dòng của ma trận. Viết hàm xóa một cột của ma trận

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void XoaDong(int a[][100], int &m, int n, int r)
{
   for(int i=r;i<m-1;i++)
      for(int j=0;j<n;j++)
         a[i][j]=a[i+1][j];
   m--;
}
 
void XoaCot(int a[][100], int m, int &n, int c)
{
   for(int i=0;i<m;i++)
      for(int j=c;j<n-1;j++)
         a[i][j]=a[i][j+1];
   n--;
}

BT4. Viết hàm đổi chỗ 2 hàng của 1 ma trận. Viết hàm đổi chỗ 2 cột của ma trận.

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
void swap(int &a, int &b)
{
   int temp = a;
   a = b;
   b = temp;
}
 
void DoiCho2Hang(int a[][100], int m, int n, int row1, int row2)
{
   if((row1>=0 && row1<m)&&(row2>=0 && row2<m))
      for(int j=0;j<n;j++)
         swap(a[row1][j],a[row2][j]);
}
 
void DoiChoHaiCot(int a[][100], int m, int n, int column1, int column2)
{
   if((column1>=0 && column1<n)&&(column2>=0 && column2<n))
      for(int i=0;i<m;i++)
         swap(a[i][column1],a[i][column2]);
}

BT5. Viết hàm tìm giá trị lớn nhất/ nhỏ nhất trên đường chéo chính của ma trận.

 
//Tìm max
int Max(int a[][100], int n)
{
   int max = a[0][0];
   for(int i = 1; i < n; i++)
      if(a[i][i] > max)
         max = a[i][i];
   return max;
}
 
//Tìm min
int Min(int a[][100], int n)
{
   int min = a[0][0];
   for(int i = 1; i < n; i++)
      if(a[i][i] < min)
         min = a[i][i];
   return min;
}

6. Các Thuật Toán Sắp Xếp Trong C++

Sắp xếp là quá trình bố trí lại các phần tử trong một tập hợp theo một trình tự nào đó nhằm mục đích giúp quản lý và tìm kiếm các phần tử dễ dàng và nhanh chóng hơn.

Tại sao phải sắp xếp?

Để có thể sử dụng thuật toán tìm nhị phân
Để thực hiện thao tác nào đó được nhanh hơn

Các phương pháp sắp xếp thông dụng:

Phương pháp Đổi chỗ trực tiếp (Interchange sort)
Phương pháp Nổi bọt (Bubble sort)
Phương pháp Chèn trực tiếp (Insertion sort)
Phương pháp Chọn trực tiếp (Selection sort)

Interchange Sort

Khái niệm nghịch thế:

Xét một mảng các số a[0], a[1], … a[n-1]
Nếu có i<j và a[i] > a[j], thì ta gọi đó là một nghịch thế

Mảng chưa sắp xếp sẽ có nghịch thế

Mảng đã có thứ tự sẽ không chứa nghịch thế

a[0] <= a[1] <=… <=[n -1]

Nhận xét:

Để sắp xếp một dãy số, ta có thể xét các nghịch thế có trong dãy và làm triệt tiêu dần chúng đi

Ý tưởng:

Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế
Lặp lại xử lý trên với các phần tử tiếp theo trong dãy

void Swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void InterchangeSort(int a[], int n){	
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
           if(a[i] > a[j])  //nếu có nghịch thế thì đổi chỗ
              Swap(a[i], a[j]);
}

Đánh giá:

Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu
Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh

Bubble Sort

Ý tưởng:

Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo
Ở lần xử lý thứ i có vị trí đầu dãy là i
Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét

void BubbleSort(int a[], int n){	
   for (int i = 0; i < n - 1; i++)
      for (int j = n - 1; j > i; j--)
         if(a[j] < a[j-1])
             Swap(a[j], a[j-1]);
}

Đánh giá:

Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu
Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh

Khuyết điểm:

Không nhận diện được tình trạng dãy đã có thứ tự hay có thứ tự từng phần
Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm\

Insertion Sort

Nhận xét:

Mọi dãy a[0] , a[1] ,…, a[n-1] luôn có i-1 phần tử đầu tiên a[0] , a[1] ,… , a[i-2] đã có thứ tự (i ≥ 2)

Ý tưởng chính:

Tìm cách chèn phần tử a[i] vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a[0] , a[1] ,… , a[i-1] trở nên có thứ tự
Vị trí này chính là pos thỏa : a[pos-1] <= a[i ]< a[pos] (1 <= pos <= i)

void InsertionSort(int a[], int n){	
   int pos, x;
   for(int i = 1; i < n; i++){ //đoạn a[0] đã sắp
      x = a[i]; 
      pos = i;
      while(pos > 0 && x < a[pos-1]){
         a[pos] = a[pos-1];	// dời chỗ
         pos--;
      }
      a[pos] = x;
   }
}

Đánh giá:

Giải thuật thực hiện tất cả N-1 vòng lặp tìm pos, do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau:

Selection Sort

Nhận xét:

Mảng có thứ tự thì a[i] = min(a[i], a[i+1], …, a[n-1])

Ý tưởng: mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế:

Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành
Xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành… đến khi dãy hiện hành chỉ còn 1 phần tử

void SelectionSort(int a[], int n)
{
   int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
   for (int  i = 0; i < n - 1; i++){
      min = i; 
      for(int j = i + 1; j < n; j++)
      	   if (a[j] < a[min])
             min = j; // ghi nhận vị trí phần tử nhỏ nhất
      if (min != i)
      	   Swap(a[min], a[i]);
   }
}

Đánh giá:

Ở lượt thứ i, cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành
Số lượng phép so sánh không phụ thuộc vào tình trạng của dãy số ban đầu

Trong mọi trường hợp, số lần so sánh là:

7. Sắp Xếp Quicksort Trong C

Trong bài này mình sẽ giới thiệu thuật toán Quick Sort (sắp xếp nhanh), đây là thuật toán sắp xếp được xem là nhanh nhất. Chúng ta sẽ cùng nhau tìm hiểu về sắp xếp nhanh là gì? Cũng như cách thức nó hoạt động và triển khai trong C++ như thế nào.

Giải thích thuật toán

Trong phần này chúng ta có hai giai đoạn. Giai đoạn một là giai đoạn phân đoạn mảng (partition()) và giai đoạn hai là giai đoạn sắp xếp (quickSort()).

Chọn pivot cho mảng, ở đây mình sẽ chọn pivot là số cuối cùng của mảng.
Tạo hai biến là left và right để trỏ tới bên trái và bên phải của danh sách.
Thực hiện so sánh các phần tử với pivot. Nếu phần tử nhỏ hơn pivot thì dịch chuyển qua bên trái và ngược lại.
Sau khi dịch chuyển thực hiện công việc sắp xếp các phần tử trong mảng con mới, trước khi tiếp tục phân đoạn tiếp theo.

Thuật toán Quick Sort trong C++

Ở phần trên mình đã nêu ra các bước viết thuật toán. Để chi tiết hơn mình đã có chú thích rõ ràng, cụ thể trong từng dòng code trong thuật toán dưới đây. Các bạn hãy đọc thật kỹ nhé:

Hàm partition()

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // khai báo phần tử đánh dâu pivot
    int left = low;   //khai báo biến bên trái
    int right = high - 1; //khai báo biến bên phải
    while(true){
        while(left <= right && arr[left] < pivot) left++; // tìm phần tử >= phần tử pivot trong mảng
        while(right >= left && arr[right] > pivot) right--; // tìm phần tử <= phần tử pivot trong mảng
        if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp
        swap(arr[left], arr[right]); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi.
        left++; // Vì left hiện tại đã xét, nên cần tăng
        right--; // Vì right hiện tại đã xét, nên cần giảm
    }
    swap(arr[left], arr[high]);
    return left; // Trả về chỉ số sẽ dùng để chia đôi mảng
}

Hàm quicksort()

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* index là chỉ số nơi phần tử này đã đứng đúng vị trí
         và đây là phần tử chia mảng làm 2 mảng con trái & phải */
        int index = partition(arr, low, high);
  
        // Gọi đệ quy sắp xếp 2 mảng con trái và phải
        quickSort(arr, low, index - 1);
        quickSort(arr, index + 1, high);
    }
}

Hàm swap()

void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

8. Hàm Sắp Xếp Nổi Bọt Trong C++

Ý tưởng của sắp xếp nổi bọt

Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự(số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy số được sắp xếp.

Ví dụ minh họa

Giả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] này tăng dần.
Lần lặp đầu tiên:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Ở đây, thuật toán sẽ so sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Đổi chỗ do 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Đổi chỗ do 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ.

Lần lặp thứ 2:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Đổi chỗ do 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.

Lần lặp thứ 3:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Code sắp xếp nổi bọt trong C/C++

 
// Code from https://nguyenvanhieu.vn
 
#include <stdio.h>
 
void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}
 
// Hàm sắp xếp bubble sort
void bubbleSort(int arr[], int n)
{
    int i, j;
    bool haveSwap = false;
    for (i = 0; i < n-1; i++){
    // i phần tử cuối cùng đã được sắp xếp
        haveSwap = false;
        for (j = 0; j < n-i-1; j++){
            if (arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
                haveSwap = true; // Kiểm tra lần lặp này có swap không
            }
        }
        // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm
        if(haveSwap == false){
            break;
        }
    }
}
 
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("n");
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: n");
    printArray(arr, n);
    return 0;
}

Ở đây, trong hàm bubbleSort tôi sử dụng thêm một biến haveSwap để kiểm tra tại lần lặp hiện hành có xảy ra việc đổi chỗ hai số không. Nếu không, ta có thể kết luận mảng đã sắp xếp mà không cần phải thêm một lần lặp nữa.

Kiểm tra kết quả:

 
Sorted array:
11 12 22 25 34 64 90

Đánh giá thuật toán sắp xếp nổi bọt

Độ phức tạp thuật toán

Trường hợp tốt: O(n)
Trung bình: O(n^2)
Trường hợp xấu: O(n^2)

Không gian bộ nhớ sử dụng: O(1)

9. Sắp Xếp Chèn Trong C++

+ Ý tưởng thuật toán sắp xếp chèn trực tiếp

Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1.

Giả sử đoạn a[0] trong danh sách đã được sắp xếp. Bắt đầu từ phần tử thứ i=1, tức là a1. Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp xếp để có dãy mới a0,…,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 < ai < ak (0<= k <=i). Lưu ý, khi k=0 thì có nghĩa là ai cần chèn vào trước vị trí đầu tiên trong danh sách.

Lặp lại quá trình trên ở mỗi lần lặp với mỗi lần lặp thì tăng i lên 1 đến khi i<n thì dừng quá trình lặp.

Một câu hỏi đặt ra là cách chèn phần tử trong danh sách như thế nào? Các bạn hãy đọc tiếp phần 2 và 3 nhé.

+ Các bước thực hiện thuật toán

Bước 1: i = 1;//giả sử có đoạn a[0] đã được sắp xếp

Bước 2: x = a[i];

Bước 3:

Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i-1] để chèn a[i] vào danh sách.

Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i].

Bước 4: a[pos] = x;//chèn x, có đoạn a[0],…,a[i] đã được sắp.

Bước 5: i = i+1; nếu i < n -> lặp lại bước 2, ngược lại -> Dừng.

+ Cài đặt thuật toán sắp xếp chèn trực tiếp với C++

void Insertion_Sort(int a[], int n){
   int pos, i;
   int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
   for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp
      x = a[i]; pos = i-1;
      //tìm vị trí chèn x
      while((pos>=0)&&(a[pos]>x)){
                //kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới
         a[pos+1] = a[pos];
         pos--;
      }
      a[pos+1] = x;//chèn x vào danh sách
   }
}
void main()
{
   int a[5] = {8, 4, 1, 6, 5};
   Insertion_Sort(a, 5);
   cout<<"Mang sau khi sap xep:"<<endl;
   for(int i=0;i<5;i++){
      cout<<a[i]<<" ";
   }
   system("pause");
}

Kết quả

Mang sau khi sap xep:
1 4 5 6 8

Đánh giá thuật toán

Trường hợp	Số lần so sánh
Tốt nhất	n-1
Xấu nhất	n(n-1)/2

Độ phức tạp thuật toán trong trường hợp xấu nhất là O(n2).

The post Thuật Toán Sắp Xếp Trong C++ first appeared on Techacademy.

source https://techacademy.edu.vn/thuat-toan-sap-xep-trong-c/

Kiểm Tra Số Nguyên Tố Trong C++

Hướng dẫn phương pháp kiểm tra số nguyên tố trong C++. Bạn sẽ học được cách tạo hàm kiểm tra số nguyên tố trong C++ cũng như cách liệt kê tất cả các số nguyên tố nhỏ hơn n bằng C++ sau bài học này.

1. Số Nguyên Tố Là Gì?

Chúng ta đều biết số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai ước số là 1 và chính nó.

Ví dụ, chúng ta xem xét các số 2, 3, 6 như sau:

Số 2 chỉ có đúng hai ước số là 1 và chính nó nên là số nguyên tố
Số 3 chỉ có đúng hai ước số là 1 và chính nó nên là số nguyên tố
Số 6 có 4 ước số là 1, 2 , 3 và 6, do đó nó không phải là số nguyên tố.

2. Kiểm Tra Số Nguyên Tố Trong C Dùng While

+ Cấu trúc vòng lặp do while

Cấu trúc vòng lặp do-while là: do { <khối lệnh> } while (<điều kiện>)

Vậy nên khi bạn chuyển từ vòng lặp for sang vòng lặp do while thì chỉ cần thay thế:

Khối lệnh trong do là những gì thực hiện trong vòng lặp for:

if(n%i==0) demuoc++; i++;

Và đừng quên theo sau nó vẫn còn biến i++ nữa nhé, mỗi lần lặp nó sẽ tăng lên 1 đơn vị.

Điều kiện trong while là: điều kiện trong for: i<=n

+ CODE SỐ NGUYÊN TỐ DO WHILE TRONG C++

#include <iostream>
using namespace std;
int main()
{
    int i=1,n,demuoc=0;  
    cout<<"nhap n = ";cin>>n;  
    do
    {
        if(n%i==0)  demuoc++; i++;
     }
    while (i<=n);     
    if (demuoc==2) cout<<"la so nguyen to";  
    else cout<<"khong la so nguyen to";
}

Kết quả khi chạy chương trình:

nhap n = 11
la so nguyen to
Dãy số nguyên tố <100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Kiểm Tra Số Nguyên Tố Trong C Dùng While

3. Dùng Đệ Quy Kiểm Tra Số Nguyên Tố

Dưới đây là một chương trình minh họa sử dụng đệ quy trong C. Bạn chú ý, trong thân hàm recurse() có lời gọi hàm tới chính nó => đó là hàm đệ quy.

 
void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}
 
int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

Vậy 1 chương trình sẽ chạy như thế nào nếu có hàm đệ quy? Bạn hãy xem hình ảnh dưới đây:

Như các bạn có thể thấy, khi một hàm đệ quy được gọi (ở ví dụ trên là hàm main gọi) thì thay vì hàm đó chỉ được thực thi 1 lần thì ở đây bản thân hàm gọi lại chính nó => Nó có thể tự chạy lại chính mình số lần bất kỳ.

The post Kiểm Tra Số Nguyên Tố Trong C++ first appeared on Techacademy.

source https://techacademy.edu.vn/kiem-tra-so-nguyen-to-trong-c-2/

String Trong C++

Cùng tìm hiểu về kiểu dữ liệu string trong C++. Bạn sẽ biết khái niệm string là gì trong C++, cách khai báo string trong C++, cách khởi tạo string trong C++, cách gán string trong C++ cũng như cách truy xuất ký tự của string. Bạn cũng sẽ biết sự khác biệt giữa mảng ký tự và string trong C++ sau bài học này.

I. String Trong C++ Là Gì

Trong ngôn ngữ C++, có một kiểu dữ liệu gọi là kiểu char (kiểu ký tự) ( char là viết tắt của character). Đây là kiểu dữ liệu có kích thước bộ nhớ là 1 byte. Vì 1 byte là đơn vị nhỏ nhất nên có thể nói char là loại có kích thước bộ nhớ nhỏ nhất.

Khi chúng ta nối những ký tự (char) trong C++ lại với nhau thì sẽ được 1 chuỗi ký tự. Ví dụ như “Hello” là 1 chuỗi ký tự được tạo bởi các ký tự đơn chẳng hạn.

Và chúng ta gọi loại dữ liệu được tạo thành bởi tập hợp những ký tự đơn như vậy là kiểu dữ liệu string trong C++ hay còn gọi là chuỗi string trong C++.

Để xử lý chuỗi string trong C++, chúng ta có thể dùng đến mảng ký tự được kế thừa từ ngôn ngữ C, hoặc là sử dụng tới std::string là một trình bao bọc để xử lý chuỗi thuận tiện mới được thêm vào C++. Về phương pháp sử dụng string trong c++ bằng mảng ký tự thì Kiyoshi đã phân tích rất kỹ trong loạt bài tại chuyên đề Chuỗi trong C rồi.

II. Nhập String Trong C++

Hướng dẫn cách nhập xuất string trong C++. Bạn sẽ học được cách sử dụng lệnh cin, cout cũng như hàm getline() để nhập xuất string trong C++ sau bài học này.

Nhập xuất string trong C++*

Giống như việc nhập các loại dữ liệu khác, chúng ta sử dụng lệnh cin để nhập vào một string trong C++ với cú pháp sau đây:

string str;
cin >> str

Trong đó dòng đầu tiên dùng để khai báo biến str có kiểu string, và dòng thứ 2 dùng để gán dữ liệu nhập từ bàn phím vào biến str.

Tương tự, chúng ta sử dụng lệnh cout để xuất vào một string trong C++ với cú pháp sau đây:

cout >> str

Ví dụ, chúng ta viết chương trình nhập xuất string trong C++ như sau:

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    cout << "Nhap chuoi ky tu: ";
 
    string str;
    cin >>   str;
 
    cout <<"Chuoi ky tu vua nhap: "<< str;
 
    return 0;
}

Khi đó màn hình nhập dữ liệu sẽ như sau:

Nhap chuoi ky tu: abcdd
Chuoi ky tu vua nhap: abcdd

Nhập nhiều string trong C++

Để nhập nhiều string trong C++ cách nhau bởi dấu cách, chúng ta viết các string nhập vào cách nhau bởi toán tử >>, khi dùng lệnh cin với cú pháp sau đây:

string str1, str1, str3;
cin >> str1 >> str2 >>str3 ;

Ví dụ, chúng ta viết chương trình nhập nhiều string trong C++ như sau:

#include <iostream>
#include <cstring>
using namespace std;
 
int main(){
    cout << "Nhap cac chuoi: ";
    string str1, str2, str3;
    cin >> str1 >> str2 >>str3 ;
    cout <<"Cac chuoi vua nhap: "<<str1<<' '<<str2<<' ' <<str3;
}

Khi đó màn hình nhập dữ liệu sẽ hiện ra. Chúng ta nhập từng string cách nhau bởi dấu cách từ bàn phím như sau:

Nhap cac chuoi: ab cd123 ef8
Cac chuoi vua nhap: ab cd123 ef8

III. Các Hàm String Trong C++

Thư viện <string> rất nhiều hàm cho phép xử lý chuỗi. Ví dụ: tìm chiều dài chuỗi, so sánh hai chuỗi, tìm kiếm/rút trích chuỗi con, nối chuỗi,…

Hàm s.length()

Trả về số lượng ký tự trong string s.

string s1 = "introduction to programming";
cout<<"length of s1 = "<<s1.length();//27

Hàm s.substr(x, y)

Rút trích một chuỗi con với chiều dài y bắt đầu tại vị trí x. Nếu không có y, một chuỗi con từ vị trí x tới cuối chuỗi sẽ được rút trích.

string s1 = "introduction to programming";
cout<<"substring has 10 characters of s1 start at 5:"<<s1.substr(5, 10);
//Kết quả: substring has 10 characters of s1 start at 5:duction to

Hàm s.find(r)

Kiểm tra chuỗi string r có xuất hiện trong chuỗi s hay không. Nếu có thì trả về vị trí bắt đầu xuất hiện chuỗi r trong chuỗi s.

string s1 = "introduction to programming";
cout<<"position of 'duc' string in s1:"<<s1.find("duc");//5

Hàm s.erase(x, n)

Xóa n ký tự bắt đầu tại vị trí x.

string s1 = "introduction to programming";
s1.erase(5, 15);
cout<<"s1 string after erase:"<<s1;//s1 string after erase:introramming

Hàm s.replace(x, n, str)

Thay thế n ký tự tại vị trí bắt đầu là x bằng chuỗi str. Lưu ý: chiều dài của str có thể lớn hơn n.

string s1 = "introduction to programming";
s1.replace(5, 10, "123123123");
cout<<"s1 string after replace:"<<s1;//s1 string after replace:intro123123123 programming

Hàm s1.compare(s2)

So sánh chuỗi s1 với s2. Giá trị trả về là -1 nếu s1 < s2, bằng 0 nếu s1 == s2, là 1 nếu s1 > s2.

string s1 = "introduction to programming";
string s2 = "c++ programming language";
cout<<"s1 compare s2:"<<s1.compare(s2);//1

Hàm s1.swap(s2)

Hoán đổi nội dung hai chuỗi.

string s1 = "introduction to programming";
string s2 = "c++ programming language";
s1.swap(s2);
cout<<"s1 after swap:"<<s1<<endl;
cout<<"s2 after swap:"<<s2;
//Kết quả:
//s1 after swap:c++ programming language
//s2 after swap:introduction to programming

Hàm s1.insert(index, s2)

Thêm chuỗi s2 vào s1 sau vị trí index.

string s1 = "introduction to programming";
string s2 = "c++ programming language";
s1.insert(10, s2);
cout<<"s1 after insert s2:"<<s1;
//Kết quả:
//s1 after insert s2:introductic++ programming languageon to programming

IV. Tính Độ Dài String Trong C++

Hướng dẫn cách lấy độ dài string trong C++. Bạn sẽ học được cách dùng hàm size và hàm length để lấy độ dài string trong C++ sau bài học này.

Độ dài string trong C++ là gì

Độ dài string trong C++ chính là số ký tự chứa trong string đó. Độ dài string trong C++ có thể lấy được bằng cách chia kích thước của string cho kích thước 1 phần tử trong string đó.

Độ dài string (số phần tử) = [Kích thước string] / [Kích thước kiểu char]

Do phần tử tạo nên string là các ký tự thuộc dạng char với kích thước là 1 byte, nên thông thường, chúng ta coi độ dài string trong C++ chính bằng kích thước của string đó.

Lấy độ dài string trong C++ bằng hàm size và hàm length

Do thông thường độ dài string trong C++ chính bằng kích thước của string đó, nên bằng phương pháp tính ra kích thước string thì chúng ta có thể thu về ngay độ dài của string đó.

Và để tính kích thước string trong C++, chúng ta sẽ sử dụng một trong hai hàm đã học tại bài Lấy kích thước string trong C++.

Cách lấy độ dài string trong C++ như các ví dụ sau đây:

Ví dụ 1: lấy độ dài string trong C++ bằng hàm size

#include <iostream>
#include <string>
using namespace std;

int main ()
{
    string str("Hello world");
    cout<<"Do dai string = kich thuoc string = ",str.size()<<endl;

    return 0;
}//Do dai string = kich thuoc string = 11

Ví dụ 1: lấy độ dài string trong C++ bằng hàm length

#include <iostream>
#include <string>
using namespace std;

int main ()
{
    string str("Hello world");
    cout<<"Do dai string = kich thuoc string = "<<str.length()<<endl;

    return 0;
}//Do dai string = kich thuoc string = 11

Trường hợp độ dài string khác với số ký tự có trong string

Ở phần trên chúng ta đã biết với những chuỗi được tạo thành bởi các ký tự được biểu diễn bởi 1 mã ký tự, do kích thước của các ký tự như vậy cũng là 1 byte, nên kết quả tính độ dài string bằng 2 hàm size và length cũng chính là số ký tự có trong string đó.

Tuy nhiên trong trường hợp chuỗi được tạo ra bởi các ký tự được biểu diễn bởi 2 mã ký tự như là tiếng Việt có dấu, hay kanji tiếng Nhật chẳng hạn, thì độ dài string sẽ lớn hơn số ký tự có trong string. Ví dụ:

#include <iostream>
#include <string>
using namespace std;

int main ()
{
    string str("Hà Nội");
    cout<<str.size()<<endl;

    string str2("東京");
    cout<<str2.size()<<endl;
    return 0;
}

Kết quả:

9
6

Có thể thấy rõ độ dài chuỗi trong các trường hợp này sẽ lớn hơn số ký tự có trong chuỗi đó.

Bởi vậy lúc dùng 2 hàm này để lấy số ký tự có trong string, cần hết sức chú ý trong trường hợp tồn tại ký tự được tạo thành bởi 2 mã ký tự như trên.

V. Cắt String Trong C++

Hướng dẫn phương pháp cắt string trong C++. Bạn sẽ học được cách sử dụng 3 hàm cơ bản như front(), back() và substr() để cắt string trong C++ sau bài học này.

Chúng ta có 3 phương pháp cơ bản để cắt string trong C++ như sau:

Hàm front(): Cắt ký tự trước tiên từ string
Hàm back(): Cắt ký tự cuối cùng từ string
Hàm substr(): Cắt một phạm vi từ string

Cắt ký tự trước tiên từ string trong C++ bằng hàm front

Hàm front là 1 hàm thành viên trong class std:string, có tác dụng tham chiếu tới ký tự đầu tiên trong chuỗi string.

Bằng cách ứng dụng hàm front(), chúng ta không những có thể cắt ra giá trị của ký tự đầu tiên trong string, mà còn có thể thay đổi giá trị của ký tự đầu tiên đó.

Chúng ta sử dụng hàm front trong C++ với cú pháp sau đây:

str.front();

Trong đó str là chuỗi string cần cắt ra ký tự ban đầu. Hàm front() sẽ trả về tham chiếu tới ký tự đầu tiên của chuỗi string, qua đó chúng ta có thể cắt lấy giá trị của ký tự đầu tiên này, hoặc là gán một ký tự khác để thay đổi nó.

Lưu ý chúng ta không dùng hàm front() cho chuỗi string trống nhé.

Ví dụ cụ thể:

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string str = "Hello World!";
    
    //Tạo tham chiếu tới vị trí ký tự đầu tiên của chuỗi string
    char frontstr = str.front();
    cout << frontstr << endl;
    
    //Thay đổi ký tự đầu tiên
    str.front() = 'K';
    cout << str << endl;
 
    return 0;
}

Kết quả:

H
Kello World!

Cắt ký tự cuối cùng từ string trong C++ bằng hàm back

Ngược lại với hàm front() chính là hàm back().

Hàm back là 1 hàm thành viên trong class std:string, có tác dụng tham chiếu đến ký tự cuối cùng trong chuỗi string.

Bằng cách ứng dụng hàm back(), chúng ta không những có thể cắt ra giá trị của ký tự đầu tiên trong string, mà còn có thể thay đổi giá trị của ký tự cuối cùng đó.

Chúng ta dùng hàm back trong C++ với cú pháp sau đây:

str.back();

Trong đó str là chuỗi string cần cắt ra ký tự cuối cùng. Hàm back() sẽ trả về tham chiếu tới ký tự cuối cùng của chuỗi string, qua đó chúng ta có thể cắt lấy giá trị của ký tự cuối cùng này, hoặc là gán một ký tự khác để thay đổi nó.

Lưu ý chúng ta không dùng hàm back() cho chuỗi string trống nhé.

Ví dụ cụ thể:

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string str = "Hello World!";
    
    //Tạo tham chiếu tới vị trí ký tự cuối cùng của chuỗi string
    char backstr = str.back();
    cout << backstr << endl;
    
    //Thay đổi ký tự cuối cùng.
    str.back() = '?';
    cout << str << endl;
 
    return 0;
}

Kết quả:

!
Hello World?

Cắt một phạm vi từ string bằng hàm substr()

Chúng ta sử dụng hàm substr() để cắt một phạm vi chỉ định từ trong string ban đầu. Ví dụ cụ thể:

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string str = "Hello World!";
    string substr = str.substr(1, 3);
    cout << substr << endl;

    string substr2 = str.substr(1,6); 
    cout << substr2 << endl;
    return 0;
}

Kết quả, các chuỗi string được cắt trong phạm vi chỉ định như sau:

ell
ello W

VI. Nối Chuỗi String Trong C++

Bài tập C++: Nối chuỗi trong C++

Đề bài: Viết chương trình C++ để nối 2 chuỗi trong C.

Bài tập C++ này có nhiều cách gọi: trộn hai chuỗi, nối hai chuỗi, ghép hai chuỗi hay cộng hai chuỗi, … Dù có nhiều cách gọi khác nhau đi chăng nữa thì đây cũng chỉ là một bài tập để nối ghép các ký tự của hai chuỗi để thành một chuỗi duy nhất.

Lời giải (không sử dụng hàm)

Để giải bài tập C++ này, bạn sử dụng hàm strlen() để tìm độ dài chuỗi. Sử dụng vòng lặp để lặp qua tất cả ký tự của chuỗi.

Dưới đây là chương trình C++ để giải bài tập nối chuỗi trong C++:

#include <stdio.h>
#include <string.h>
 
int main() {
   char s1[10] = "VietTuts";
   char s2[] = ".Vn";
     
   int i, j, n1, n2;
     
   n1 = strlen(s1);
   n2 = strlen(s2);
     
   j=0;
   for(i = n1; i<n1+n2; i++ ) {
      s1[i] = s2[j];
      j++;
   }
     
   s1[i] = '\0';
    
   printf("\nKet qua sau khi noi chuoi la:\n");
   printf("%s", s1);
 
   return 0;
}

Chạy chương trình C++ trên cho kết quả như sau:

Lời giải (sử dụng hàm)

Bạn có thể thực hiện nối hai chuỗi thành một chuỗi bởi sử dụng các hàm strcpy() và strcat() trong C.

Giả sử bạn cần nối hai chuỗi là str1 và str2. Bạn cần khai báo thêm một chuỗi str3 có độ dài bằng tổng độ dài của str1 và str2. Sau đó:

Sử dụng hàm strcpy(str3, str1) để sao chép chuỗi str1 vào str3.

Sử dụng hàm strcat(str3, str2) để nối chuỗi str2 với str1 vừa được sao chép.

Dưới đây là chương trình C++ để giải bài tập nối chuỗi trong C++:

#include<stdio.h>
#include<string.h>
 
int main() {
   char str1[100];
   char str2[100];
   char str3[100];
   int len;
  
   printf("Nhap chuoi 1: ");
   gets(str1);
  
   printf("Nhap chuoi 2: ");
   gets(str2);
  
   strcpy(str3, str1);
   strcat(str3, str2);
  
   printf("\nNoi chuoi: %s", str3);
  
   return (0);
}

VII. So Sánh 2 String Trong C++

Bài tập C++: So sánh hai chuỗi trong C++

Đề bài: Viết chương trình C++ để sa sánh hai chuỗi.

Yêu cầu bài tập C++ này là so sánh xem hai chuỗi có đồng nhất (giống nhau) hay không. Để giải bài tập C++ này bạn cần sử dụng vòng lặp để duyệt qua tất cả các ký tự của hai chuỗi và kiểm tra từng ký tự tương ứng với chỉ mục có giống nhau không.

Lời giải

Dưới đây là chương trình C++ để giải bài tập so sánh 2 chuỗi trong C++:

#include <stdio.h>
 
int main() {
   char s1[50];     
   char s2[50];
    
   int n = 0;
   short flag = 1;
    
    printf("Nhap chuoi s1: ");
    gets(s1);
    printf("Nhap chuoi s2: ");
    gets(s2);
     
   // so sanh chuoi s1 voi s2
   while (s1[n] != '\0') {
      if(s1[n] != s2[n]) {
         flag = 0;
         break;
      }
      n++;
   }
     
   if(flag == 1) {
      printf("Chuoi %s va chuoi %s la giong nhau.", s1, s2);
   }else {
      printf("Chuoi %s va chuoi %s la khac nhau.", s1, s2);
   }
 
   return 0;
}

VIII. Xóa 1 Ký Tự Trong String C++

Hướng dẫn cách xóa string trong C++. Bạn sẽ học được cách sử dụng các hàm như hàm pop_back, hàm erase để xóa string trong C++ sau bài học này.

Chúng ta có 3 phương pháp để xóa string trong C++ như sau:

Hàm pop_back : Xóa ký tự cuối cùng trong string
Hàm erase: Xóa ký tự tại vị trí chỉ định
Hàm erase(first, last): Xóa các ký tự trong phạm vi chỉ định

Xóa ký tự cuối cùng trong string C++ bằng pop_back

Hàm pop_back là một hàm thành viên trong class std:string, có tác dụng xóa ký tự cuối cùng trong string cũng như giảm độ dài của nó đi một đơn vị.

Cú pháp sử dụng hàm pop_back để xóa ký tự cuối cùng trong string như sau:

str.pop_back();

Trong đó str là tên string cần xóa ký tự cuối cùng. Lưu ý là ký tự cuối cùng ở đây không bao gồm ký tự kết thúc chuỗi \0.

Hàm pop_back thuộc kiểu void, do đó nó sẽ không trả giá trị. Bởi vậy nó sẽ xóa ký tự cuối cùng trong string chứ không trả về ký tự đó. Trong trường hợp muốn lấy ký tự cuối cùng trong string, hãy sử dụng tới hàm back để thay thế.

Ví dụ cụ thể:

#include <iostream>
#include <string>

int main ()
{
  std::string str ("Hello world");
  str.pop_back();
  std::cout << str;
  return 0;
}
//> Hello worl

Có thể thấy ký tự cuối cùng trong chuỗi là ký tự d đã bị xóa khỏi chuỗi ban đầu.

Xóa 1 ký tự trong string bằng hàm erase

Hàm erase là một hàm thành viên trong class std:string, có tác dụng xóa một hoặc nhiều ký tự trong string C++ cũng như làm giảm độ dài tương ứng của nó.

Để xóa 1 ký tự tại vị trí chỉ định trong string C++ bằng hàm erase chúng ta sử dụng cú pháp sau đây:

str.erase(p);

Ở đây trình lặp (iterator) là một vòng lặp có tác dụng giống như con trỏ, giúp truy cập đến các ký tự ở vị trí cụ thể trong string.

Trong trường hợp cần chỉ đến vị trí index thứ n trong string, chúng ta sẽ viết trình lặp p như sau:

str.begin() + i

Trong đó str.begin() chỉ đến vị trí đầu tiên trong string, và i là index của vị trí ký tự cần chỉ đến.

Kết hợp lại thì công thức để xóa 1 ký tự vào vị trí chỉ định trong string C++ bằng hàm erase sẽ như sau:

str.erase(str.begin() + i);

Ví dụ cụ thể:

#include <iostream>
#include <string>
using namespace std;
int main ()
{
    string str("Hello World");
    str.erase(str.begin() + 2);//Xóa ký tự ở vị trí thứ 2
    cout << str<<endl;

    str.erase(str.begin() + 6);//Xóa ký tự ở vị trí thứ 6
    cout << str;
    return 0;
}

Kết quả:

Helo World
Helo Wrld

Xóa các ký tự trong một phạm vi chỉ định trong string C++

Chúng ta sử dụng hàm erase để xóa các ký tự trong một phạm vi chỉ định trong string C++ với cú pháp sau đây:

str.erase( iterator_first, iterator_last);

Trong đó str là chuỗi ban đầu, iterator_first và iterator_last là phạm vi cần xóa được chỉ định trong trình lặp trỏ đến vị trí cần xóa trong string.

Tương tự như khi xóa 1 ký tự thì cú pháp sử dụng thực tế để xóa các ký tự trong một phạm vi chỉ định trong string C++ bằng hàm erase sẽ là:

str.erase(str.begin() + start, str.begin() + end);

Trong đó start và end là vị trí index của phạm vi xóa trong string.

Ví dụ cụ thể:

#include <iostream>
#include <string>
using namespace std;
int main ()
{
    string str("Hello World");

    //Xóa ký tự trong phạm vi index từ 1 đến 3
    str.erase(str.begin() + 1, str.begin() + 3);
    cout << str<<endl;

    //Xóa ký tự trong phạm vi index từ 2 đến 5
    str.erase(str.begin() + 2, str.begin() +5);
    cout << str;
    return 0;
}

Kết quả:

Hlo World
Hlorld

IX. Bài Tập Về String Trong C++

C++ cung cấp hai kiểu biểu diễn chuỗi như sau:

Chuỗi theo phong cách của ngôn ngữ C (C-style),

Lớp Chuỗi (String) được giới thiệu trong C/C++ chuẩn.

Chuỗi theo phong cách C

Dạng chuỗi này bắt nguồn từ ngôn ngữ C và tiếp tục được hỗ trợ trong C/C++. Chuỗi trong ngôn ngữ lập trình C thực chất là mảng một chiều của các ký tự mà kết thúc bởi một ký tự null ‘\0’.

Phần khai báo và khởi tạo dưới đây tạo ra một chuỗi bao gồm một từ “Hello”. Để giữ các giá trị null tại cuối của mảng, cỡ của mảng các ký tự bao gồm một chuỗi phải nhiều hơn số lượng các ký tự trong từ khóa “Hello”.

char loiChao[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

Nếu bạn theo quy tắc khởi tạo các chuỗi, bạn có thể viết lệnh như sau:

char loiChao[] = "Hello";

Dưới đây là phần biểu diễn ô nhớ cho đoạn chuỗi trên trong ngôn ngữ C/C++:

Thực tế, bạn không đặt ký tự null tại vị trí cuối cùng của biến hằng số. Bộ biên dịch C tự động thêm ‘\0’ tại ví trí cuối cùng của chuỗi khi nó khởi tạo chuỗi. Cùng thử ví dụ in ra chuỗi sau đây:

#include <iostream>

using namespace std;

int main ()
{
   char loiChao[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

   cout << "Khi gap nhau, chung ta noi: ";
   cout << loiChao << endl;

   return 0;
}

Khi đoạn code trên được biên dịch và thực hiện, kết quả in ra sẽ như sau:

Khi gap nhau, chung ta noi: Hello

Ngôn ngữ C/C++ hỗ trợ nhiều hàm đa dạng để thao tác các chuỗi kết thúc là null:

STT	Hàm & Mục đích
1	strcpy(s1, s2);Sao chép chuỗi s2 cho chuỗi s1.
2	strcat(s1, s2);Nối chuỗi s2 vào cuối chuỗi s1.
3	strlen(s1);Trả về độ dài của chuỗi s1.
4	strcmp(s1, s2);Trả về 0 nếu s1 và s2 là như nhau; nhỏ hơn 0 nếu s1<s2; lớn hơn 0 nếu s1>s2.
5	strchr(s1, ch);Trả về con trỏ tới vị trí đầu tiên của ch trong s1.
6	strstr(s1, s2);Trả về con trỏ tới vị trí đầu tiên của chuỗi s2 trong chuỗi s1.

Dưới đây là ví dụ cho việc sử dụng một vài hàm bên trên:

#include <iostream>
#include <cstring>

using namespace std;

int main ()
{
   char chuoi1[10] = "Hello";
   char chuoi2[10] = "Christmas";
   char chuoi3[10];
   int  len ;

   // sao chep chuoi1 vao trong chuoi3
   strcpy( chuoi3, chuoi1);
   cout << "strcpy( chuoi3, chuoi1) : " << chuoi3 << endl;

   // noi hai chuoi: chuoi1 va chuoi2
   strcat( chuoi1, chuoi2);
   cout << "strcat( chuoi1, chuoi2): " << chuoi1 << endl;

   // tong do dai cua chuoi1 mot sau khi thuc hien noi chuoi
   len = strlen(chuoi1);
   cout << "Dung ham strlen(chuoi1) de tinh do dai chuoi1: " << len << endl;

   return 0;
}

Chạy chương trình C/C++ trên sẽ cho kết quả như hình sau:

Lớp String trong C/C++

Thư viện chuẩn C/C++ cung cấp một kiểu lớp String mà hỗ trợ tất cả hoạt động liên quan tới chuỗi đã đề cập ở trên, và bổ sung thêm nhiều tính năng nữa. Chúng ta sẽ học lớp này trong Thư viện chuẩn C/C++ (C++ Standard Library), nhưng lúc này, chúng ta xem xét ví dụ sau:

Lúc này, có thể bạn không hiểu ví dụ này, bởi vì chúng ta chưa bàn luận về Lớp và Đối tượng trong C/C++. Vì thế, bạn quan sát và ghi nhớ chúng tới khi bạn đã hiểu các khái niệm về Hướng đối tượng được trình bày ở chương sau đó.

#include <iostream>
#include <string>

using namespace std;

int main ()
{
   string chuoi1 = "Hello";
   string chuoi2 = "Christmas";
   string chuoi3;
   int  len ;

   // sao chep chuoi1 vao trong chuoi3
   chuoi3 = chuoi1;
   cout << "Bay gio chuoi3 la: " << chuoi3 << endl;

   // noi hai chuoi: chuoi1 va chuoi2
   chuoi3 = chuoi1 + chuoi2;
   cout << "chuoi1 + chuoi2 co ket qua la: " << chuoi3 << endl;

   // tong do dai cua chuoi3 mot sau khi thuc hien noi chuoi
   len = chuoi3.size();
   cout << "Tinh do dai voi ham chuoi3.size() :  " << len << endl;

   return 0;
}

Chạy chương trình C/C++ trên sẽ cho kết quả như hình sau:

X. Chuẩn Hóa String Trong C++

Chuẩn hóa chuỗi trong C

Ý tưởng chuẩn hóa chuỗi trong C như sau:

Bỏ các ký tự khoảng trắng thừa ở đầu chuỗi
Bỏ các ký tự khoảng trắng thừa ở cuối chuỗi
Viết hoa chữ cái đầu tiên của chuỗi
Bỏ qua các khoảng trắng thừa ở giữa
Đưa tất cả về lowercase
Viết hoa chữ cái bắt đầu từ theo ý tưởng đếm từ phía trên

 
void Correct(char str[], int length)
{
    int first = 0, last = length - 1;
    // Xóa dấu trắng đầu chuỗi
    while (first < last && str[first] == ' ')
        first++;
    // Xóa dấu trắng cuối chuỗi
    while (last > first && str[last] == ' ')
        last--;
 
    // Viết hoa chữ cái đầu tiên
    if (str[first] >= 'a' && str[first] <= 'z')
        str[first] -= 32;
    for (int i = first + 1; i <= last; i++)
    {
        // Đưa hết về chữ thường
        if (str[i] >= 'A' && str[i] <= 'Z'){
            str[i] += 32;
        }
        if (i + 1 <= last)
        {
            // Bỏ dấu trắng thừa ở giữa
            if (str[i] == str[i + 1] && str[i] == ' ')
            {
                continue;
            }
            // Nếu là chữ cái đầu mỗi từ thì viết hoa
            if (str[i] == ' ' && str[i + 1] >= 'a' && str[i + 1] <= 'z')
            {
                str[i + 1] -= 32;
            }
        }
        printf("%c", str[i]);
    }
}

Lời giải chuẩn hóa chuỗi và đếm số từ trong C

#include <stdio.h>
#include <string.h>
 
int WordCount(char str[], int length)
{
    int word = (str[0] != ' ');
    for (int i = 0; i < length - 1; i++)
    {
        if (str[i] == ' ' && str[i + 1] != ' ')
        {
            word++;
        }
    }
    return word;
}
 
void Correct(char str[], int length)
{
    int first = 0, last = length - 1;
    // Xóa dấu trắng đầu chuỗi
    while (first < last && str[first] == ' ')
        first++;
    // Xóa dấu trắng cuối chuỗi
    while (last > first && str[last] == ' ')
        last--;
 
    // Viết hoa chữ cái đầu tiên
    if (str[first] >= 'a' && str[first] <= 'z')
        str[first] -= 32;
    for (int i = first + 1; i <= last; i++)
    {
        // Đưa hết về chữ thường
        if (str[i] >= 'A' && str[i] <= 'Z'){
            str[i] += 32;
        }
        if (i + 1 <= last)
        {
            // Bỏ dấu trắng thừa ở giữa
            if (str[i] == str[i + 1] && str[i] == ' ')
            {
                continue;
            }
            // Nếu là chữ cái đầu mỗi từ thì viết hoa
            if (str[i] == ' ' && str[i + 1] >= 'a' && str[i + 1] <= 'z')
            {
                str[i + 1] -= 32;
            }
        }
        printf("%c", str[i]);
    }
}
 
int main()
{
    char str[100];
    // Nhập chuỗi
    printf("\nNhap chuoi: ");
    fgets(str, sizeof str, stdin);
    // Do sử dụng fgets nên chuỗi của chúng ta sẽ đọc cả ký tự '\n'.
    // Xóa bỏ nó đi.
    int length = strlen(str) - 1; 
    str[length] = '\0';
    printf("So tu cua \"%s\" la %d", str, WordCount(str, length));
    printf("\nXau chuan hoa la: ");
    Correct(str, length);
}

Kết quả chạy thử:

 
PS G:\c_cources\day_61> g++ .\ChuanHoa.cpp -o .\ChuanHoa
PS G:\c_cources\day_61> .\ChuanHoa.exe
 
Nhap chuoi:    LAP    trINH    khong    KHO!
So tu cua "   LAP    trINH    khong    KHO!" la 4
Xau chuan hoa la: Lap trinh khong kho

The post String Trong C++ first appeared on Techacademy.

source https://techacademy.edu.vn/string-trong-c/

Đệ Quy Trong C++

Đệ quy trong C++ là 1 phương thức vô cùng quan trọng và là cơ sở của rất rất đa dạng thuật toán. Vì vậy, hiểu được đệ quy sẽ giúp bạn dễ dàng tiếp cận và học hỏi thêm nhiều kiến thức khác về lập trình. Trong bài viết ngày này, Techacademy sẽ chia sẻ với các bạn tất tần tật mọi thứ về đệ quy cùng với các bài tập đệ quy có lời giải chi tiết để giúp bạn hiểu rõ hơn về nó nữa đấy!

I. Đệ Quy Trong C++ Là Gì

Đệ quy trong C++ là quá trình trong đó một phương thức gọi lại chính nó một cách liên tiếp. Một hàm trong C++ gọi lại chính nó được gọi là phương thức đệ quy. Trong một hàm đệ quy sẽ gồm có điều kiện dừng và lời gọi hàm đệ quy, cú pháp cụ thể như sau:

Kiểu_trả_về   Tên_hàm (Các_tham_số)
{ 
    Điều_kiện_dừng;

    return Tên_hàm (Các_tham_số_mới) ;
    // hoặc một biểu thức có chứa lời gọi hàm.
}

Để giúp bạn dễ hình dung hơn thì dưới đây sẽ là ví dụ về hàm đệ quy giúp tính giai thừa của một số tự nhiên:

long long Giaithua(int n)
{
    if (n==0 || n==1)
       return 1;
    else
       return Giaithua(n-1) * n;
}

Giải thích thuật toán: Ở đây, điều kiện dừng chính là n=0 hoặc là n=1 thì sẽ trả về giá trị là 1 ( Do 0!=1!=1). Ngược lại, nếu n>1, hàm sẽ trả về n*Giaithua(n-1). Chẳng hạn ta cho n nhận giá trị là 3, chương trình sẽ thực thi như sau:

GiaiThua(3) 
GiaiThua(2) 
GiaiThua(1) 
return 1 
return 2*1 = 2 
return 3*2 = 6

Vậy mục đích của hàm đệ quy là chia vấn đề thành những vấn đề nhỏ hơn cho đến lúc đạt được điều kiện cơ bản. Lưu ý quan trọng khi dùng đệ quy là bắt buộc phải có điều kiện dừng, nếu không có thì sẽ làm hàm gọi hàm liên tục không có điểm dừng và dẫn đến chương trình không thể kết thúc được.

II. Cách Sử Dụng Đệ Quy Trong C++

Trong C++, một hàm gọi chính nó ta gọi đó là hàm đệ quy, nghĩa là trong thân hàm sẽ gọi đến chính tên hàm hiện tại và truyền đúng những tham số mà hàm đã khai báo.

Cú pháp: Cú pháp của hàm đệ quy trong C++ như sau:

HamDeQuy(){    
      HamDeQuy();  //goi lai chinh no
}

Ví dụ: Chúng ta cùng xem một ví dụ đơn giản về hàm đệ quy trong C++ đó là tính giai thừa của một số nguyên.

Trước khi giải bài toán tính giai thừa của một số nguyên trong C++ chúng ta cùng nhớ lại công thức tính giai thừa trong toán học trước đã nhé.

Theo định nghĩa giai thừa ta có:

0! = 1
n! = 1 * 2 * 3 * … * n

Vậy là ta đã có công thức tính giai thừa của một số nguyên rồi. Nếu n = 0 thì giai thừa bằng 1. Nếu n > 0 thì giai thừa sẽ là tích từ 1 đến n. Và không có giai thừa của số âm.

Giải bằng vòng lặp For

Trước khi đi vào giải bài toán trên bằng hàm đệ quy, mình sẽ giải bằng vòng lặp for trong C++ trước nhé.

Ví dụ

#include<iostream>  
using namespace std;
int main()   
{    
    int n;
    while(true) {
        int giaithua = 1;
        cout << "Nhap so n: ";
        cin >> n;
         
        //Nhap n nho hon 0 de thoat khoi vong lap
        if(n < 0) {
            cout << "  So am khong co giai thua" << endl;
            break;
        }
 
        if ( n > 0) {
            for(int i = 1; i <=n; i++) {
                giaithua = giaithua * i;
            }
        }
        cout << "  Giai thua cua " << n << " la: " << giaithua << endl;
 
    }
    return 0;  
}

Và kết quả sau khi thực thi chương trình trên như sau:

Như vậy, để giải quyết bài toán giai thừa của một số bằng vòng lặp for trong C++ rất đơn giản phải không các bạn? Bây giờ mình sẽ giải bài toán giai thừa trên bằng hàm đệ quy trong C++.

Giải bằng đệ quy C++

Các bạn để ý kỹ thì thấy thuật toán tính giai thừa sẽ như sau: Giả sử cần tính 5!, lúc này quy luật của nó sẽ là.

5! = 4! * 5
4! = 3! * 4
3! = 2! * 3
2! = 1! * 2
1! = 1

Thay các vế vào ta sẽ được quy luật: 5! = 1 * 2 * 3 * 4 * 5.

Giả sử ta có hàm tính gian thừa của một số tên là GT, lúc này thay vào công thức trên ta được như sau:

GT(5) = GT(4) * 5
GT(4) = GT(3) * 4
GT(3) = GT(2) * 3
GT(2) = GT(1) * 2
GT(1) = 1

Vậy, ta có thể áp dụng giải thuật đệ quy C++ để giải quyết, bằng cách bên trong thân hàm sẽ gọi đến chính hàm đó.

Ví dụ

#include<iostream>  
using namespace std;
int GiaiThua(int n) {
    // Trường hợp người dùng nhập
    if (n == 1)
        return 1;
    else
        return (n * GiaiThua(n - 1));
}
 
int main()   
{    
    int n;
    while(true) {
        cout << "Nhap so n: ";
        cin >> n;
        //Nhap n nho hon 0 de thoat khoi vong lap
        if(n < 0) {
            cout << "  So am khong co giai thua" << endl;
            break;
        }
        cout << "  Giai thua cua " << n << " la: " << GiaiThua(n) << endl;
    }
    return 0;  
}

Và kết quả sau khi thực thi chương trình trên như sau:

Đối với các bạn mới bắt đầu học lập trình thì cách giải bài toán giai thừa trên bằng vòng lặp for sẽ dễ hiểu hơn rất nhiều so với việc giải bằng hàm đệ quy. Tuy nhiên, các bạn đừng quá lo lắng, mình sẽ giải thích đoạn code cho các bạn bạn dễ hiểu.

Giả sử mình nhập n = 5 thì chương trình trên sẽ chạy như sau:

GiaiThua(5) 
   GiaiThua(4) 
      GiaiThua(3) 
         GiaiThua(2) 
            GiaiThua(1) 
               return 1 
            return 2*1 = 2 
         return 3*2 = 6 
      return 4*6 = 24 
   return 5*24 = 120

Mục đích của hàm đệ quy là chia vấn đề thành các vấn đề nhỏ hơn cho đến khi đạt được điều kiện cơ bản.

Ví dụ trong chương trình giai thừa ở trên, chúng ta đang giải quyết hàm giai thừa GiaiThua(n) bằng cách gọi hàm giai thừa nhỏ hơn GiaiThua(n-1), điều này được lặp lại liên tục cho đến khi giá trị n đạt đến điều kiện cơ sở (GiaiThua(1) = 1).

III. Đệ Quy Quay Lui Trong C++

Quay lui là 1 kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

Tư tưởng

Dùng để giải bài toán liệt kê những cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử toàn bộ các khả năng.

Các bước trong việc liệt kê cấu hình dạng X[1…n]:

Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận những giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
Xét đa số giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]…tiếp tục như vậy cho đến bước:
…
…
Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
Thông báo cấu hình tìm được.

Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search).

Mô hình thuật toán

Mã giả cho thuật toán quay lui.

Backtracking(k) {
   for([Mỗi phương án chọn i(thuộc tập D)]) {
      if ([Chấp nhận i]) {
         [Chọn i cho X[k]];
         if ([Thành công]) {
            [Đưa ra kết quả];
         } else {
            Backtracking(k+1);
            [Bỏ chọn i cho X[k]];
         }
      }
   }
}

Ví dụ: Trò chơi Sudoku

Sudoku là một trò chơi khá phổ biến và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9×9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3×3 chính là các số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và lời giải:

Áp dụng quay lui để giải bài toán sudoku. Ý tưởng: Mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán (ở đây chú ý mảng chỉ có kích thước 9×9×9)

void solveSudoku(int S[][9], int x, int y){
    if(y == 9){
        if(x == 8){
            printSolution(S);
            exit(0);
        } else {
            solveSudoku(S, x+1,0);
        }
    } else if(S[x][y] == 0){
        for (int k = 1; k <=9; k++){
            if(checkValid(S,x,y,k)){
                S[x][y] = k;
                solveSudoku(S, x, y+1);
                S[x][y] = 0;
            }
        }
    } else {
        solveSudoku(S,x,y+1);
    }
}

boolean checkValid(int S[][9], int x, int y, int k){
    for(int i = 0; i <9 ; i++){
        if(S[x][i] == k) return false;
    }
    for(int i = 0; i <9 ; i++){
        if(S[i][y] == k) return false;
    }
    int a = x/3, b = y/3;
    for(int i = 3*a; i < 3*a+3; i++){
        for(int j = 3*b; j < 3*b+3; j++){
            if(S[i][j] == k) return false;
        }
    }
    return true;
}

Nhận xét

Ưu điểm: Việc quay lui là thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian chạy.

Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải các nhược điểm sau:

Rơi vào tình trạng “thrashing”: qúa trình tìm kiếm cứ gặp phải bế tắc với cùng một nguyên nhân.
Thực hiện các công việc dư thừa: Mỗi lần chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
Không sớm phát hiện được các khả năng bị bế tắc trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết đc nhánh tìm kiếm sẽ đi vào bế tắc.

IV. Bài Tập Đệ Quy Quay Lui Trong C++

+ Tìm Ước Chung Lớn Nhất Và Bội Chung Nhỏ Nhất Bằng Đệ Quy

Hàm đệ quy là những hàm gọi lại chính nó. Nó hữu dụng trong các tác vụ như sắp xếp hoặc tính toán các số giai thừa… Hàm đệ quy tương ứng với khái niệm quy nạp trong toán học.

Bài tập 1. Thuật toán Euclide tìm ước chung lớn nhất

Viết chương trình tìm ước chung lớn nhất của 2 số nguyên dương a, b bằng thuật toán. Euclide được định nghĩa đệ quy như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);
else
return UCLN(a,b-a);
}
void main() {
clrscr();
int a,b;
cout<<"Nhap a = ";
cin>>a;
cout<<"Nhap b = ";
cin>>b;
cout<<"Uoc chung lon nhat cua "<<a<<" va "<<b<<" la "<<UCLN(a,b);
getch();
}

Bài tập 2. Tìm ước chung lớn nhất của n số nguyên

Viết chương trình tìm ước chung lớn nhất của n số nguyên dương 0 1 ,…, n a a được định nghĩa đệ quy như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
/*Ham tra ve uoc chung lon nhat cua a va b*/
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);
else
return UCLN(a,b-a);
}
/*Ham tra ve uoc chung lon nhat cua n phan tu duoc luu tru trong mang 1 chieu a*/
int UC(int a[], int n) {
if(n==1)
return a[0];
else
return UCLN(a[n-1],UC(a,n-1));
}
void main() {
clrscr();
int *a,n;
cout<<"Nhap n = ";
cin>>n;
a = new int[n];
cout<<"Nhap vao "<<n<<" phan tu\n";
for(int i=0; i<n ; i++){
cout<<"a["<<i<<"] = ";
cin>>a[i];
}
cout<<"UCLN cua "<<n<<" phan tu vua nhap la "<<UC(a,n);
getch();
}

+ Đệ Quy Fibonacci Trong C++

Chắc các bạn cũng đã biết dãy Fibonacci là gì rồi. Đó là dãy số mà số tiếp theo là tổng của hai số liền trước, ví dụ: 1, 1, 2, 3, 5, 8, 13, …. Bài viết này sẽ hướng dẫn cho các bạn cách tính số fibonacci bằng phương pháp dùng đệ quy và không dùng đệ quy.

Dùng đệ quy để tính số fibonacci

Công thức truy hồi của dãy fibonacci có dạng: f(n) = f(n-1) + f(n-2) .

Với f(1) = 1; f(2) =1;

Cách tính số Fibonacci trong C

 
#include <stdio.h>
#include <conio.h>
int Fibonacci(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main()
{
    int n;
    printf("nhap n: ");
    scanf("%d", &n);
    printf("So Fibonacci thu %d la: %d", n, Fibonacci(n));
    return 0;
}

 
nhap n: 6
So Fibonacci thu 6 la: 8

Cách tính số Fibonacci trong C++

 
#include <iostream>
using namespace std;
int Fibonacci(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main()
{
    int n;
    cout << "nhap n: ";
    cin >> n;
    cout << "So Fibonacci thu " << n << " la: " << Fibonacci(n);
    return 0;
}

 
nhap n: 6
So Fibonacci thu 6 la: 8

Khi đã có hệ thức truy hồi thì việc viết hàm đệ quy rất đơn giản phải không nào ? Nhưng liệu bạn có thử nhập n lớn ( cỡ 30 – 40 ) không ạ. Nếu thử rồi thì chắc các bạn cũng thấy nó chậm hơn rất nhiều. Nguyên nhân là khi tính số fibonacci thứ 5 chương trình sẽ yêu cầu tính hai số fibonacci thứ 4 và thứ 3. Nó lại tiếp tục như vậy đến khi tính được số fibonacci thứ 2 hoặc thứ 1 mới dừng lại.

Vậy nếu muốn chương trình của chúng ta chạy nhanh hơn thì chúng ta phải khử đệ quy. Cùng làm nhé !

Cách tính số Fibonacci không dùng đệ quy

Ý tưởng cách này là chúng ta sẽ dùng một vòng lặp để tính số Fibonacci .

Nếu n = 1 hoặc n = 2 thì chúng ta return 1
Sau đó tạo một biến i có giá trị bằng 3
Trong vòng while chúng ta tính a = a1 + a2
Sau đó gán a1 = a2 và a2 = a cứ chạy đến khi nào i = n thì dừng

 
#include <stdio.h>
int Fibonacci(int n)
{
    int a1 = 1, a2 = 1;
    if (n == 1 || n == 2)
        return 1;
    int i = 3, a;
    while (i <= n)
    {
        a = a1 + a2;
        a1 = a2;
        a2 = a;
        i++;
    }
    return a;
}
int main()
{
    int n;
    printf("nhap n: ");
    scanf("%d", &n);
    printf("So Fibonacci thu %d la: %d", n, Fibonacci(n));
    return 1;
}

 
nhap n: 40
So Fibonacci thu 40 la: 102334155

Cách tính số Fibonacci trong C++

 
#include <iostream>
using namespace std;
int Fibonacci(int n)
{
    int a1 = 1, a2 = 1;
    if (n == 1 || n == 2)
        return 1;
    int i = 3, a;
    while (i <= n)
    {
        a = a1 + a2;
        a1 = a2;
        a2 = a;
        i++;
    }
    return a;
}
int main()
{
    int n;
    cout << "nhap n: ";
    cin >> n;
    cout << "So Fibonacci thu " << n << " la: " << Fibonacci(n);
    return 1;
}

nhap n: 40
So Fibonacci thu 40 la: 102334155

Tìm 1000 số Fibonacci đầu tiên

Với code trên bạn tìm đến số Fibo thứ 50 là bị tràn số rồi. Code với số nguyên lớn dưới đây sẽ giúp bạn tính được số Fibo thứ 1000 hoặc hơn thế nữa. Có thể bạn sẽ cần đọc bài viết dưới đây trước khi tham khảo code này.

Lời giải cho chương trình in ra 1000 số Fibo đầu tiên.

 
#include <bits/stdc++.h>
using namespace std;
 
const int base = 1000000000;
const int base_digits = 9;
struct bigint
{
    vector<int> a;
    int sign;
 
    bigint() : sign(1)
    {
    }
 
    bigint(long long v)
    {
        *this = v;
    }
 
    bigint(const string &s)
    {
        read(s);
    }
 
    void operator=(const bigint &v)
    {
        sign = v.sign;
        a = v.a;
    }
 
    void operator=(long long v)
    {
        sign = 1;
        if (v < 0)
            sign = -1, v = -v;
        for (; v > 0; v = v / base)
            a.push_back(v % base);
    }
 
    bigint operator+(const bigint &v) const
    {
        if (sign == v.sign)
        {
            bigint res = v;
 
            for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i)
            {
                if (i == (int)res.a.size())
                    res.a.push_back(0);
                res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
                carry = res.a[i] >= base;
                if (carry)
                    res.a[i] -= base;
            }
            return res;
        }
        return *this - (-v);
    }
 
    bigint operator-(const bigint &v) const
    {
        if (sign == v.sign)
        {
            if (abs() >= v.abs())
            {
                bigint res = *this;
                for (int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i)
                {
                    res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
                    carry = res.a[i] < 0;
                    if (carry)
                        res.a[i] += base;
                }
                res.trim();
                return res;
            }
            return -(v - *this);
        }
        return *this + (-v);
    }
 
    void operator*=(int v)
    {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i)
        {
            if (i == (int)a.size())
                a.push_back(0);
            long long cur = a[i] * (long long)v + carry;
            carry = (int)(cur / base);
            a[i] = (int)(cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }
 
    bigint operator*(int v) const
    {
        bigint res = *this;
        res *= v;
        return res;
    }
 
    friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1)
    {
        int norm = base / (b1.a.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.a.resize(a.a.size());
 
        for (int i = a.a.size() - 1; i >= 0; i--)
        {
            r *= base;
            r += a.a[i];
            int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
            int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
            int d = ((long long)base * s1 + s2) / b.a.back();
            r -= b * d;
            while (r < 0)
                r += b, --d;
            q.a[i] = d;
        }
 
        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return make_pair(q, r / norm);
    }
 
    bigint operator/(const bigint &v) const
    {
        return divmod(*this, v).first;
    }
 
    bigint operator%(const bigint &v) const
    {
        return divmod(*this, v).second;
    }
 
    void operator/=(int v)
    {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = (int)a.size() - 1, rem = 0; i >= 0; --i)
        {
            long long cur = a[i] + rem * (long long)base;
            a[i] = (int)(cur / v);
            rem = (int)(cur % v);
        }
        trim();
    }
 
    bigint operator/(int v) const
    {
        bigint res = *this;
        res /= v;
        return res;
    }
 
    int operator%(int v) const
    {
        if (v < 0)
            v = -v;
        int m = 0;
        for (int i = a.size() - 1; i >= 0; --i)
            m = (a[i] + m * (long long)base) % v;
        return m * sign;
    }
 
    void operator+=(const bigint &v)
    {
        *this = *this + v;
    }
    void operator-=(const bigint &v)
    {
        *this = *this - v;
    }
    void operator*=(const bigint &v)
    {
        *this = *this * v;
    }
    void operator/=(const bigint &v)
    {
        *this = *this / v;
    }
 
    bool operator<(const bigint &v) const
    {
        if (sign != v.sign)
            return sign < v.sign;
        if (a.size() != v.a.size())
            return a.size() * sign < v.a.size() * v.sign;
        for (int i = a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }
 
    bool operator>(const bigint &v) const
    {
        return v < *this;
    }
    bool operator<=(const bigint &v) const
    {
        return !(v < *this);
    }
    bool operator>=(const bigint &v) const
    {
        return !(*this < v);
    }
    bool operator==(const bigint &v) const
    {
        return !(*this < v) && !(v < *this);
    }
    bool operator!=(const bigint &v) const
    {
        return *this < v || v < *this;
    }
 
    void trim()
    {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            sign = 1;
    }
 
    bool isZero() const
    {
        return a.empty() || (a.size() == 1 && !a[0]);
    }
 
    bigint operator-() const
    {
        bigint res = *this;
        res.sign = -sign;
        return res;
    }
 
    bigint abs() const
    {
        bigint res = *this;
        res.sign *= res.sign;
        return res;
    }
 
    long long longValue() const
    {
        long long res = 0;
        for (int i = a.size() - 1; i >= 0; i--)
            res = res * base + a[i];
        return res * sign;
    }
 
    friend bigint gcd(const bigint &a, const bigint &b)
    {
        return b.isZero() ? a : gcd(b, a % b);
    }
    friend bigint lcm(const bigint &a, const bigint &b)
    {
        return a / gcd(a, b) * b;
    }
 
    void read(const string &s)
    {
        sign = 1;
        a.clear();
        int pos = 0;
        while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+'))
        {
            if (s[pos] == '-')
                sign = -sign;
            ++pos;
        }
        for (int i = s.size() - 1; i >= pos; i -= base_digits)
        {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            a.push_back(x);
        }
        trim();
    }
 
    friend istream &operator>>(istream &stream, bigint &v)
    {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }
 
    friend ostream &operator<<(ostream &stream, const bigint &v)
    {
        if (v.sign == -1)
            stream << '-';
        stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int)v.a.size() - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.a[i];
        return stream;
    }
 
    static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits)
    {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0] = 1;
        for (int i = 1; i < (int)p.size(); i++)
            p[i] = p[i - 1] * 10;
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int i = 0; i < (int)a.size(); i++)
        {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits)
            {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int)cur);
        while (!res.empty() && !res.back())
            res.pop_back();
        return res;
    }
 
    typedef vector<long long> vll;
 
    static vll karatsubaMultiply(const vll &a, const vll &b)
    {
        int n = a.size();
        vll res(n + n);
        if (n <= 32)
        {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }
 
        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());
 
        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);
 
        for (int i = 0; i < k; i++)
            a2[i] += a1[i];
        for (int i = 0; i < k; i++)
            b2[i] += b1[i];
 
        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < (int)a1b1.size(); i++)
            r[i] -= a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            r[i] -= a2b2[i];
 
        for (int i = 0; i < (int)r.size(); i++)
            res[i + k] += r[i];
        for (int i = 0; i < (int)a1b1.size(); i++)
            res[i] += a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            res[i + n] += a2b2[i];
        return res;
    }
 
    bigint operator*(const bigint &v) const
    {
        vector<int> a6 = convert_base(this->a, base_digits, 6);
        vector<int> b6 = convert_base(v.a, base_digits, 6);
        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());
        while (a.size() < b.size())
            a.push_back(0);
        while (b.size() < a.size())
            b.push_back(0);
        while (a.size() & (a.size() - 1))
            a.push_back(0), b.push_back(0);
        vll c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for (int i = 0, carry = 0; i < (int)c.size(); i++)
        {
            long long cur = c[i] + carry;
            res.a.push_back((int)(cur % 1000000));
            carry = (int)(cur / 1000000);
        }
        res.a = convert_base(res.a, 6, base_digits);
        res.trim();
        return res;
    }
};
 
int main()
{
    bigint first, second, temp;
    first = 1;
    second = 1;
    int i = 3;
    cout << 1 << " " << first << "\n";
    cout << 2 << " " << second << "\n";
    while (i < 1000)
    {
        i++;
        temp = first + second;
        cout << i << " " << temp << "\n";
        first = second;
        second = temp;
    }
}

Dưới đây là giá trị của số Fibo thứ 1000:

 
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626

+ In Đảo Ngược Một Số Nguyên Dương N

Hướng dẫn cách tìm số đảo ngược trong C. Bạn sẽ học được cách tạo hàm tìm số đảo ngược trong C sau bài học này.

Bài toán tìm số đảo ngược trong C

Tìm số đảo ngược trong C là bài toán nhập vào một số nguyên dương n từ bàn phím. In ra số đảo ngược của số n vừa nhập.

Ví dụ chúng ta nhập số 1234 thì sẽ thu về số 4321 chẳng hạn.

Mặc dù không không có ý nghĩa về mặt ứng dụng nhưng đây là một bài toán căn bản vô cùng hay giúp chúng ta rèn luyện lập trình bằng ngôn ngữ C.

Tìm số đảo ngược trong C

Cách tìm số đảo ngược trong C rất đơn giản, chúng ta viết lại từng hàng trong số theo thứ tự ngược lại là xong.

Vậy thì chúng ta sẽ viết ngược như thế nào?

Giả sử số đã cho là n = 1234. Chúng ta có thể biểu diễn số này dưới dạng tổng các lũy thừa của 10 như sau:

n = 1x104 + 2x103 + 3x102 + 4x101

Để biểu diễn số này theo cách ngược lại, chúng ta sẽ giữ nguyên phần lũy thừa của 10 và viết ngược lại từng chữ số trong tổng như sau:

n = 4x104 + 3x103 + 2x102 + 1x101

Để tìm ra được từng chữ số trong hàng thập phân như trên, chúng ta sẽ chia lần lượt số đã cho cho các luỹ thừa của 10 để tìm phần dư là xong.

Chúng ta sẽ sử dụng vòng lặp while và viết hàm để thực hiện xử lý đảo ngược số ở trên như sau:

/*Hàm tìm số đảo ngược trong C*/
int reverse_num(int n){ 
  int reverse = 0; 
  while (n > 0) {
    reverse = reverse * 10 + n % 10;
    n /= 10;
  }
  return reverse;
}

Chúng ta có thể gọi hàm này và sử dụng trong chương trình nhập vào một số nguyên dương n từ bàn phím. In ra số đảo ngược của số n vừa nhập trong C như sau:

#include <stdio.h>

/*Hàm tìm số đảo ngược trong C*/
int reverse_num(int n){ 
  int reverse = 0; 
  while (n > 0) {
    reverse = reverse * 10 + n % 10;
    n /= 10;
  }
  return reverse;
}

int main(void){
    int n;
 
    printf(">> nhap mot so nguyen duong: ");
    scanf("%d",&n);

    int result = reverse_num(n);
    printf("So dao nguoc: %d\n",result );

    return 0;
}

Màn hình nhập liệu và kết quả tìm số đảo ngược trong C sẽ như sau:

>> nhap mot so nguyen duong: 1234
So dao nguoc: 4321

>> nhap mot so nguyen duong: 23456789
So dao nguoc: 98765432

+ In Ra Dạng Nhị Phân Của Số Nguyên Dương N

Chắc hẳn ai học về giải thuật cũng đã từng nghe qua và làm về bài toán đưa ra chuỗi nhị phân độ dài N rồi, nếu bạn mới bắt đầu học hoặc đã bỏ lỡ qua bài toán thú vị này thì cũng đừng lo, vì trong bài viết này mình sẽ giới thiệu cho tất cả các bạn về bài toán này nhé.

Chuỗi nhị phân là gì?

Khái niệm về chuỗi nhị phân

Hệ nhị phân (hay hệ đếm cơ số hai hoặc mã nhị phân) là một hệ đếm dùng hai ký tự để biểu đạt một giá trị số, bằng tổng số các lũy thừa của 2. Hai ký tự đó thường là 0 và 1, chúng thường được dùng để biểu đạt hai giá trị hiệu điện thế tương ứng (có hiệu điện thế, hoặc hiệu điện thế cao là 1 và không có, hoặc thấp là 0). Do có ưu điểm tính toán đơn giản, dễ dàng thực hiện về mặt vật lý, chẳng hạn như trên các mạch điện tử, hệ nhị phân trở thành một phần kiến tạo căn bản trong các máy tính đương thời.

Ví dụ 0, 1, 0000, 0001, 010101, 00011100 là các chuỗi nhị phân

Bài toán đưa ra chuỗi nhị phân độ dài N

Chắc hẳn ai học về giải thuật cũng đã từng nghe qua và làm về bài toán đưa ra chuỗi nhị phân độ dài N rồi, nếu bạn mới bắt đầu học hoặc đã bỏ lỡ qua bài toán thú vị này thì cũng đừng lo, vì ngay bây giờ mình sẽ giới thiệu về nó nhé.

Bài toán cụ thể như sau:

Nhập vào một số nguyên dương N (1 ≤ N ≤ 20) hãy đưa ra tất cả các chuỗi nhị phân độ dài N, một chuỗi ghi trên một dòng, các chuỗi được sắp xếp từ bé đến lớn theo thứ tự từ điển,

Ví dụ 1:

Input

Output

Ví dụ 2:

Input

Output

Ví dụ 3:

Input

Output

000

001

010

011

100

101

110

111

Bài toán khá là thú vị đúng không nào, đã có ai có ý tưởng làm bài này chưa? hãy thử làm nó nhé, nếu bạn đã làm xong hoặc chưa biết làm thì cũng xem thử mình đã xử lý bài toán này bằng cách nào nhé.

Một số thuật toán đưa ra chuỗi nhị phân độ dài N

Biến đổi số thành chuỗi nhị phân

Thực chất các chuỗi nhị phân độ dài N lần lượt là biểu diễn nhị phân của các số thập phân từ 0 đến 2N-1.

Ví dụ 0 = 0(2), 1 = 1(2), 2 = 10(2), 7 = 111(2).

Việc cần làm của chúng ta rất đơn giản đó là chỉ cần chuyển đổi các số tự nhiên từ 0 đến 2N-1 sang chuỗi nhị phân là được (chú ý nhớ chèn các ký tự ‘0’ vào các chuỗi nhị phân để độ dài của chuỗi nhị phân đủ N).

Để chuyển một số tự nhiên sang chuỗi nhị phân ta có thể làm như sau:

In ra dạng nhị phân của số nguyên dương n

string decToBin(int n){
    string ans = "";
    while (n > 0) {
        ans = char (n % 2 + '0') + ans;
        n /= 2;
    }
    while (ans.length() < N)
        ans = "0" + ans;
    return ans;
}

Ta sẽ chia N cho 2 cho đến khi kết quả bằng 0, mỗi lần chia như vậy ta lưu lại số dư của N cho 2, chuỗi nhị phân của N chính là chuỗ số dư được đọc ngược.

Source code:

#include <iostream>
#include <math.h>
 
using namespace std;
 
int N;
 
string decToBin(int n){
    string ans = "";
    while (n > 0) {
        ans = char (n % 2 + '0') + ans;
        n /= 2;
    }
    while (ans.length() < N)
        ans = "0" + ans;
    return ans;
}
 
int main(){
    cin >> N;
    int N_2 = pow(2, N);
    for (int i = 0; i < N_2; i++)
        cout << decToBin(i) << endl;
}

Đệ quy quay lui

Với bài này ta có thể dùng phương pháp đệ quy, hiểu đơn giản là chúng ta cần dùng N vòng for lồng nhau, mỗi vòng for biến chạy sẽ chạy từ 0 đến 1.

phương pháp này để các bạn luyện tập đệ quy rất tốt, nhưng mình không khuyến khích các bạn dùng đệ quy trong khi nó có thể làm theo cách khác nha.

Source code:

#include <iostream>
 
using namespace std;
 
int N;
 
int x[100];
 
void in(int x[]){
    for (int i = 1; i <= N; i++)
        cout << x[i];
    cout << endl;
}
 
void deQuy(int i){
    for (int j = 0; j <= 1; j++){
        x[i] = j;
        if (i == N)
            in(x);
        else
            deQuy(i + 1);
        
    }
}
 
int main(){
    cin >> N;
    deQuy(1);
}

Phương pháp sinh

Ta thấy rằng nếu lấy lần lượt các chuỗi nhị phân độ dài N – 1, sau đó thêm ký tự 0 hoặc 1 vào cuối chuỗi đó, ta sẽ được 2 chuỗi nhị phân độ dài N.

Ví dụ như các chuỗi nhị phân độ dài 2 có các chuỗi là “00”, “01”, “10”, “11”.

Với chuỗi “00” khi ta thêm vào cuối nó ký tự ‘0’ hoặc ‘1’ ta có chuỗi “000” và “001”.

Tương tự với chuỗi “01” ta sẽ có chuỗi “010” và “011”.

Tương tự với chuỗi “10” ta sẽ có chuỗi “100” và “101”.

Tương tự với chuỗi “11” ta sẽ có chuỗi “110” và “111”.

Như vậy chỉ cần 2 ký tự “0” và “1” ta có thể sinh ra các chuỗi nhị phân độ dài N.

Source code:

#include <iostream>
#include <math.h>
 
using namespace std;
 
int N;
 
string a[100009];
 
int main(){
    cin >> N;
    int n = 2;
    a[0] = "0";
    a[1] = "1";
    int k = 0;
    while (a[k].length() < N){
        a[n++] = a[k] + "0";
        a[n++] = a[k] + "1";
        k++;
    }
    for (int i = k; i < n; i++)
        cout << a[i] << endl;
}

Tìm chuỗi nhị phân tiếp theo

Với phương pháp này ta sẽ tìm chuỗi nhị phân tiếp theo khi biết được chuỗi nhị phân trước đó, ví dụ tiếp theo của chuỗi “101” là “110”, tiếp theo của “111” là “1000”, vậy là sao làm được như vậy.

Cách làm sẽ là với chuỗi nhị phân S, để tìm chuỗi nhị phân tiếp theo của S ta sẽ làm như sau.

– Tìm vị trí index là vị trí của bit khác ‘0’ cuối cùng của S.

– Thay thì bit thứ index từ ‘0’ thành ‘1’.

– Biến đổi tất cả bit ‘1’ thành ‘0’ từ vì trí index + 1 đến hết chuỗi.

Ví dụ:

Với chuỗi S = “10011”, thì ta có bit bằng ‘0’ cuối cùng là bit thứ 3, ta biến đổi bit 3 thành 1 và bit 4, bit 5 thành 0, ta sẽ được chuỗi nhị phân tiếp theo của S là “10100”.

Source code:

#include <iostream>
#include <math.h>
 
using namespace std;
 
int N;
 
string next(string s){
    for (int i = s.length() - 1; i >= 0; i--)
        if (s[i] == '0'){
            s[i] = '1';
            return s;
        } else
            s[i] = '0';
    return "";
}
 
int main(){
    cin >> N;
    string s = "";
    for (int i = 0; i < N; i++)
        s = "0" + s;
    for (int i = 0; i < pow(2, N); i++){
        cout << s << endl;
        s = next(s);
    }
}

+ Tính N Giai Thừa Trong C/C++ Bằng Đệ Quy Và Khử Đệ Quy

Bài viết chia sẻ thuật toán và cách tính n giai thừa trong C/C+ sử dụng hai phương pháp đệ quy và khử đệ quy. Một bài toán hay dành cho các bạn học lập trình.

Giới thiệu bài toán

Giai thừa là một bài toán kinh điển trong lập trình, nó là một bài toán mà mình tin là bất kì bạn nào mới học đều phải trải qua. Bài toán này sẽ giúp bạn hiểu được thuật toán đệ quy hoặc sử dụng thành thạo vòng lặp.

Đề bài đại loại có thể tóm tắt lại như sau: Tính n giai thừa và in kết quả ra màn hình, n nhập vào từ bàn phím.

Trước khi giải quyết bài toán, chúng ta cần hiểu định nghĩa về n! (n là một số nguyên dương): n giai thừa là tích của n số nguyên dương đầu tiên.

Công thức tổng quát: n! = n*(n-1)!

Trường hợp đặc biệt: 0! = 1

Tính N giai thừa trong CC++ bằng đệ quy và khử đệ quy

Tính giai thừa sử dụng vòng lặp

Cách tính đầu tiên này sẽ đơn giản hơn cách sử dụng đệ quy. Và nó được gọi là cách khử đệ quy bởi vì nó tránh được việc phải dùng đến đệ quy. Tùy từng trường hợp mà đệ quy và khử đệ quy có ưu điểm khác nhau.

Tư tưởng giải quyết:

Khai báo một biến để lưu giá trị và gán nó bằng 1: giai_thua = 1

Sử dụng vòng lặp chạy i từ 1 đến n sau đó gán: giai_thua = giai_thua*i

Code C/C++:

// giai thua su dung vong lap
int giaithualap(int n){
    int giai_thua = 1;
    for (int i = 1; i <= n; i++)
        giai_thua = giai_thua * i;
    return giai_thua;
}

Tính giai thừa sử dụng đệ quy

Để hiểu rõ hơn thuật toán này trước tiên bạn nên tìm hiểu thuật toán đệ quy.

Ở bài này, ta có công thức tổng quát n giai thừa là : n!=n*(n-1)!

Chính vì thế, ta cũng sử dụng lệnh truy hồi dựa trên công thức này.

Điều kiện dừng ở đây là khi n =1 (vì ta tính tích các số bắt đầu từ 1)

Code C/C++:

// tinh giai thua su dung de quy
int factorial(int n){
    if(n==1)
        return 1;
    return(n*factorial(n-1));
}

Đánh giá cả 2 cách: Cách sử dụng đệ quy để tính giai thừa có vẻ chuyên nghiệp hơn. Tuy nhiên cách sử dụng vòng lặp có tốc độ nhanh không kém đệ quy, thậm trí là nhanh hơn.

Trong cách bài toán thực tế, nếu để lựa chọn thì các lập trình viên sẽ sử dụng cách 1 để hạn chế ít nhất việc sử dụng đệ quy.

Chú ý: Ở đây kiểu dữ liệu của hàm mình để là kiểu int, chính vì thế chỉ có thể chạy khi n <= 19 (nếu quá thì sẽ vượt kích thước của kiểu int dẫn đến sai kết quả). Nếu bạn muốn chạy được số lớn hơn thì nên để kiểu double (max n 170).

Code full bài toán nhập N và tính đệ quy:

/*  Bai toan tinh N giai thua trong C++
    By: https://duongdinh24.com/
    github: https://github.com/duongdinh24/
*/
#include<bits/stdc++.h>
using namespace std;
// n! su dung de quy
int factorial(int n){
    if(n==1)
        return 1;
    return(n*factorial(n-1));
}
// nn! Khu de quy su dung vong lap
int giaithualap(int n){
    int giai_thua = 1;
    for (int i = 1; i <= n; i++)
        giai_thua = giai_thua * i;
    return giai_thua;
}
int main(){
    int n;
    cout<<"Nhap n: "; cin>>n;
    cout<<"Ket qua "<<n<<"!: "<<factorial(n);   // De quy
//    cout<<"Ket qua "<<n<<"!: "<<giaithualap(n);  // Khu de quy
}

The post Đệ Quy Trong C++ first appeared on Techacademy.

source https://techacademy.edu.vn/de-quy-trong-c/