Bài toán 8 hậu

1. Mô tả:

– Các yêu cầu của bài toán:
+ Không có đường chéo chính nào trên bàn cờ có 2 quân trở lên
+ Không có đường chéo phụ nào trên bàn cờ có 2 quân trở lên
+ Không có cột nào trên bàn cờ có 2 quân trở lên

Hình 1 – Trường hợp đúng trong bài toán 8 hậu:

Untitled

 

Hình 1

 – Về thuật toán thì các bạn có thể tìm thấy vô số trên các diễn đàn nên trong bài viết này tôi chỉ tập trung giải thích việc xác định đường chéo chính và đường chéo phụ của bài toán.

2. Cài đặt:

– Thuật toán khá đơn giản:

Untitled

 

3. Giải thích đường chéo chính:

Hình 2 – Mô tả chiều đường chéo chính

312px-Chessboard480.svg

Hình 2

Hình 3 – Chúng ta sẽ tìm cách xác định một đường chéo chính dựa vào chỉ số hàng i và chỉ số cột j. Trong hình, tất cả các ô nằm trong 1 đường chéo đều có tổng (i + j) bằng nhau:

312px-Chessboard480.svg

Hình 3

4. Giải thích đường chéo chính:

Hình 4 – Mô tả chiều đường chéo phụ

312px-Chessboard480.svg

Hình 4

Hình 5 – Chúng ta sẽ tìm cách xác định một đường chéo phụ dựa vào chỉ số hàng i và chỉ số cột j. Trong hình, tất cả các ô nằm trong 1 đường chéo phụ đều có biểu thức (i – j + 8) bằng nhau:

312px-Chessboard480.svg

Hình 5

Như vậy tôi đã giải thích vì sao lại dùng biểu thức (i + j) và (i – j + n) để xác định chéo chính và chéo phụ trong bài toán 8 hậu. Chúc các bạn thành công!

Advertisements

[Lập trình đa nền tảng 2015] – Ứng dụng VietTraffic đạt giải cao nhất cuộc thi

– Vừa qua, SHTP – Trung Tâm Đào Tạo Khu Công Nghệ Cao đã tổ chức cuộc thi Lập Trình Ứng Dụng Đa Nền Tảng 2015 ngày 24/04/2015, nhóm chúng tôi bao gồm 2 thành viên là Lê Hoàng Chương và Phan Thái An đã xuất sắc vượt qua 25 đội đến từ các trường Đại học khu vực thành phố Hồ Chí Minh để đạt giải cao nhất cuộc thi. Xem kết quả cuộc thi tại đây.

 11167964_709419179166399_7681997244594186795_n

 – Ứng dụng của chúng tôi có tên là VietTraffic, là ứng dụng giúp người tham gia giao thông tra cứu tình trạng giao thông trên thành phố tại nơi mà Camera giao thông được lắp đặt, các bạn xem DEMO tại đây.

 – Một số hình ảnh của ứng dụng VietTraffic:

first-screen search-router state-region state-result state-result-zoom update-region update-state

Thuật toán Kadane – Tìm tập hợp con có tổng lớn nhất

1. Giới thiệu:

–  Là thuật toán quy hoạch động có thể tìm ra tập hợp con có tổng lớn nhất từ tập hợp ban đầu một cách nhanh chóng, tốc độ thực hiện O(n).

– Chẳng hạn: A = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84} , nên tập hợp con có tổng hợp nhất là {59, 26, -53, 58, 97}

2. Hiện thực:

Hình 1 – Khai báo tập hợp ban đầu

1

Hình 1

Hình 2 – Định nghĩa hàm tìm tổng lớn nhất

1

Hình 2

Hình 3 – Cải tiến hàm để tìm phần tử đầu tiên và bắt đầu của tập con

1

Hình 3

Như vậy là tôi vừa hướng dẫn bạn cài đặt thuật toán Kadane tìm tập hợp con có tổng lớn nhất với tốc độ nhanh nhất có thể. Chúc các bạn thành công!

Big Number – Các thao tác cộng trừ nhân chia số nguyên lớn

1. Giới thiệu:

– Trong một vài trường hợp, bạn cần lưu một số nguyên cực kỳ lớn.

– Chẳng hạn: 123.456.789.123.456.789.123.456.789.123.456.789.123.456.789.123.456.789

– Bạn có bao giờ thắc mắc có kiểu dữ liệu nào có thể đáp ứng được chuyện đó?

– Kiểu int chỉ có thể biểu diễn một số nguyên khoảng 2,1 tỉ. Ngoài ra, chúng ta còn có kiểu “unsigned long long int” với việc có biểu diễn một số có 18  ký số. Trong đó, từ khóa “unsigned” nhầm mục đích chỉ biểu diễn số dương. Nếu không có từ khóa “unsigned” thì vấn đề gì xảy ra, bạn tự tìm hiểu nhé!

– Trong bài này, tôi sẽ hướng dẫn các bạn thực hiện các phép tính cơ bản + – * / giữa 2 “số nguyên“. Nhưng “số nguyên” mà tôi muốn nói là số rất lớn, có số lượng ký số lên đến hàng chục, hàng ngàn và thậm chí là hàng tỉ ký số.

