Bạn đang xem: Bài tập cấu trúc dữ liệu và giải thuật có lời giải
Bài 3.Cho dãy AN = {a1, a2, ..,aN} gồm N số tự nhiên phân biệt. Hãy sử dụng thuật toán sinh (quay lui, nhánh cận, qui hoạch động) viết chương trình liệt kê tất cả các dãy con K phần tử của dãy số AN (Kdayso.in ketqau.out5 3 50 25 10 15 20 25 5 20 25 10 15 25Bài 4.Hãy sử dụng thuật toán sinh (quay lui, nhánh cận, qui hoạch động) viết chương trình Viết chương trình tìm X = (x1, x2,..,xn) và f(X) đạt giá trị lớn nhất. Trong đó:
Bài 5.Một dãy số tự nhiên bất kỳ AN = {a1, a2,.., aN} được gọi là một dãy số nguyên tố thuần nhất bậc K nếu tổng K phần tử liên tiếp bất kỳ của dãy số AN là một số nguyên tố (K Ví dụ:Input:• n = 5, K =3• A = (3, 7, 9, 15, 27)Output: 4 3 27 7 9 15 15 9 7 3 27 15 9 7 27 3 27 3 7 9 15
Xem thêm: Tuổi 1988 Hợp Hướng Nào ? Tuổi Mậu Thìn Hợp Hướng Nào
Bài 6.Cho số tự nhiên n. Hãy in ngược lại dãy số tự nhiên ngược lại từ n đến 1. Ví dụ n=5, ta in ngược lại là : 5 4 3 2 1.Bài 14.Cho tập gồm n hành động, mỗi hành động được biểu diễn như bộ đôi thời gian bắt đầu si và thời gian kết thúc fi (i=1, 2, .., n). Bài toán đặt ra là hãy lựa chọn nhiều nhất các hành động có thể thực hiện bởi một máy hoặc một cá nhân mà không xảy ra tranh chấp. Giả sử mỗi hành động chỉ thực hiện đơn lẻ tại một thời điểm.Input:- Số lượng hành động: 6 - Thời gian bắt đầu Start <>= { 1, 3, 0, 5, 8, 5} - Thời gian kết thúc Finish<>= { 2, 4, 6, 7, 9, 9}Output: Số lượng lớn nhất các hành động có thể thực hiện bởi một người. OPT<> = {0, 1, 3, 4 }
Bài 15.Bài toán n-ropes. Cho n dây với chiều dài khác nhau. Ta cần phải nối các dây lại với nhau thành một dây. Chi phí nối hai dây lại với nhau được tính bằng tổng độ dài hai dây. Nhiệm vụ của bài toán là tìm cách nối các dây lại với nhau thành một dây sao cho chi phí nối các dây lại với nhau là ít nhất.Input: - Số lượng dây: 4 - Độ dài dây L<>= { 4, 3, 2, 6}Output: Chi phí nối dây nhỏ nhất. OPT = 39
Bài 16.Cho xâu ký tự s<> độ dài n và số tự nhiên d. Hãy sắp đặt lại các ký tự trong xâu s<> sao cho hai ký tự giống nhau đều cách nhau một khoảng là d. Nếu bài toán có nhiều nghiệm, hãy đưa ra một cách sắp đặt đầu tiên tìm được. Nếu bài toán không có lời giải hãy đưa ra thông báo “Vô nghiệm”.Ví dụ.Input: • Xâu ký tự S<> =“ABB”; • Khoảng cách d = 2.Output: BABInput: • Xâu ký tự S<> =“AAA”; • Khoảng cách d = 2.Output: Vô nghiệm.Input: • Xâu ký tự S<> =“GEEKSFORGEEKS”; • Khoảng cách d = 3.Output: EGKEGKESFESOR.
Bài 17.Cho dãy số nguyên bao gồm cả số âm lẫn số dương. Nhiệm vụ của ta là tìm dãy con liên tục có tổng lớn nhất.Ví dụ. Với dãy số A = {-2, -5, 6, -2, -3, 1, 5, -6} thì tổng lớn nhất của dãy con liên tục ta nhận được là 7.
Bài 18.Cho mảng số nguyên
