PDA

View Full Version : cho mình xin thuật toán RANDOM...



themummy
09-04-2005, 00:48
mình có một tập 100 quân bài, mình muốn chia nó thành 5 phần, 3 phần có 19 lá bài, 1 phần có 20 lá, 1 phần còn lại có 23 lá. (chia một cách ngẫu nhiên).??

themummy
11-04-2005, 16:39
hổng ai biết cái này sao?

bete
12-04-2005, 06:58
themummy coi thử ở đây đi:

http://ddth.com/showthread.htm?t=60978

-thân

htbn_hoang
12-04-2005, 10:11
Chào bạn, bạn dùng 1 mảng đánh dấu, trong trường hợp này là b[100] (vì có 100 phần tử). Trong lần đầu tiên, bạn lặp 19 lần (bộ đầu) và dùng đoạn sau để xác định quân bài
while (b[d]!=0)
d = rand()%100;
Bạn làm tương tự với các bộ khác tùy thuộc vào số quân trong mỗi bộ mà ta sẽ lặp lại tương ứng bấy nhiêu lần. Riêng bộ cuối, bạn không cần lặp vì số quân còn lại đương nhiên thuộc bộ cuối.
Lưu ý : bạn dùng hàm srand() để khởi tạo bộ sinh số ngẫu nhiên
vd srand((unsigned int)time(null));
dùng hàm rand() để lấy số ngẫu nhiên.Hàm rand() trả về số 32 bit, nếu lấy số nhỏ hơn n thì ghi như sau d = rand()%n;
Mảng b dùng để đánh dấu, do đó bạn dùng giá trị gì cũng được, tui hay dùng 0 là chưa dùng còn 1 là đã dùng.
Trong các bài toán ngẫu nhiên, bạn chỉ cần xác định ngẫu nhiên chỗ nào, và dùng d=rand()%n tại chỗ đó là được.

bete
13-04-2005, 01:58
Thân gửi htbn_hoang: mình đã có bàn sơ sơ về cách giải bài này trong thread trước rồi phải không !? Tui xin thử bàn thêm thêm 1 chút nghen:

Cách xài 1 mảng đánh dấu chắc chắn là được rồi. Nói nôm na nó là như vầy: mình có 1 rổ banh đánh số từ 1 tới 50 chẳng hạn. Giả sử mình cần lấy ra hết 50 trái theo 1 thứ tự ngẫu nhiên => mình bốc ngẫu nhiên 1 trái: nếu đã bị đánh dấu rồi thì BỎ LẠI VÔ RỔ; nếu chưa đánh dấu thì mình ghi số thứ tự trên trái banh xuống 1 tờ giấy rồi đánh dấu nó và cũng BỎ LẠI VÔ RỔ. Cứ làm như vậy hoài cho tới khi ghi xuống được 50 trên tờ giấy => 50 số này sẽ có thứ tự ngẫu nhiên

Nhưng cách trên có vẻ "không được tự nhiên" cho lắm. Bình thường, mình sẽ làm như vầy: mình bốc ngẫu nhiên 1 trái: ghi số thứ tự trên trái banh xuống 1 tờ giấy rồi BỎ QUA MỘT BÊN. Cứ làm như vậy hoài cho tới khi ghi xuống được 50 trên tờ giấy => 50 số này sẽ có thứ tự ngẫu nhiên

Chỗ khác nhau giữa 2 cách là "BỎ LẠI VÔ RỔ" và "BỎ QUA MỘT BÊN":

"BỎ QUA MỘT BÊN" => số banh trong rổ ngày càng ít đi & mình chỉ cần bốc 50 lần là xong

"BỎ LẠI VÔ RỔ" => số banh trong rổ lúc nào cũng là 50; số banh bị đánh dấu càng lúc càng tăng; số banh chưa bị đánh dấu càng lúc càng giảm => càng lúc càng khó bốc ra ra 1 trái banh chưa bị đánh dấu => số lần bốc chắc chắn chắn lớn hơn hay bằng 50 (xác suất lớn hơn 50 là khá cao)

Xét về "độ ngẫu nhiên" thì cả 2 cách đều có vẻ tốt như nhau

Tui xài cụm từ "tự nhiên" hay "không tự nhiên" cũng hơi mơ hồ: nếu đặt bài toán theo kiểu "có 1 mảng ........" thì cách giải "đánh dấu" có vẻ "tự nhiên" hơn (hầu hết mọi người kể cả tui sẽ nghĩ theo hướng này). Nhưng nếu đặt bài toán theo kiểu "có 1 rổ banh ......" thì chắc hầu hết mọi người sẽ làm theo kiểu "BỎ QUA MỘT BÊN" thay vì làm theo kiểu "BỎ LẠI VÔ RỔ"

(có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)

-thân

htbn_hoang
16-04-2005, 09:51
Chào bạn, đúng là mới nhìn thì có vẻ cả hai đều đáp ứng được tính chất ngẫu nhiên. Nhưng nếu bạn có học môn Xác Xuất Thống Kê, bạn sẽ hiểu rõ hơn vì sao chúng không tương đương. Ở đây tui chỉ nói sơ qua thôi.
Trước tiên chúng ta bàn về việc BỎ LẠI VÀO RỔ. Xác xuất để bốc được một số chưa dùng (lần đầu) là n/n = 1 (chắc chắn bốc được). Lần thứ hai là (n-1)/n và tương tự cho các lần sau. Vậy xác xuất để thu được n số theo một thứ tự ngẫu nhiên là n!/(n mu n).
Tiếp theo, chúng ta xét đến BỎ QUA MỘT BÊN. Chúng ta có thể coi như chúng ta bốc liên tiếp các con số, tức là ta đã thu được 1 chỉnh hợp của n số. Vậy xác xuất để thu được n số theo 1 thứ tự ngẫu nhiên là 1/n! vì chỉnh hợp n chập n là n!.
Vậy chúng ta có thể thấy hai xác xuất là khác nhau nên hai cách làm là khác nhau. Cách đầu tiên chi phí rất lớn vì xác xuất nhỏ. Còn cách thứ hai thì đỡ hơn nhiều trong trường hợp n lớn.
Như tui cũng đã có nói trong bài trước, chỉ khi nào người ta đặt nặng tính ngẫu nhiên (trong các bài toán khoa học) thì mới dùng cách đầu. Cách của bạn bete rất tốt, chúng ta có thể áp dụng rộng rãi. Vì tính chất ngẫu nhiên trong các bài toán chúng ta làm không yêu cầu cao.
Thân.