2. Hiện thực: 

– Để sử dụng lớp vector, bạn cần thư viện <vector> và khai báo using namespace std

Hình 1 – Khởi tạo và xem kết quả sau khi khởi tạo

1

Hình 1

Hình 2 – Hàm khởi tạo một số

1

Hình 2

Hình 3 – Hàm loại bỏ các số 0 ở đầu

1

Hình 3

Hình 4 – Hàm in số nguyên

1

Hình 4

 – Sau đó, các bạn thử khởi tạo 2 số và in ra màn hình nhé.

 – Bây giờ chúng ta sẽ bắt đầu vào thực hiện các phép tính + – * /

Hình 5 – Phép cộng

1

Hình 5

Hình 6 – Phép trừ

1

Hình 6

Hình 7 – Phép nhân

1

Hình 7

Hình 10 – Phép chia

 – Trong 4 phép toán thì phép chia là phép dài dòng và phức tạp nhất

 – Phép chia cần đến hàm so sánh và phép trừ

Hình 8 – Thực hiện phép chia thủ công

 – Chúng ta sẽ thực hiện việc chia 2 số như cách mà chúng ta đã biết từ khi học cấp 1

phep-chia-2-so-thap-phan-cho-nhau-buoc-7

Hình 8

Hình 9 – Phép so sánh

1

Hình 9

1

Hình 10

Như vậy là tôi vừa hướng dẫn các bạn thực hiện các phép tính cơ bản giữa các số nguyên cực lớn. Các bạn hãy thử cải tiến các thuật toán trên bằng cách mỗi phần tử của 1 vector có thể lưu 9 ký số chứ không phải là 1 ký số như tôi đã trình bày. Nếu được, hãy kiểm tra tính đúng đắn của thuật toán và liên hệ tôi để cùng nhau thảo luận vấn đề này nhé 🙂

Thuật toán Eratosthenes – Tối ưu thuật toán sàng số nguyên tố

1. Giới thiệu:

– Thuật toán Eratosthenes là thuật toán cổ xưa của người Hy Lạp để tìm một lượng số nguyên tố trong một phạm vi nhất định.

– Trong trường hợp muốn tìm tất cả các số nguyên tố trong một phạm vi lớn, việc sử dụng thuật toán sàng Eratosthenes sẽ mang lại hiệu quả cao về tốc độ thực hiện.

– Các bước của thuật toán sàng Eratosthenes:

+ Bước 1: Khởi tạo một tập hợp các số từ 2 đến N, trong đó N là phạm vi cần tìm

+ Bước 2: Từ 2, ta sẽ đánh dấu tất cả các bội của 2 và các bội này phải < N, những số được đánh dấu không phải là số nguyên tố. Sau khi đánh dấu hết tất cả các bội của 2, ta tiến hành đánh dấu bội của 3, 5 …. ta bỏ qua số 4 vì nó là bội của 2 và đã được đánh dấu.

+ Bước 3: Những số còn lại không được đánh dấu là số nguyên tố.

2. Cài đặt:

Sau đây, tôi sẽ trình bày phần hiện thực thuật toán.
Thông thường, chúng ta sẽ duyệt lại tập hợp sau khi đã sàng lọc.
Trong phần này, tôi sẽ tối ưu thuật toán bằng cách vừa sàng vừa hiển thị kết quả để tăng tốc độ thuật toán.

 Hình 1 – Khởi tạo và gọi hàm:

1

Hình 1

Hình 2 – Cài đặt thuật toán Eratosthenes:

1

Hình 2

Hình 3 – Đánh dấu các bội của một số nguyên tố:

1

Hình 3

Như vậy là tôi vừa hướng dẫn các bạn cài đặt và tối ưu thuật toán Eratosthenes.

Chúc các bạn thành công!

Thuật toán Kruskal – Tìm cây bao trùm nhỏ nhất

1. Mô tả:

– Giống như Prim, thuật toán Kruskal cũng tìm cây khung nhỏ nhất nhưng không phụ thuộc vào điểm bắt đầu.

Hình 1, đồ thị như sau:

400px-Đồ_thị_G_trong_lý_thuyết_đồ_thị

Hình 1

 – Bước 1: lập bảng, liệt kê tăng dần theo trọng số của các cạnh.

Untitled

Bước 2: dựa vào thứ tự bảng trên để đánh giá cạnh đó có thuộc cây khung tối tiểu hay không. Một cạnh thõa điều kiện khi nó không góp phần tạo thành một chu trình với tất cả các cạnh đã tìm được.

 1-4-1: Ta nhận thấy cạnh 1-4 không tạo ra một chu trình nào. Vì vậy, thêm 1-4 vào tập hợp

1

Hình 2

 6-7-1: Ta nhận thấy cạnh 6-7 không tạo ra một chu trình nào. Vì vậy, thêm 6-7 vào tập hợp

2

