[Bài toán] Xây dựng đường sắt

Bài toán: Bộ xây dựng đang có kế hoạch xây dựng hệ thống đường sắt nối liền các thành phố với nhau, sao cho chỉ có duy nhất 1 tuyến đường sắt nối liền hai thành phố bất kỳ. Sau khi nhiên cứu tính toán chi phí xây dựng các tuyến đường sắt nối liền các thành phố, bộ xây dựng thu...

[Bài tập mẫu] Đa giác số

Bài toán: Trên vòng tròn đánh dấu n điểm phân biệt. Các điểm này được chọn làm n đỉnh của đa giác lồi P. Vẽ tất cả các đường chéo của đa giác P. Cho N là một họ gồm n số nguyên dương. Mỗi số của họ N sẽ được viết bên cạnh một đỉnh của đa giác P. Ta gọi việc làm này là phân...

[Bài tập mẫu] Con đường Tùng - Trúc.

[Bài toán] Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng,dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất...

[Bài toán] Xếp hậu

Bài toán:  Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ n x n sao cho chúng không ăn được nhau bằng thuật toán Back Track. Giải. Bàn cờ có n hàng được đánh số từ 0 đến n-1, n cột được đánh số từ 0 đến n-1; Bàn cờ có n*2 -1 đường chéo xuôi được đánh số từ 0 đến 2*n...

[Bài toán] Liệt kê các hoán vị của tập n phần tử bằng thuật toán Back Track

     Biểu diễn hoán vị dưới dạng p1, p2,.., pn, trong đó pi nhận giá trị từ 1 đến n và pi≠pj với i≠j. Các giá trị từ 1 đến n lần lượt được đề cử cho pi, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy, cần phải ghi nhớ với mỗi giá trị j xem...

[Bài toán] Liệt kê các tập con k phần tử của tập n phần tử bằng thuật toán Back Track

Lý thuyết Back Track bạn có thể xem thêm ở đây.      Biểu diễn tập con k phần tử dưới dạng c1, c2,.., ck, trong đó 1< c1các giá trị đề cử cho ci là từ ci-1+ 1 cho đến n - k + i. Cần thêm vào c0= 0. Các giá trị đề cử này mặc nhiên được chấp nhận mà không cần phải...

[Bài toán] Liệt kê các xâu nhị phân độ dài n bằng thuật toán Back Track

Lý thuyết Back Track bạn có thể xem thêm ở đây.      Biểu diễn các xâu nhị phân dưới dạng b1, b2,..., bn, trong đó bi∈{0, 1 }. Thủ tục đệ qui Try(i) xác định bi với các giá trị đề cử cho bi là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không cần phải...

[Bài tập mẫu] Vẽ hình tròn.

[Bài tập] Tuấn viết một chương trình đồ họa, chương trình đó vẽ n hình tròn màu trắng lên màn hình màu đen. Màn hình là màn hình đen trắng có độ phân giải là w * h pixels. Pixels được đánh số từ góc trên bên trái (0,0) tới góc dưới bên phải (w-1,h-1). Một hình tròn có tâm O(xc,yc) bán...

[Bài tập mẫu] Hệ thống phòng thủ.

[Bài tập] Hãy tưởng tượng bạn đang tham gia một trò chơi có tên là " Hệ thống phòng thủ". Ở mỗi mức chơi (level) người chơi phải bảo vệ một vùng đất hình chữ nhật có dạng mạng lưới các ô vuông. Người chơi xây dựng các tháp phòng thủ tại một vài vị trí trên vùng đất đó. Một tháp...

[Bài toán] Chuỗi số nguyên tố.

Trong chuối số nguyên tố thì chữ số đầu tiên là số nguyên tố, số đến chữ số thứ n là số nguyên tố. Để hiểu hơn ta sét ví dụ sau: Số 7331 là chuỗi số nguyên tố có 4 chữ số, trong đó chữ số đầu tiên (7) là số nguyên tố, số đến chữ số thứ 2 (73) là số nguyên tố, số đến chữ số thứ...

Bài tập mẫu

Dưới đây là danh sách bài tập mẫu của blog. Liệt kê các hoán vị của một tập có lặp. Biểu diễn n thành tổng các số tự nhiên không lớn hơn n. Các thao tác vào ra cơ bản và các câu lệnh có cấu trúc trong C. Xếp hạng học sinh trong lớp. Đổi chỗ các phần tử trong mảng để được số...

