Thắc Mắc Về Thuật Toán Vét Cạn - Programming - Dạy Nhau Học

Có thể bạn quan tâm

programming nts311 (Sơn) October 31, 2016, 12:03pm #1 Xin chào mọi người. Trường em có tổ chức hội thi KH-KT. Em có làm một phần mềm để giải bài toán cấu tạo số kiểu như :“Cho tập các chữ số {0,1,2,6,4,5,8,9}, lập được bao nhiêu số có 4 chữ số chắn khác nhau,…”. Trong phần mềm thì em cho 1 vòng lặp từ 111,1111,11111,… đến 999,9999,99999 thì đó có phải là quay lui vét cạn hay phương pháp sinh gì không. Và em muốn hỏi liệu còn cách nào tối ưu hơn không. Em xin cảm ơn

. KhoaTran (Trần Ngọc Khoa) October 31, 2016, 12:09pm #2 Nếu vét cạn thì bạn phải vét hết các trường hợp có thể chứ. 111, 1111, 11111 đến 999999 thì chắc chắn thiếu. Chưa kể “lập được bao nhiêu số có 4 chữ số chắn khác nhau” thì các chữ số chẵn trong số đó phải khác nhau nữa.1 Like nts311 (Sơn) October 31, 2016, 12:13pm #3

Nếu vét cạn thì bạn phải vét hết các trường hợp có thể chứ. 111, 1111, 11111 đến 999999 thì chắc chắn thiếu. Chưa kể “lập được bao nhiêu số có 4 chữ số chắn khác nhau” thì các chữ số chẵn trong số đó phải khác nhau nữa.

Trong phần mềm em làm thì có thể chọn từ 1 dến 9 chữ số, nếu người dùng nhập 4 cs chẵn thì sẽ kiểm chạy vòng lặp từ 1112 đến 9998, mỗi lần tăng 2 đơn vi. Còn nếu người dùng yêu cầu các chữ số khác nhau thì sẽ có 1 hàm kiểm tra liệu các số có khác nhau hay không. Nếu khác thì ghi lại, giống nhau thì bỏ qua. KhoaTran (Trần Ngọc Khoa) October 31, 2016, 12:20pm #4 Bạn có thể đưa cái đề đầy đủ không? Mình đọc reply thứ hai của bạn mới biết là có thêm yêu cầu. p.s: Lần sau bạn nên đưa ra đầy đủ câu hỏi hoặc chia câu hỏi ra làm từng phần.1 Like nts311 (Sơn) October 31, 2016, 12:44pm #5 Bài toán cấu tạo số thì nó có rất nhiều kiểu. Em lấy ví dụ:“Có bao nhiêu số tự nhiên chẵn có 4 chữ số khác nhau được lập từ tập A {1;2;3;4;5;6;7;8;9}?”. Thì phần mềm của em sẽ khởi tạo số ban đầu và kết thúc . Vì là số chẵn nên bát đầu từ 1112 đến 9998 thì kết thúc. Nó sẽ chạy vòng lặp từ 1112 đến 9998. Rồi trong mỗi lần lặp sẽ kiểm tra xem các chữ số có khác nhau không, có chứa các chữ số mà người dùng đã chọn không. Nếu thỏa mãn thì sẽ tăng biến đếm lên 1, không thì thôi. Rồi kết thúc nó sẽ đưa ra số lượng các số thỏa mãn yêu cầu đề bài.

Untitled369.png1600×901 128 KB feosedit (Nguyễn Thành Trung) October 31, 2016, 12:48pm #6 bài này dùng hoán vị lớp 11 nè =]] :)) ai học chắc tổ hợp bấm P ra phát một =]] bài đó thì 7 * 7! là ra =]] KhoaTran (Trần Ngọc Khoa) October 31, 2016, 12:56pm #7 À, hóa ra chủ thớt đi thi KH-KT nên viết phần mềm. Cái phần mềm này có ứng dụng gì vậy thớt?1 Like nts311 (Sơn) November 1, 2016, 9:08am #8

bài này dùng hoán vị lớp 11 nè =]] :)) ai học chắc tổ hợp bấm P ra phát một =]] bài đó thì 7 * 7! là ra =]]

Đúng rồi bạn

À, hóa ra chủ thớt đi thi KH-KT nên viết phần mềm. Cái phần mềm này có ứng dụng gì vậy thớt?

Nó để giải các bài toán cấu tạo số mà em đang học ạ.

KhoaTran (Trần Ngọc Khoa) November 1, 2016, 10:45am #9

Nó để giải các bài toán cấu tạo số mà em đang học ạ.