Hình 3

 4-6-2: Ta nhận thấy cạnh 4-6 không tạo ra một chu trình nào. Vì vậy, thêm 4-6 vào tập hợp

3

Hình 4

 1-2-3: Ta nhận thấy cạnh 1-2 không tạo ra một chu trình nào. Vì vậy, thêm 1-2 vào tập hợp

4

Hình 5

1-6-3: Ta nhận thấy cạnh 1-6 tạo ra một chu trình. Không thêm vào tập hợp.

5

Hình 6

 2-3-4: Ta nhận thấy cạnh 2-3 tạo ra một chu trình. Không thêm vào tập hợp.

6

Hình 7

3-7-5: Ta nhận thấy cạnh 3-7 tạo ra một chu trình. Không thêm vào tập hợp.

7

Hình 8

5-6-5: Ta nhận thấy cạnh 5-6 không tạo ra một chu trình nào. Vì vậy, thêm 5-6 vào tập hợp

8

Hình 9

CÂY BAO TRÙM THU ĐƯỢC, Hình 10:

9

Hình 10

Nguồn từ: http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Kruskal

2. Cài đặt:

Bước 1, khai báo các biến, ta sẽ không sử dụng ma trận kề để lưu đồ thị, mà sẽ sử dụng danh sách các cạnh đã khai báo để lưu từng cạnh, vì vậy khi nhập dữ liệu vào, ta cần gán dữ liệu vào danh sách các cạnh:

Untitled

Bước 2, cài đặt thuật toán Kruskal:

Untitled

 – Hàm thực hiện sắp xếp các cạnh tăng dần theo trọng số:

Untitled

 – Hàm tìm nút cha của một đỉnh:

Untitled – Hàm thực hiện việc kết nối 2 nút lại với nhau:

Untitled

Như vậy là mình vừa hướng dẫn các bạn thuật toán Kruskal – tìm cây khung nhỏ nhất, chúc các bạn cài đặt thành công ^_^

Thuật toán Prim – Tìm cây bao trùm nhỏ nhất

1. Mô tả:

Giống như Kruskal, Prim cũng tìm cây khung nhỏ nhất, tuy nhiên Prim phụ thuộc vào đỉnh xuất phát của quá trình tìm kiếm.

  Hình 1: Đây là đồ thị có trọng số ban đầu. Các số là các trọng số của các cạnh.

1

Hình 1

  Hình 2: Chọn một cách tùy ý đỉnh D là đỉnh bắt đầu. Các đỉnh A, B, EF đều được nối trực tiếp tới bằng cạnh của đồ thị. A là đỉnh gần D nhất nên ta chọn A là đỉnh thứ hai của cây và thêm cạnh AD vào cây.

 2

Hình 2

  Hình 3: Đỉnh được chọn tiếp theo là đỉnh gần D hoặc nhất. B có khoảng cách tới D bằng 9 và tới Abằng 7, E có khoảng cách tới cây hiện tại bằng 15, và F có khoảng cách bằng 6. F là đỉnh gần cây hiện tại nhất nên chọn đỉnh F và cạnh DF.

3

Hình 3

  Hình 4: Thuật toán tiếp tục tương tự như bước trước. Chọn đỉnh B có khoảng cách tới A bằng 7.

4

Hình 4

  Hình 5: Ở bước này ta chọn giữa C, E, và G. C có khoảng cách tới B bằng 8, E có khoảng cách tới B bằng 7, và G có khoảng cách tới F bằng 11. là đỉnh gần nhất, nên chọn đỉnh E và cạnh BE.

5

Hình 5

  Hình 6: Ở bước này ta chọn giữa CG. C có khoảng cách tới E bằng 5, và G có khoảng cách tới Ebằng 9. Chọn C và cạnh EC.

6

Hình 6

  Hình 7: Quá trình tìm đỉnh kế tiếp không được tạo ra một chu trình so với ban đầu, để biết được đỉnh mới được chọn có trở thành chu trình hay không, ta cần kiểm tra đỉnh đó đã được đi qua hay chưa, nếu đã đi qua thì không thể đi tới, trong trường hợp này là đỉnh B và đỉnh F đều có trọng số mới là 8 (nhỏ nhất) nhưng ta không chọn. Như vậy, đỉnh G là đỉnh còn lại duy nhất. Nó có khoảng cách tới F bằng 11, và khoảng cách tới E bằng 9. E ở gần hơn nên chọn đỉnh G và cạnh EG.

7

Hình 7

  Hình 8: Hiện giờ tất cả các đỉnh đã nằm trong cây và cây bao trùm nhỏ nhất được tô màu xanh lá cây. Tổng trọng số của cây là 39.

8

Hình 8

Nguồn từ: http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Prim

2. Cài đặt:

Bước 1: Khởi tạo các biến:

Untitled

Bước 2: Cài đặt các bước thực hiện trong thuật toán Prim:
UntitledHàm tìm nút kế tiếp:

Untitled

Như vậy là tôi vừa hướng dẫn các bạn cách cài đặt thuật toán Prim – tìm cây bao trùm nhỏ nhất, chúc các bạn thành công ^_^