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! cũng mất (n-1)*log2(n) bit rồi :smiley: mà để như ban đầu cũng là nlog2(n).

2 Likes

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 png bit
lưu index của N! mất png bit

ăn gian được mấy cái ceil(…) :V :V

5 Likes

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 đó.

1 Like

đã 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

6 Likes

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à. :slight_smile:


Mình thấy topic này có liên quan gì đến C/C++ đâu. :thinking:

1 Like

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

2 Likes

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

4 Likes

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. :smiling_imp:

3 Likes

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

5 Likes

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

1 Like

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]. :slight_smile:

1 Like

ý mình cái hàm này thôi
here

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

3 Likes

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++?

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