test2: Thuật toán

Hiển thị các bài đăng có nhãn Thuật toán. Hiển thị tất cả bài đăng

Thứ Tư, 19 tháng 3, 2014

Bàn_luận_ngôn_ngữ_lập_trình????

Thực chất ngôn ngữ k quan trọng lắm ..
Bởi về cơ bản bỏ tí thời gian thì có thể chuyển từ ngôn ngữ này qua ngôn ngữ khác được.
Quan trọng là nắm nền tản tới đâu.
Còn làm việc thì chuyên sâu 1 ngôn ngữ là tốt nhất.
1. Tại sao ở trường học lại dạy nhiều ngôn ngữ?
Đơn giản vì không biết sinh viên ra trường làm việc với ngôn ngữ nào cả!
Dạy hết - dạy mức cơ bản để hình dung ngôn ngữ đó là gì thôi.Còn dùng ngôn ngữ đó để đi làm thì ở trường kiến thức vẫn không đủ.
2. Tại sao thầy cô không dạy chủ yếu một ngôn ngữ đã nắm hết rồi sau đó có thể học ngôn ngữ khác. vì mỗi ngôn ngữ đều liên quan mà, chỉ cần nắm là có thể??
Đơn giản vì thời gian không đủ. + không 1 lập trình viên nào dám nói là mình đã nắm hết 1 ngôn ngữ nào cả!
P/S: Với hiểu biết của ad là thế :))

Trao đổi tại đây

Thuật toán Quick Sort – Sắp xếp nhanh

By Unknown 09:57 Thuật toán No comments

Thuật toán Quick Sort – Sắp xếp nhanh

by lhchuong

1. Mô tả:

- Quick Sort hay còn gọi là thuật toán sắp xếp theo kiểu phân chia, là thuật toán có khả năng sắp xếp 1 mảng các phần tử 1 cách nhanh nhất trong tất cả các thuật toán sắp xếp. Sở dĩ tốc độ thực hiện là nhanh nhất vì nó phân chia thành nhiều vùng nhỏ rồi mới thực hiện công việc sắp xếp.

- Cách sắp xếp như Hình 1, trong đó phần khoanh đỏ là mốc, mũi tên chỉ 2 phần tử vừahoán đổi vị trí cho nhau:

Hình 1

2. Cài đặt thuật toán:

- Khởi tạo các phần tử trong mảng Hình 2:

Hình 2

- Hàm hoán đổi 2 biến Hình 3:

Hình 3

- Cài đặt Quick Sort Hình 4:

Hình 4

- Gọi phương thức Hình 5:

Hình 5

Thuật toán Dijkstra – Tìm đường đi ngắn nhất dựa vào trọng số

By Unknown 09:56 Thuật toán No comments

Thuật toán Dijkstra – Tìm đường đi ngắn nhất dựa vào trọng số

by lhchuong

1. Mô tả:

- Đồ thị sẽ được tổ chức như Hình 1:

Hình 1

- Chúng ta sẽ thực hiện việc tìm đường đi ngắn nhất dựa vào trọng số từ đỉnh 1 -> đỉnh 10.

2. Cài đặt:

Chúng ta sẽ tiến hành cài đặt bằng ngôn ngữ C++

- Hình 2: tiến hành lưu đồ thị trên theo ma trận kề, với 10 đỉnh

Hình 2

- Hình 3: Gọi hàm trong main, ở đây 0 là đỉnh bắt đầu và 9 là đỉnh kết thúc

Hình 3

- Hình 4: Hàm dijkstra + input: đỉnh bắt đầu và đỉnh kết thúc
+ output: tổng trọng số và thứ tự đi giữa các đỉnh từ đỉnh bắt đầu đến đỉnh kết thúc.

Hình 4

- Hình 5: Hàm printPath
+ input: đỉnh bắt đầu và đỉnh kết thúc, mảng lưu thứ tự các đỉnh
+ ouput: in đường đi đã được thiết lập từ đỉnh bắt đầu và đỉnh kết thúc

Hàm 5

Như vậy là tôi vừa hoàn thành việc mô tả và cài đặt thuật toán Dijkstra, trong bài viết tôi không giải thích chi tiết các bước vì đã có rất nhiều trong các diễn đàn lớn…

Thuật toán BFS – Tìm kiếm theo chiều rộng

By Unknown 09:55 Thuật toán No comments

Thuật toán BFS – Tìm kiếm theo chiều rộng

by lhchuong

1. Mô tả

- Đây là thuật toán tìm các đỉnh bằng cách duyệt theo chiều rộng.

- Xuất phát từ 1 đỉnh và đi tới các đỉnh kề nó, tiếp tục cho đến khi không còn đỉnh nào có thể đi.