[Bài toán] Liệt kê dãy nhị phân độ dài n.

[Bài toán] Liệt kê dãy nhị phân độ dài n. [Giải] Viết dãy nhị phân dưới dạng b1b2..bn, trong đó bi∈{0, 1 }. Xem mỗi dãy nhị phân b=b1b2..bn là biểu diễn nhị phân của một số nguyên p(b). Khi đó thứ tự hiển nhiên nhất có thể xác định trên tập các dãy nhị phân là thứ tự từ điển...

[Bài toán] Tìm đường đi trong ma cung.

[Bài toán] Một mê cung được cho như hình bên dưới. Mê cung là một ma trận có kích thước 100x100. Trong đó màu trắng là đường đi, màu vàng là tường. Hãy tìm đường đi từ điểm bắt đầu có giá trị 2 đến điểm kết thúc có giá trị 3.  Giả sử đỉnh trên cùng bên trái có tọa độ là (0,0)....

[Baì toán] Tìm đường đi Hamiton ngắn nhất.

[Bài toán] Nhân viên giao bánh piza phải giao bánh cho N khách hàng. Từ cửa hàng bánh , anh ta phải đi giao bánh cho N khách hàng sau đó trở về nhà của mình. Vị trí của của hàng bánh, nhà của anh ta và của khách hàng theo mẫu sau (x,y). Khoảng cách giữa 2 vị trí (x1,y1) và...

[Bài toán] Sắp xếp mảng 1 chiều bằng QuickSort

[Bài toán] Cho mảng một chiều a. Hãy cài đặt QuickSort để sắp xếp mảng trên theo thứ tự tăng dần. [Thuật toán] QuickSort là một thuật toán sắp xếp được sử dùng rộng rãi nhất và vì lý do: trong hầu hết mọi trường hợp, nó là phương pháp nhanh nhất, thời gian chạy thuật toán là O(N*logN)....

[Bài toán] Liệt kê tất cả các hoán vị của n phần tử.

Bài toán : Liệt kê các hoán vị của tập n phần tử. Cho X = { 1, 2,.., n }. Hãy liệt kê các hoán vị từ n phần tử của X. Chương trình cài đặt bằng đệ quy quay lui. //chương trình sẽ liệt kê tất cả các hoán vị của tập X={1,2,3,4} bằng phương pháp đệ quy quay lui. //Kết quả...

[Bài toán] Liệt kê tập con của tập n phần tử.

Bài toán: Cho X = {1, 2,3,.., n}. Hãy liệt kê tất cả các tập con k phần tử của X (k<=n). Giải: Mỗi tập con của tập hợp X có thể biểu diễn bằng bộ có thứ tự gồm k thành phần a = (a1a2..ak) thoả mãn 1 ≤a1 ≤a2 ≤..≤ak ≤n. Trên tập các tập con k phần tử của X có thể xác định nhiều...

[Bài toán] Tìm điểm căn bằng.

Ở một dải ngân hà X có n hành tinh. Tọa độ của mỗi hành tinh được đặc trưng bởi 3 tọa độ (x,y,z). Vào một thời điểm nào đó trong năm, các hành tinh được sắp xếp trên một đường thẳng x (y = z = 0). Đây là một hiện tượng khoa học thú vị, các nhà khoa học đã đặt ra  câu hỏi: Ở...

[Bài toán] Đổi chỗ các phần tử trong mảng để được số lớn nhất.

Bài toán: Trong một chương trình truyền hình, người chơi có cơ hội nhận được một số tiền thưởng. Số tiền được ghi lên các card (bảng). Người chơi phải đổi chỗ 2 card bất kỳ theo một số lần quy định cho trước để được số tiền lớn nhất có thể. Ví dụ: Có 5 card sau: 3, 2, 8, 8, 8...

[Bài toán] Xếp hạng học sinh trong lớp.

Bài toán: Lớp học có n học sinh vừa trải qua kỳ thi cuối học kỳ I. Sau khi công bố điểm thi của các học sinh. Giáo viên chủ nhiệm muốn xem thứ tự xếp hạng của mỗi thí sinh. Giới hạn thời gian : 1 sec. [Input] Dữ liệu đầu vào được lưu trong file INPUT.TXT. Dòng đầu chứa số lượng...