zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài toán liệt kê

Chia sẻ: Hanh My | Ngày: | Loại File: PDF | Số trang:3

Báo xấu

134
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thứ tự từ điển Trong các bộ từ điển, các từ được liệt kê theo thứ tự được gọi là thứ tự từ điển. Cho hai từ dưới dạng xâu của các kí tự x = x1x2...xm y = y1y2...yn Từ x được gọi là đứng trước từ y theo thứ tự từ điển nếu tồn tại chỉ số i, sao cho xj + 1 đứng trước yj + 1 Chú ý: Nếu jm thì ta coi xj là kí tự rỗng, tương tự nếu jn thì coi yj là kí tự rỗng, kí tự rỗng đứng trươc mọi kí...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài toán liệt kê

Bài toán liệt kê Thứ tự từ điển Trong các bộ từ điển, các từ được liệt kê theo thứ tự được gọi là thứ tự từ điển. Cho hai từ dưới dạng xâu của các kí tự x = x1x2...xm y = y1y2...yn Từ x được gọi là đứng trước từ y theo thứ tự từ điển nếu tồn tại chỉ số i, sao cho xj + 1 đứng trước yj + 1 Chú ý: Nếu j>m thì ta coi xj là kí tự rỗng, tương tự nếu j>n thì coi yj là kí tự rỗng, kí tự rỗng đứng trươc mọi kí tự khác. [sửa] Liệt kê các hoán vị của tập n phần tử Việc liệt kê toàn bộ các hoán vị của tập X = {x1,x2,...,xm} được quy về việc liệt kê tất cả n! hoán vị của tập chỉ số {1,2,...,n}. Ta sẽ liệt kê các hoán vị của n số tự nhiên {1,2,...,n} theo thứ tự từ điển. Nhận xét rằng, khi xếp theo thứ tự từ điển, hoán vị đứng trước tiên sẽ là hoán vị (1,2,3,...,n − 1,n), hoán vị đứng cuối cùng sẽ là hoán vị (n,n − 1,...,2,1). Ví dụ với n=5, hoán vị đứng đầu là (1,2,3,4,5), đứng cuối là (5,4,3,2,1). Trong hoán vị đầu tiên mỗi số đều nhỏ hơn số đứng ngay sau nó, trong hoán vị cuối cùng thì ngược lại. Vậy kế tiếp sau hoán vị đầu tiên là hoán vị nào?
[sửa] Hoán vị kế tiếp của một hoán vị (theo thứ tự từ điển) Giả sử có hoán vị x = (x1,x2,...,xn − 1,xn) của n số 1,2,...,n. Thuật toán sinh hoán vị kế tiếp  1. Tìm từ bên phải sang chỉ số i sao cho xi − 1 < xi. 2. Nếu không tìm thấy thì trả lời x là hoán vị cuối cùng, không có hoán vị kế tiếp. 3. Nếu có i như vậy:  sắp xếp các giá trị xi,...,xn theo thứ tự tăng dần.  đổi chỗ xi − 1 cho phần tử lớn hơn xi − 1 gần nhất trong các giá trị xi,...,xn Ví dụ: với n=5 kế tiếp của hoán vị (1,2,3,4,5) là hoán vị (1,2,3,5,4)  kế tiếp của hoán vị (1,2,3,5,4) là hoán vị (1,2,4,3,5)  kế tiếp của hoán vị (1,2,4,3,5) là hoán vị (1,2,4,5,3)  ... kế tiếp của hoán vị (5,4,3,1,2) là hoán vị (5,4,3,2,1)  [sửa] Thuật toán liệt kê tất cả các hoán vị của n số 1,2,...,n 1. Khới tạo: x = (1,2,...,n) 2. Tìm x' là hoán vị kế tiếp của x 3. Nếu không tìm được thì dừng. 4. Nếu thấy,thay x bằng x' quay lại 2. Ví dụ: Liệt kê 24 hoán vị của 1,2,3,4 theo thứ tự từ điển
1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321. === Liệt kê các tổ hợp chập k của tập n phần tử 1,2,3,4,5,6

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.