- Trong quá trình đi đến đỉnh kề, tiến hành lưu lại đỉnh cha của đỉnh kề để khi đi ngược lại từ đỉnh Kết thúc đến đỉnh Xuất phát, ta có được đường đi ngắn nhất.

- Sở dĩ thuật toán này tìm được đường đi ngắn nhất là nhờ vào cơ chế tô màu và lưu đỉnh cha. Quá trình tô màu khiến 1 đỉnh không thể xét 2 lần trở lên và có thể xem được đường đi từ đỉnh Kết Thúc đến đỉnh Xuất phát dựa vào việc lưu đỉnh cha.

- Sau đây là minh họa về thuật toán:

+ Hình 1 : Xuất phát từ đỉnh 1

Hình 1

+ Hình 2 : Đi đến đỉnh 2, như vậy nút 1 là nút cha của nút 2

Hình 2

+ Hình 3 : Đã đi hết tất cả các đỉnh kề của đỉnh 1, tiến hành bôi đen đỉnh 1

Hình 3

+ Hình 4: Xuất phát từ đỉnh 2, chọn đỉnh 3, nút cha của đỉnh 3 là đỉnh 2

Hình 4

+ Hình 5 : Xuất phát từ đỉnh 2, bôi đen đỉnh 4, nút cha của đỉnh 4 là đỉnh 2

Hình 5

+ Hình 6 : Đã đi hết tất cả các đỉnh kề của đỉnh 2, tiến hành bôi đen đỉnh 2

Hình 6

+ Hình 7 : Xuất phát tử đỉnh 3, đi đến đỉnh 7, như vậy đỉnh 3 là đỉnh cha của đỉnh 7

Hình 7

+ Hình 8 : Xuất phát từ đỉnh 3, đi đến đỉnh 5, như vậy đỉnh 3 là đỉnh cha của đỉnh 5

Hình 8

+ Hình 3 : Đã đi hết tất cả các đỉnh kề của đỉnh 3, tiến hành bôi đen đỉnh 3

Hình 9

+ Hình 10 : Xuất phát từ đỉnh 5, đi đến đỉnh 6, như vậy đỉnh 5 là đỉnh cha của đỉnh 6

Hình 10

+ Hình 11: Đã đi hết tất cả các đỉnh kề của đỉnh 5, tiến hành bôi đen đỉnh 5

Hình 11

+ Hình 12: Đã đi hết tất cả các đỉnh kề của đỉnh 7, tiến hành bôi đen đỉnh 7

Hình 12

+ Hình 13 : Đã đi hết tất cả các đỉnh kề của đỉnh6, tiến hành bôi đen đỉnh 6

Hình 13

- Như vậy ta vừa đi hết tất cả các đỉnh trong đồ thị, và mỗi lần đi đến đỉnh mới, ta đều lưu lại nút cha của đỉnh mới, dựa vào những đỉnh cha này, ta có liệt kê đường đi ngắn nhất bằng cách đi ngược từ đỉnh Kết thúc, đến đỉnh cha của đỉnh Kết thúc … rồi đến đỉnh cha của đỉnh tiếp theo … đến đỉnh Bắt đầu.

2. Cài đặt

- Hình 14: Cài đặt thuật toán BFS

Hình 14

- Hình 15: In đường đi từ đỉnh Xuất phát đến đỉnh Kết thúc

Thuật toán DFS – Tìm kiếm theo chiều sâu

By Unknown 09:43 Thuật toán No comments

Thuật toán DFS – Tìm kiếm theo chiều sâu

by lhchuong

1. Mô tả:

- Đây là thuật toán tìm các đỉnh bằng cách duyệt theo chiều sâu.

- Xuất phát từ 1 đỉnh và đi mãi cho đến khi không thể đi tiếp, sau đó đi về lại đỉnh đầu.
Trong quá trình quay lại:

+ nếu gặp đường đi khác thì đi cho đến khi không đi tiếp được nữa

+ nếu không tìm ra đường đi nào khác thì ngừng việc tìm kiếm.

- Trong quá trình đi đến đỉnh khác, thuật toán sẽ lưu lại đỉnh cha vừa đi qua để khi đi ngược lại từ đỉnh Kết thúc đến đỉnh Xuất phát, ta có thể xem được đường đi từ đỉnh Kết thúc đến đỉnh Bắt Đầu (có thể số lần đi không ít nhất, các bạn có thể tham khảo thuật toán BFS).

- Sở dĩ thuật toán này tìm được đường đi là nhờ vào cơ chế tô màu và lưu đỉnh cha. Quá trình tô màu khiến 1 đỉnh không thể xét 2 lần trở lên và có thể xem được đường đi từ đỉnh Kết Thúc đến đỉnh Xuất phát dựa vào việc lưu đỉnh cha.

- Sau đây là minh họa về thuật toán:

+ Hình 1 đi từ đỉnh bắt đầu, đi cho đến khi không đi được nữa.