Thuật toán « MicrosoftTech.Net

Bài toán Đệ Quy

Bài toán Đệ quy trong Lập trình | Lập trình Csharp | MicrosoftTech.Net

1. Giới thiệu Bài toán Đệ quy Đệ quy là một kỹ thuật lập trình khá hữu dụng trong nhiều trường hợp. Xét về bản chất, đệ quy chính là những vòng lặp nhưng dĩ nhiên đệ quy sẽ có những ưu điểm so với vòng lặp thông thường và khi sử dụng đệ quy sẽ đem lại kết quả tối ưu hơn với những cách thực hiện đơn giản hơn. Và tất nhiên những bài toán giải được bằng đệ quy thì có thể giải bằng vòng lặp thông thường (Quy trình khử đệ quy) (Có thể không tối ưu bằng).

Hình phía trên nhằm minh họa để ta dễ hiểu hơn về đệ quy. Hình được tạo ra khi tôi chạy chương trình team viewer trên 2 máy tính, trên máy tính này sẽ thấy màn hình máy tính kia và ngược lại… cứ như thế bên trong mỗi màn hình lại có chứa màn hình khác. Quá trình lặp đi lặp lại dường như đến vô tận (có thể xem quá trình này dừng lại khi kích thước khung hình được tạo ra quá nhỏ, không đủ pixel để hiển thị chi tiết) Ví dụ thường thấy là khi ta để 2 tấm gương phản chiếu hướng vào nhau, nhìn trong tấm này sẽ thấy hình ảnh tấm kia, cứ như vậy số lượng hình ảnh sẽ tăng lên… đến vô tận.

2. Khái niệm Đệ quy Đến đây chắc …..

Chuyên mục: Cấu trúc dữ liệu, Thuật toán
Từ khóa: , ,

Thuật toán Sắp xếp Nổi bọt– Bubble Sort

Thuật toán sắp xếp Nổi bọt - Bubble Sort | MicrosoftTech.Net

1. Bài toán sắp xếp Nổi bọt

Như đã biết ở bài viết trước về thuật toán Sắp xếp chọn ta thấy rằng sau mỗi vòng lặp ta lựa được một phần tử nhỏ nhất đưa về đầu danh sách, các phần tử còn lại hầu như không ảnh hưởng. Ta thấy rằng kết quả của vòng lặp trước không ảnh hưởng đến vòng lặp sau. Trong bài viết này chúng ta sẽ xét tới thuật toán sắp xếp Nổi bọt – Cải tiển hơn so với Thuật toán sắp xếp chọn.

Với thuật toán này, sẽ có 2 vòng lặp lồng nhau. Tại mỗi vòng lặp con sẽ chạy từ cuối danh sách trở về đầu danh sách. tại mỗi bước sẽ so sánh 2 phần tử kế cận nhau nếu phần tử nào nhỏ hơn sẽ được đảo về phía trước. Trong mỗi vòng lặp con, phần tử nhỏ nhất sẽ lần lượt được đưa về đầu dòng theo phương pháp tráo đổi – Đúng với tư tưởng “Nổi bọt” phần tử nhỏ sẽ dần được nổi lên trên cùng. Đặc điểm tối ưu hơn so với Sắp xếp chọn là tại mỗi vòng lặp con do có quá trình tráo đổi phần tử nhỏ về đầu dãy nên các phần tử lớn dần được đưa về cuối dãy và đồng thời những giá trị nhỏ cũng dần được đưa về đầu dãy. Đối với phương pháp sắp xếp chọn có tối …..

Chuyên mục: Cấu trúc dữ liệu, Thuật toán
Từ khóa: , , , ,

Thuật toán Sắp xếp chọn - Selection Sort

Thuật toán sắp xếp chọn - Selection Sort | MicrosoftTech.Net

1. Bài toán sắp xếp chọn

Trong quá trình thao tác dữ liệu, sẽ có những trường hợp cần phải sắp xếp dữ liệu trong danh sách theo một thứ tự nào đó theo các yêu cầu. Tùy từng loại cấu trúc dữ liệu khác nhau sẽ có phương án sắp xếp tối ưu cho cấu trúc dữ liệu đó. Xét giới hạn trong kiểu dữ liệu danh sách đơn giản là mảng các phần tử, Sắp xếp chọn – Selection Sort là một kiểu sắp xếp đơn giản nhất, thuật toán rõ ràng, dễ hiểu.

Tư tưởng của của thuật toán này như sau: Sẽ có n – 1 vòng lặp duyệt qua danh sách (n là tổng số phần tử), tại mỗi vòng lặp sẽ chọn phần tử nhỏ nhất đưa lên đầu danh sách. Như vậy sau vòng lặp thứ nhất thu được phần tử nhỏ nhất tại vị trí đầu tiên, sau vòng lặp thứ 2 thu được phần tử nhỏ nhất trong danh sách còn lại (không tính phần tử thứ 2) tại vị trí thứ hai… cứ như vậy cho đến vòng lặp thứ n – 1 sẽ còn 2 phần tử, ta lấy phần tử nhỏ hơn đưa vào vị trí thứ n – 1 và tất nhiên vị trí cuối cùng sẽ là phần tử lớn nhất. Tại mỗi vòng lặp để xác định phần tử có giá trị nhỏ nhất ta cần dùng thêm một …..

Chuyên mục: Cấu trúc dữ liệu, Thuật toán
Từ khóa: , ,

