56. Hãy tìm tất cả các số tự nhiên có 9 chữ số thỏa mãn: a] Số có 9 chữ số tạo thành một số thuận nghịch; b] Số có 9 chữ số tạo thành một số thuận nghịch và có tất cả các chữ số đều khác 0; c] Số có 7 chữ số có tổng các chữ số là 19; 57. Hãy tìm tất cả các số tự nhiên có 10 chữ số thỏa mãn: a] Số có 10 chữ số tạo thành một số thuận nghịch; b] Số có 10 chữ số tạo thành một số thuận nghịch và có tất cả các chữ số đều khác 0; c] Số có 10 chữ số có tổng các chữ số là 18. 58. a] Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n và không có k số 1 liên tiếp? b] Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n có ít nhất một dãy k số 1 liên tiếp? 59. a] Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n và không có k số 0 liên tiếp? b] Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n có ít nhất một dãy k số 0 liên tiếp? PTIT
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc 1, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
dần. Thuật toán nhánh cận giải bài toán cái túi được mô tả như Hình 4.4 dưới đây. Thuật toán Brach_And_Bound [i] { t = [ b - bi]/A[i]; //Khởi tạo số lượng đồ vật thứ i for j = t; j 0; j--]{ x[i] = j; //Lựa chọn x[i] là j; ;iiii xabb // Trọng lượng túi cho bài toán bộ phận thứ i. ;iiii xc // Giá trị sử dụng cho bài toán bộ phận thứ i If [k==n] ; else if [k + [ck+1*bk]/ak+1 >FOPT] //Nhánh cận được triển khai tiếp theo Branch_And_Bound[k+1]; ;iiii xabb ;iiii xc } } Hình 4.4. Thuật toán nhánh cận giải bài toán cái túi Ví dụ. Giải bài toán cái túi sau theo thuật toán nhánh cận trình bày ở trên. .4,3,2,1, 84235 max63510][ 4321 4321 jZx xxxx xxxxxf j Lời giải. Quá trình giải bài toán được mô tả trong cây tìm kiếm trong Hình 4.4. Thông tin về một phương án bộ phận trên cây được ghi trong các ô trên hình vẽ tương ứng theo thứ tự sau: Đầu tiên là các thành phấn của phương án bộ phận thứ i : X =[x1,x2,..,xi]; Tiếp đến là giá trị của các đồ vật theo phương án bộ phận thứ i; Kế tiếp là w tương ứng với trọng lượng còn lại của túi; Cuối cùng là cận trên g. PT IT 84 Kết thúc thuật toán, ta thu được phương án tối ưu là x* =[1, 1, 0, 1], giá trị tối ưu f*= 15. PT IT 85 x1=1 x1=0 x1=1 x2=0 Loại vì cận trên