n! cũng mất (n-1)*log2(n)
bit rồi mà để như ban đầu cũng là nlog2(n).
Có thể giảm xuống còn bao nhiêu phần tử nữa mà vẫn lưu trữ đủ danh sách N số đã được sinh ngẫu nhiên
nhân vào giảm bit chứ, ví dụ lưu 0,1,2,3 mất 1+1+2+2=6 bit, lưu 0 tới 3!=6 chỉ mất 3 bit thôi =]
lưu từng số một mất bit
lưu index của N! mất bit
ăn gian được mấy cái ceil(…) :V :V
Thật ra cách bạn đang nói là cách xác định cấu hình của một hoán vị dựa vào số thứ tự của nó trong từ điển.
Nhưng làm sao biết được số nào đã có , số nào chưa có, thông qua cái số index đó.
đã giải thích ở trên rồi mà, ví dụ N=4, index=5 thì
f(4, 5, 0) = 0
f(4, 5, 1) = 3
f(4, 5, 2) = 2
f(4, 5, 3) = 1
số trước đó đã được lưu trong cái index đó rồi :V
5 = 0*3! + 2*2! + 1*1! + 0*0!
tức là
số đầu tiên sẽ là số index 0 trong 4 số [0,1,2,3] là số 0
số thứ hai sẽ là số index 2 trong 3 số [1,2,3] là số 3
số thứ ba sẽ là số index 1 trong 2 số [1,2] là số 2
số cuối cùng sẽ là số index 0 trong 1 số [1] là số 1
edit: à mà chuyển từ index về cấu hình thì cũng phải lưu 1 cái mảng n chữ số rồi bóc ra từ từ nhỉ :V :V :V Vậy nói cần 1 phần tử cũng đâu có đúng :V
Vậy bạn nào hiểu vấn đề rồi, có thể tóm tắt lại một số điểm được không, để mình tich solution nào? HUhu
Không cần, anh có thể sinh ra được cấu hình của nó khi biết được vị trí và số phần tử mà.
Mình thấy topic này có liên quan gì đến C/C++ đâu.
bài này sao có solution được :V :V
cần chứ, ví dụ N=4, index=5, số đầu tiên là 0, rồi tiếp theo đòi index 2 trong 3 số còn lại, vậy phải nhớ 3 số còn lại là số mấy :V
Vì mình thấy. liên quan đến mảng hoặc danh sách liên kết, nói chung là cấu trúc dữ liệu và nó phải ở trong C/C++ nên nó liên quan đến C/C++
hầu hết ngôn ngữ nào cũng có mảng và dslk hết :V
Biết là vậy, nhưng ý nói là vấn đề này được áp dụng trong C/C++, nên nó liên quan đấy. Vì có thể có project = C/C++
Đơn giản hóa đề bài.
Vừa sinh vừa in ra luôn, khỏi lưu.
ngôn ngữ khác ko liên quan sao? Bộ ko viết hàm sinh số ngẫu nhiên ko trùng lặp bằng Java hay C# hay Python Ruby Go Rust Pascal v.v… gì được à :V
sửa title nha :V
vậy thế phải có bước xác định xem “phần tử đấy đã có chưa” và “bao giờ thì đủ phần tử” nếu không in mãi
trong C/C++ cũng có hàm “random” mà :), thì dùng nó thôi.
C/C++ nào có hàm random :V
Có vẻ bạn vẫn chưa hiểu cách làm này.
- rand một lần duy nhất lấy index
- từ index sinh số ngẫu nhiên
Vd với n = 3
thì có các cấu hình:
0 # 0 1 2
1 # 0 2 1
2 # 1 0 2
3 # 1 2 0
4 # 2 0 1
5 # 2 1 0
Rand được số 3 thì các số ngẫu nhiên là [1, 2, 0]
.
Java C# Python v.v… gì cũng có hàm sinh số ngẫu nhiên vậy ~.~
cái gì C/C++ có C# Java Python có hết :V
nhưng chiều ngược thì đâu có đúng, nên mình mơi chỉ giới hạn trong cái vòng tròn nhỏ thôi
vậy thì chừng nào hỏi chiều ngược lại cái gì đặc biệt mà chỉ có ngôn ngữ X mới có hoặc bắt buộc code bằng X thì hẵn liên quan tới X :V
nguyên cả cái đề em có thấy chữ C/C++ nào ko? :V :V
Cần sinh ngẫu nhiên N phần tử có giá trị từ 0 đến (N-1). Vấn đề là khi dùng hàm sinh ngẫu nhiên có thể sinh ra một số đã được sinh ở lần trước, khi đó lại gọi hàm ngẫu nhiên cho đến khi nào sinh được một phần tử không nằm trong danh sách đã sinh ra trước đó.
Vậy cần có một mảng lưu danh sách các phần tử đã được sinh, mảng này nếu khai báo thông thường thì phải chứa N phần tử.Chẳng hạn cần sinh ngẫu nhiên 6 phần tử từ 0 đến 5; để biết đã sinh được bao nhiêu phần tử thì ta cần một mảng có 6 phần tử. Lý do dùng mảng chứ không dùng danh sách liên kết vì tốc độ truy cập của mảng nhanh chóng hơn DSLK nhiều.
Câu hỏi, mảng này có thể giảm xuống còn bao nhiêu phần tử nữa mà vẫn lưu trữ đủ danh sách N số đã được sinh ngẫu nhiên.
nếu nói liên quan tới Java chắc cũng ko ai biết là liên quan tới C/C++?