Bài 2.Cho dãy A<> gồm N số tự nhiên khác nhau và số tự nhiên K. Hãy sử dụng thuật toán sinh viết chương trình liệt kê tất cả các dãy con của dãy số A<> sao cho tổng các phần tử trong dãy con đó đúng bằng K.Dayso.in Ketqua.out5 50 35 10 15 20 25 10 15 25 5 20 25 5 10 15 20

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 25
Bà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
*
.Tìm cặp số có hiệu độ lệch lớn nhất trong đó số lớn hơn đứng ở sau số nhỏ hơn.Giả sử Diff(a<1,n>) độ lệch cần tìm thì Diff(a<1,n>)=Max(
*
) trong đó 1Tải về code C++(Giải thuật chia để trị)Bài 19.Trong giờ học môn Điện tử số về mã Gray, MĐ chợt nảy sinh ra một bài toán để code. Bài toán rất đơn giản như sau: In ra lần lượt bảng mã gray n-bit.Mã Gray là mã nhị phân mà hai mã liền kề trong bảng mã chỉ khác nhau một bit. Các giá trị ở nửa sau của bảng mã có sự đối xứng với nửa đầu của bảng mã theo thứ tự ngược lại, ngoại trừ bit cao nhất bị đảo giá trị (bit cao nhất là bit ngoài cùng bên trái). Tính chất đối xứng này vẫn đúng cho các bit thấp hơn trong mỗi nửa, mỗi phần tư,… của bảng mã.InputMột số nguyên duy nhất n (1OutputBảng mã gray n-bit theo thứ tự, mỗi mã trên một dòng.Tải về code C++Bài 20.Cho số tự nhiên X.Hãy tìm cách biểu diễn X thành tổng lũy thừa bậc n của các số tự nhiên khác nhau.Input: Output:X=10,n=2 1 3 X=100,n=2 0 10 6 8Tải về code C++Bài 21.1.Special Triangle . Cho dãy số A<> gồm n số nguyên dương. Tamgiác đặc biệt của dãy số A<> là tam giác được tạo ra bởi n hàng, trong đó hàngthứ n là dãy số A<>, hàng i là tổng hai phần tử liên tiếp của hàng i+1(1≤i≤n-1). Ví dụ A<> = {1, 2, 3, 4, 5}, khi đó tam giác được tạo nên như dướiđây: