Gợi ý cách giải quyết bài liệt kê ra tất cả các cách sắp xếp n người vào 1 cái bàn

Đề yêu cầu là nhập vào danh sách tên n người, xuất ra tất cả các cách sắp xếp n người đó vào 1 bàn.

Em tính dùng hàm random để random ra tên 1 người cho 1 ghế(ở đây em vd bàn 4 ghế và số người là 5) nhưng mà không biết làm sao để nó không random lặp lại

Dùng lệnh này để randomize

srand(time(NULL));

nhớ include stdlib.h và time.h

3 Likes

srand(time(NULL)); để không bị lặp lại hả anh??

1 Like

Có lặp mà tỉ lệ ít. :penguin:

2 Likes

okay để em thử làm :muscle:

Xem qua bài hoán vị nhé :smile:
https://github.com/minhhuy150894/C-CPPSourceCode/blob/master/Some-Problems/hoan-Vi.cpp

2 Likes

giúp em với nó em nhập tên 3 người nhập số ghế là 2 thì nó toàn random ra 2 tên giống nhau -_-

void sapxep(nguoi a[],int n,int k){
	int j;
	for (int i=1;i<=k;i++){
		srand(time(NULL));
		j=rand()%n;
		printf("%s	 ",a[j]);	
	}
		
}

em chạy debug từ từ thì nó ra 2 tên khác nhau nhưng mà chạy bth thì ra giống nhau

Hoán vị sao lại dùng random? Ở đây có một ví dụ về hoán vị, bằng java nhưng mình nghĩ dễ hiểu thôi :))
Permutations.java

ở đây em mới thử random tên thôi chứ chưa động gì hoán vị anh à :smiley:

Đặt srand(time(NULL)) lên trước vòng for

%n thì nó thu hẹp phạm vi lại rồi.
Như n = 2 thì chỉ có 1 và 0 -> 50% trùng
n = 3 thì kq chỉ là 1 2 0 -> 1/3 khả năng trùng…
n càng lớn tỷ lệ trùng càng nhỏ

3 Likes

ồ vậy chắc không dùng được rồi :smile: chắc em phải làm bài này theo thuật toán sinh quá

cảm ơn anh :smile: em giải theo cách khác không dùng rand nữa :smiley:

1 Like

Nếu anh biết cách làm thì chỉ cho em với được không :cry: bí lắm rồi

Dạng bài liệt kê tổ hợp hoặc hoán vị này thường có 2 cách đơn giản nhất để làm đó là dùng phương pháp sinh hoặc đệ quy lui, cả 2 pp này bạn có thể tham khảo trong cuốn giải thuật và lập trình của Lê Minh Hoàng

bài này em đọc từ cuốn thầy LMH đây :cry:

vậy thì bạn dùng đệ quy lui mà làm, chứ sao lại dùng rand cho nó phức tạp, hàm rand rất khó kiểm soát

Yup hqua giờ ngồi thử dùng thuật đẻ mà rắc rối quá nên đọc xuống thấy quay lui dễ hiểu hơn :wink:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?