Home » LẬP TRÌNH (page 2)

LẬP TRÌNH

Toán rời rạc: Kiểm tra đồ thị hai phía hay không?

Kiểm tra đồ thị hai phía   Có Ma trận kề của đồ thị lưu trong file văn bản có dạng như sau: Kết quả: Không hai phía. HD:  Đơn đồ thì G=(V,E) được gọi là hai phía nếu như tập đỉnh V của nó có thể phân hoạch thành hai tập X và Y sao cho mỗi cạnh của ... Read More »

Bài toán người du lịch

BÀI TOÁN NGƯỜI DU LỊCH Cho n thành phố đánh số từ 1 đến n và m tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi bảng C cấp nxn, ở đây C[i, j] = C[j, i] = Chi phí đi đoạn đường trực tiếp từ thành phối đến thành phốj. Giảthiết rằng ... Read More »

Tìm dãy số (Spoj)

Link bài: http://www.spoj.com/PTIT/problems/PTIT136C/ 14080. Tìm dãy số Mã bài: PTIT136C Cho trước một dãy số dương có N phần tử. Bạn biết trước tổng của bất kì 2 phần tử nào trong dãy số, hãy tìm dãy số ban đầu. Input Dòng đầu tiên là N, số phần tử của dãy số. (2 <= N <= 1000) N dòng sau, mỗi ... Read More »

Liệt kê dãy nhị phân (PP quay lui)

Đề bài : Liệt kê dãy nhị phân có độ dài n. HD: Đáp số có dạng (x1,x2,…,x n). Khả năng của xi là 0,1. Chấp nhận khả năng j của xi: luôn chấp nhận. Xác định xi theo j: xi=j. Ghi nhận 1 đáp số: xuất dãy xi. Code tham khảo:  [crayon-5c149d2a478a2841354223/]       Read More »

Thuật toán Quay lui (Backtracking Algorithms)

Ý tưởng: G/s đáp số của bài toán là một bộ có n thành phần (x1,x2,…,xn) và g/s đã xác định được i-1 thành phần x1,x2,…,xi-1. Để xác định xi, ta xét tất cả các khả năng có thể của xi, đánh số các khả năng này là 1,…,ni. Với mỗi khả năng j của xi ta kiểm tra xem khả năng j ... Read More »

Liệt kê hoán vị (PP Sinh)

Link bài: http://www.spoj.com/PTIT/problems/BCPERMU/ 9807. Liệt kê hoán vị (Cơ bản) Mã bài: BCPERMU Liệt kê hoán vị của n phần tử của một tập gồm các số từ 1->n. Input Dòng duy nhất chứa số n (1<=n<=8) Output Các hoán vị sắp xếp theo thứ tự từ điển tăng dần. Example Input: 3 Output: 123 132 213 231 312 321   ... Read More »

Liệt kê dãy nhị phân có độ dài n (PP Sinh)

Link bài: http://www.spoj.com/PTIT/problems/BCSINH/ 9806. Sinh các dãy nhị phân độ dài n (Cơ bản) Mã bài: BCSINH Sinh các dãy nhị phân có độ dài n. Input Số nguyên duy nhất n (1<=n<=9) Output Mỗi dòng một dãy nhị phân. Các dãy nhị phân phải được liệt kê theo thứ tự từ điển. Example Input: 2 Output: 00 01 10 11 ... Read More »

Dãy số 3 (Spoj)

Link bài: http://www.spoj.com/PTIT/problems/PTIT125C/ 11036. Dãy số 3 Mã bài: PTIT125C Cho dãy số N (1 <= N <= 1,000,000, N lẻ) phần tử đánh số từ 1 đến N, ban đầu có giá trị là 0. Có tất cả K (1<=K<=25,000) truy vấn, mỗi truy vấn có dạng “A B” sẽ thực hiện tăng các phần tử trong đoạn [A,B] lên ... Read More »

Sàng nguyên tố (Spoj)

Link bài: http://www.spoj.com/PTIT/problems/P134SUMF/ 15525. SUM4 F – Sàng nguyên tố Mã bài: P134SUMF Tí và Tèo đang cùng nhau học về sàng nguyên tố Eratosthenes. Thuật toán sàng nguyên tố để tìm các số nguyên tố từ 2 tới N như sau: 1. Viết tất cả các số nguyên từ 2 tới N theo đúng thứ tự. 2. Tìm số nguyên ... Read More »

Thuật toán sinh (Basic)

Ý tưởng: Xây dựng một thứ tự trên tập các cấu hình cần liệt kê và suy ra cấu hình đầu tiên, cấu hình cuối cùng. Xây dựng thuật toán sinh cấu hình thứ i từ cấu hình thứ i-1 (gọi là thuật toán sinh cấu hình kế tiếp) Từ thuật toán sinh và biết cấu hình 1 sẽ tìm ... Read More »

Share
Free WordPress Themes - Download High-quality Templates