Cuối cùng thì cũng hình dung được cái yêu cầu và thêm nữa là mục đích.Mấy cái bài toán này nó chỉ yêu cầu xuất ra số lượng nên nếu có thể thì bạn nên dùng kiến thức về xác suất thống kê (nếu đã biết) để giảm số vòng lặp. Ví dụ để tìm số các số tự nhiên chia hết cho 3 có 4 chữ số, bạn chỉ cần tính số tập các chữ số có tổng chia hết cho 3. Sau đó tính số hoán vị của chúng là ra.Không biết bạn học lớp mấy rồi nhỉ. Nếu bạn khoảng cấp 1 thì phần mềm này có giải rồi đó bạn.1 Like hell6w9rld (HelloWorld) November 1, 2016, 1:36pm #10 bạn học toán rời rạc chưa Cho tập các chữ số {0,1,2,6,4,5,8,9} trả lời cho câu hỏi lập được bao nhiêu số có 4 chữ số chắn khác nhau? đây là bài toán đếm sử dụng lý thuyết tổ hợp để liệt kê các số có thể lập được đây bài toán liệt kê có thể sử dụng sinh bằng phương pháp quay lui vét cạn hoặc cách khác, nhưng quay lui vét cạn sẽ khỏe hơn

như bạn nói trên k phải là thuật toán quay lui, vét cạn, quay lui vét cạn là thuật toán thử và saimô hình như sauquay lui vét cạn là thuật toán dễ về mặt hình thức, ngắn gọn, dễ cài đặt, nhưng ngược lại để hiểu nó chạy ntn thì bạn phải chạy bằng tay thì mới hiểu được, vì quay lui sử dụng hàm đệ quy nên tốn bộ nhớ, máy chạy khổ

nhưng mà máy chạy chứ k phải ng chạy nên không lo , nhìn code ngắn có 1 đoạn thôi, nhưng chạy thay thì ra cả mấy tờ giấy a4 k hết đâu

chưa kể bùng nổ 1 phát thì ngồi liệt kê cả đời, còn mt thì nó chạy nhanh nên có thể giải quyết những bài toán trên thay con ng trong thời gian cho phép2 Likes nts311 (Sơn) November 1, 2016, 1:53pm #11

Cuối cùng thì cũng hình dung được cái yêu cầu và thêm nữa là mục đích.

Mấy cái bài toán này nó chỉ yêu cầu xuất ra số lượng nên nếu có thể thì bạn nên dùng kiến thức về xác suất thống kê (nếu đã biết) để giảm số vòng lặp. Ví dụ để tìm số các số tự nhiên chia hết cho 3 có 4 chữ số, bạn chỉ cần tính số tập các chữ số có tổng chia hết cho 3. Sau đó tính số hoán vị của chúng là ra.

Không biết bạn học lớp mấy rồi nhỉ. Nếu bạn khoảng cấp 1 thì phần mềm này có giải rồi đó bạn.

Cảm ơn anh

. Em đang học cấp 3 a… nts311 (Sơn) November 1, 2016, 1:54pm #12

bạn học toán rời rạc chưa Cho tập các chữ số {0,1,2,6,4,5,8,9} trả lời cho câu hỏi lập được bao nhiêu số có 4 chữ số chắn khác nhau? đây là bài toán đếm sử dụng lý thuyết tổ hợp để liệt kê các số có thể lập được đây bài toán liệt kê có thể sử dụng sinh bằng phương pháp quay lui vét cạn hoặc cách khác, nhưng quay lui vét cạn sẽ khỏe hơn

như bạn nói trên k phải là thuật toán quay lui, vét cạn, quay lui vét cạn là thuật toán thử và sai

mô hình như sau

try( phần tử cấu hình đầu tiên ){ duyệt tập đề cử{ nếu mỗi phần tử đề cử tm yêu cầu{ đánh dấu phần tử đề cử đã dùng; ghi nhận phần tử đề cử vào cấu hình; nếu cấu hình tm đề bài thì in kết quả; không thì try( phần tử cấu hình tiếp theo ); trả lại trạng thái cũ; } } }

quay lui vét cạn là thuật toán dễ về mặt hình thức, ngắn gọn, dễ cài đặt, nhưng ngược lại để hiểu nó chạy ntn thì bạn phải chạy bằng tay thì mới hiểu được, vì quay lui sử dụng hàm đệ quy nên tốn bộ nhớ, máy chạy khổ nhưng mà máy chạy chứ k phải ng chạy nên không lo , nhìn code ngắn có 1 đoạn thôi, nhưng chạy thay thì ra cả mấy tờ giấy a4 k hết đâu chưa kể bùng nổ 1 phát thì ngồi liệt kê cả đời, còn mt thì nó chạy nhanh nên có thể giải quyết những bài toán trên thay con ng trong thời gian cho phép

Em cảm ơn

. Em cũng đang đọc về mấy cái sinh, quay lui,… Nhưng cho em hỏi là nếu dùng quay lui hoặc dùng cách lặp từ 1111->9999 thì cách nào sẽ nhanh hơn ạ? hell6w9rld (HelloWorld) November 1, 2016, 1:58pm #13 bạn đánh giá độ phức tạp của 2 thuật toán trên xem đề bộ nhớ thì chắc chắn quay lui tốn hơn nhưng câu hỏi của bạn là hỏi lập được bao nhiêu số… chứ có bảo liệt kê đâu ,thế thì cần gì liệt kê ta?