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

#41

Giả dụ, người giải quyết vấn đề này biết mỗi C/C++ thì dĩ nhiên là phải giải quyết = C/C++ rồi, đấy là yêu cầu mà.

#42

Vậy đưa ra thuật là được rồi. Có code hộ đâu mà phải dùng C/C++. :slight_smile:

4 Likes
#43

giải thích mệt mỏi quá :V Nếu xin code giải quyết bằng C/C++ thì đề phải nói, đằng này đề có nói gì tới nnlt nào đâu :V

5 Likes
#44

thì mình nói trên title của mình thây. Không hẳn là xin code, nhưng với mỗi vấn đề thì có thêm không gian (như là trong ngôn ngữ lập trình nào) thì người đọc dễ định hương hơn. Chỉ vậy thôi.

Thôi không nói nữa.

#45

chuyển từ index về cũng cần 1 mảng n phần tử đây :V

#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>
#include <vector>

class FlatWeightTree {
public:
    FlatWeightTree(int n) : heap(twoPowCeil(n) * 2, 0) {
        const int N = heap.size() / 2;
        std::fill(begin(heap) + N, begin(heap) + N + n, 1);
        for (int i = N; i-- > 1;) heap[i] = heap[i * 2] + heap[i * 2 + 1];
    }
    int pop(int i) {
        int j = 1;
        const int N = heap.size() / 2;
        for (; j < N; --heap[j / 2])
            if (i >= heap[j *= 2]) i -= heap[j++];
        heap[j] = 0;
        return j - N;
    }

private:
    static int twoPowCeil(int n) {
        for (int ret = 1;; ret *= 2)
            if (ret >= n) return ret;
    }

private:
    std::vector<int> heap;
};

int fact(int n) {
    int res = 1;
    while (n) res *= n--;
    return res;
}

int main() {
    int N = 4;
    std::mt19937 prbg(time(0));
    int id = std::uniform_int_distribution<>{0, fact(N) - 1}(prbg);
    std::cout << "Index = " << id << "\n";

    FlatWeightTree fwt(N);
    for (int j = N, n = fact(j - 1); j--;) {
        std::cout << fwt.pop(id / n) << ' ';
        id %= n;
        if (j) n /= j;
    }
}
4 Likes
#46

N/10 là lưu như thế này

filter_by_tens[N / 10] = {...};
// filter_by_tens[i] là 1 số 10 bit,
// mỗi bit j biểu thị rằng số i * 10 + j đã được sinh

64 em đoán là lấy từ cận trên của max long long 2^63 - 1 :v

filter_by_64[N / 64] = {...};
// filter_by_tens[i] là 1 số 64 bit,
// mỗi bit j biểu thị rằng số 64 * i + j đã được sinh :v
3 Likes
#47

thì đúng rồi, từ số x-bit chuyển về 1-bit thì giảm được còn N/x “phần tử”. Cái lạ là ko phải N/32 mà là N/10 và N/64 vì int có 32 bit :V :V :V chả lẽ khi nghĩ tới số N “trong C/C++” thì nghĩ tới số 10-bit hoặc 64-bit??? @_@

mà tác giả trên facebook kia có nói mảng 128 phần tử đã chết chương trình thì ko biết lập trình nhúng xuống đất hay nhúng lên trời mà ko tạo được mảng 128 phần tử…

lạ lùng hơn nữa 128 là 7-bit, ko biết đào đâu ra số 10 và số 64

4 Likes
#48

Lười đến thế là cùng. :v
Thay mỗi tens thành 64 thôi mà. :smile:

3 Likes
#49

Mảng 1 phần tử thôi nha. Là phần tử đó là 1 string, ví dụ: “5-3-4-1-2-0”
:rofl:
Thỏa yêu cầu đề nha:

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.

:relieved:

3 Likes
#50

Thì đó. Coi như là 1 thuật toán nén đi.
Tốn nhiều tài nguyên lưu trữ thì tốn ít tài nguyên để giải nén và ngược lại :smile:

4 Likes
#51

String bản chất vẫn là mảng ký tự thôi :rofl: còn tốn mem hơn mảng số nữa :v

3 Likes
#52

Mình không quan tâm optimize nha. Mình chỉ trả lời đúng câu hỏi là “bao nhiêu” thôi. :wink:

1 Like
#53

Để đọc ra được số mấy thì dãy số đầy đủ cần n*(log2(n)+1) bit, áp dụng ct Stirling thì số bit tối đa xêm xêm n(log2(n) - log2(e)) => vẫn nén được :slight_smile:

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