Bài toán Sinh giá trị Ngẫu nhiên

Khởi tạo Giá trị ngẫu nhiên trong Csharp | MicrosoftTech.Net

1. Hàm sinh ngẫu nhiên trong csharp Trong lập trình csharp hỗ trợ đối tượng random để sinh ngẫu nhiên một giá trị số nguyên, đi kèm là phương thức .Next(); để sinh giá trị ngẫu nhiên theo điều kiện nhất định. Phương thức .Next() được overload thành 3 dạng như ví dụ bên dưới.

Dạng thứ nhất: Sinh ngẫu nhiên một giá trị số nguyên int. Số nguyên int trong lập trình csharp có giá trị từ 0 -> 2^31-1. (2^31-1 = 2148486647) Dạng thứ hai: Sinh ngẫu nhiên một giá trị số nguyên từ 9 đến giá trị cho trước. Dạng thứ ba: Sinh ngẫu nhiên một giá trị số nguyên trong khoảng 2 số nguyên cho trước.

2. Sinh ngẫu nhiên một dãy số tăng dần Trong ví dụ này ta sẽ sinh một mảng số nguyên 1 phần tử có giá trị tăng dần. Phương pháp: Phần tử đầu tiên sẽ được sinh ngẫu nhiên, các phần tử tiếp theo sẽ bằng phần tử trước đó cộng thêm một lượng ngẫu nhiên; Như vậy đảm bảo phần tử sau sẽ luôn lớn hơn phần tử cho trước. Ngược lại nếu muốn sinh một dãy giảm dần, trước tiên ta sinh một dãy tăng sau đó tiến hành reverse để có dãy giảm dần. Nếu như làm theo phương pháp phần tử sau bằng phần tử trước trừ đi một lượng ngẫu nhiên thì dễ xảy ra trường hợp sinh ra ra …..

Chuyên mục: Bài toán Liệt kê, Thuật toán
Từ khóa: , , , ,

Bài toán Sinh dãy số Fibonaci

Lập trình sinh dãy Fibonaci | MicrosoftTech.Net

Đến với bài viết hôm nay chúng ta sẽ tìm hiểu một dãy số có tính chất rất thú vị, thu hút sự chú ý của nhiều người trong các thập kỷ qua, từ dãy số này có thể phát triển thành những dãy số khác với tính chất tương tự. Dãy số mà tôi đang nói tới ở đây là dãy: Fibinaci. Dãy số Fibonaci là dãy số nguyên tăng dần với 2 phần tử đầu tiên có giá trị bằng 1. Các phần tử tiếp theo có giá trị bằng 2 tổng của 2 phần tử liền trước nó.

Dãy số Fibonaci Hình bên dưới minh họa 7 phần tử đầu tiên trong dãy số Fibonaci Làm việc với Fibonaci Thao tác với dãy số Fibonaci thường ta chỉ quan tâm đến 2 phương thức chính: Lấy giá trị phần tử thứ n và Xuất ra danh sách n phần tử đầu tiên. Nhìn vào cách định nghĩa giá trị cho phần tử trong dãy Fibonaci ta thấy phần tử sau có kết quả phụ thuộc vào 2 phần tử trước. Như vậy có thể lấy giá trị của một phần tử bất kỳ bằng giá trị của 2 phần tử trước nó. Tới đây ta thấy được phương pháp đệ quy trong việc tìm giá trị của 1 phần tử. Phương thức getValues(int n) là một hàm đệ quy. Nếu giá trị n là 1 hoặc 2 thì trả về kết quả 1. …..

Chuyên mục: Bài toán Liệt kê, Thuật toán
Từ khóa: , , , ,

Bài toán Sinh dãy số Nhị phân

Bài toán Sinh dãy Nhị phân | MicrosoftTech.Net

1. Bài toán Bài toán hôm nay sẽ sẽ tìm hiểu phương pháp để sinh ra dãy tất cả các số nhị phân với chiều dài cho trước. Số nhị phân là số được tạo nên bởi 2 ký tự suy nhất là 0 và 1. Ví dụ bên mẫu bên trên liệt kê tất cả các số nhị phân với chiều dài bằng 3. Trong ví dụ này sẽ có 8 kết quả thỏa mãn yêu cầu, giá trị nằm trong khoảng từ 000 tới 111 (Số nhị phân). Và cũng rất dễ dàng ta có thể tính được số lượng phần tử trong danh sách cần tìm. Nếu gọi n là chiều dài của số nhị phân và len là tổng số phần tử thì len = 2^n.

2. Minh họa bài toán với mã nguồn Csharp Bên dưới là minh họa tôi viết bằng Csharp. Sẽ không tốt lắm khi minh họa thuật toán bằng ngôn ngữ Csharp (Tốt nhất là C++), nhưng trong khuôn khổ website này những bài minh họa tôi chỉ sử dụng ngôn ngữ Csharp và cố gắng đưa vào điểm mạnh của Csharp – Lập trình Hướng đối tượng vào trong từng ví dụ để tập dần thói quen trong Lập trình hướng đối tượng với Csharp, thiết nghĩ đây cũng là điểm tốt.

Trong ví dụ, tôi xây dựng class DemoClass thực hiện trọn gói yêu cầu của đề bài. Khi khởi tạo đối tượng …..

Chuyên mục: Bài toán Liệt kê, Thuật toán
Từ khóa: , , , ,