bete
16-04-2005, 12:06
Thân gửi bạn htbn_hoang: tui xin so sánh 2 cách làm theo 2 khía cạnh:

1) khía cạnh kết quả cuối cùng (outcome): có đúng n! khả năng cho 1 bộ n số khác nhau, bất kể là làm cách nào. Xác suất cho 1 mỗi khả năng là như nhau => 2 cách làm là tương đương

2) khía cạnh hiệu quả:

a) BỎ QUA 1 BÊN: bạn phân tích rất đúng: xác suất cho mọi khả năng (bộ n số khác nhau) là như nhau và là 1/n!

b) BỎ LẠI VÔ RỔ: xác suất cho mọi khả năng cuối cùng (bộ n số khác nhau) là như nhau và là 1/(n^n). Đáng lưu ý là có n! khả năng cuối cùng và xác suất cho mỗi khả năng là 1/(n^n) nhưng tổng xác suất cho các khả năng này lại là n!/(n^n): KHÔNG BẰNG 1. Lý do là vì có thêm những khả năng trung gian: bộ n số nhưng không khác nhau mà có số bị lặp

Từ 2 xác suất: p1=1/n! (BỎ QUA 1 BÊN) và p2=1/(n^n) (BỎ LẠI VÔ RỔ) mình có thể nghĩ 1 cách nôm na theo luật số lớn: muốn lấy trúng 1 bộ n số khác nhau chọn trước nào đó (kiểu dò vé số chẳng hạn) => phải thử bốc n! lần (BỎ QUA 1 BÊN) hoặc n^n (BỎ LẠI VÔ RỔ). Vì (n!) < (n^n) (đặc biệt nếu n đủ lớn thì n! là rất nhỏ so với n^n) có thể thấy nếu chọn BỎ LẠI VÔ RỔ sẽ tốn nhiều công sức hơn BỎ QUA 1 BÊN (mà kết quả cũng không tốt hơn về mặt độ ngẫu nhiên).

Cần nhấn mạnh thếm lần nữa là vì trong cả 2 cách: xác suất của mọi khả năng cuối cùng là như nhau => 2 cách có cùng độ ngẫu nhiên => tốt như nhau về khía cạnh kết quả cuối cùng (nếu mình không quan tâm tới chuyện lâu mau thì cách nào cũng tốt như nhau) => nếu mình quan tâm về tính ngẫu nhiên thì chọn cách nào cũng vậy thôi. Nói dài dòng thêm 1 chút về mặt độ ngẫu nhiên: 1 cách làm được coi là tốt nếu xác suất của các kết quả cuối cùng là phân bố đều

(Và cũng xin nói rõ lại là BỎ QUA 1 BÊN không phải là tui nghĩ ra mà học được từ 1 khóa về xác suất thôi)

(có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)

-thân

themummy
27-04-2005, 22:17
cam ơn các bạn, mình tìm ra rồi.... thanks

Phong Than2008
25-02-2009, 09:38
Chào các bạn mình có bào mày hỏi các bạn tí nha:
Một môn có 5 chương có tổng là m câu hỏi.Mìm muốm tạo các đề thi mỗi đề thi gồm n câu hỏi sao cho các đề không chùng nhau và mỗi đề đều có câu hỏi ở mổi chương

qvluom
26-02-2009, 12:27
mình có một tập 100 quân bài, mình muốn chia nó thành 5 phần, 3 phần có 19 lá bài, 1 phần có 20 lá, 1 phần còn lại có 23 lá. (chia một cách ngẫu nhiên).??

Ê bạn hỏi thuật toán tạo số ngẫu nhiên hay là chỉ cần giải được bài toán cụ thể đó. Thuật toán tạo số ngẫu nhiên thì hơi phức tạp chứ còn giải bài này thì mình hàm random của pascal là xong rồi.

thientu_1589
07-12-2009, 20:40
Các anh pzo, em đang làm đề tài về random number mà không biết viết code sao hết lại không được dùng hàm rand() nữa. Có ai bit về cái này giúp em xiu...
Cảm ơn nhiu nhiu

caocuongccc
11-12-2009, 10:59
anh ơi cho em hỏi bài toán này với . thank mấy anh nhiều .
cho 1 dãy chẵn các số nguyên duơng .đến lượt ai đi thi chọn bên phải hoặc bên trái nhất của dãy .người chiến thắng nếu tổng số của họ lớn hơn của người kia.số được chọn sẽ được xóa đi"tìm chiến thuạt để người chơi tháng .người chơi va máy choi may sẽ đuợ chọn ngẫu nhiên còn người thì tùy ý chọn 2 bên .
em cũng làm thử rồi mà ko bit làm từ chỗ nào gồm bao nhiêu hàm dùng cái dì để lưu trữ những con số và làm sao để máy chọn ngẫu nhiên ở 1 trong 2 bên vẫn biết là dùng randomize() nhưng ko dc .