Tổ hợp chập k của n phân tử mà chỉ dùng for

[Tiramin (Tira)]

có cách nào tính tổ hợp chập k của n phần tử mà không sử dụng hàm, không sử dụng truy hồi và đệ quy không nhỉ? Chỉ dùng mỗi vòng lập for. Nếu có cho em xin gợi ý ạ :((

[Tiramin (Tira)]

mình thử phân tách n! rồi k! (n-k)! nhưng ráp lại thì nó lại thành dùng hàm mất rồi :((

[Nobita1 (BK Anonymous)]

hơi cùi, nhưng nếu giới hạn về bộ nhớ lớn thì không giải được: áp dung công thức này

C\binom{n}{k} = C\binom{n-1}{k-1} + C\binom{n-1}{k}

Cài đặt bằng mảng 2 chiều ấy.

[hungaya (Hung)]

Chơi ăn gian thôi.

long combinatoric(int n, int k) {
    long cn  = 1; // n!
    long ck  = 1; // k!
    long cnk = 1; // (n-k)!

    for (int i = 2; i <= n; i++) {
        cn *= i;
        if (i == k) ck = cn;
        if (i == n-k) cnk = cn;
    }

    return cn / (ck * cnk);
}

[tntxtnt]

áp dụng công thức rồi tính thôi, rút gọn 1 tí:

\frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)...(n-k+1)}{1 \cdot 2 \cdot 3 \cdot ... \cdot k}

để ý:
n sẽ chia hết cho 1
n(n-1) sẽ chia hết cho 2 (2 số liên tiếp sẽ có 1 số chẵn)
n(n-1)(n-2) sẽ chia hết cho 6 (3 số liên tiếp sẽ có ít nhất 1 số chẵn và 1 số chia hết cho 3)
v.v…

vậy xài 1 vòng for chạy là được :V

int result = 1;
for (int i = n, j = 1; j <= k; --i, ++j)
    result = result * i / j;

[Tiramin (Tira)]

khó hiểu quá ạ

[tntxtnt]

khó hiểu chỗ nào :V

em chạy tay thử n=13 k=5 là thấy ngay ấy mà

\frac{\color{red}13!}{\color{green}5!\color{blue}8!} = \frac{\color{red}\cancel{1} \cdot \cancel{2} \cdot \cancel{3} \cdot ... \cdot \cancel{8} \cdot 9 \cdot ... \cdot 12 \cdot 13}{\color{green}1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot \color{blue}\cancel{1} \cdot \cancel{2} \cdot \cancel{3} \cdot ... \cdot \cancel{8}} = \frac{\color{red}9 \cdot 10 \cdot 11 \cdot 12 \cdot 13}{\color{green}1 \cdot 2 \cdot 3 \cdot 4 \cdot 5}

latex

\frac{\color{red}13!}{\color{green}5!\color{blue}8!} = \frac{\color{red}\cancel{1} \cdot \cancel{2} \cdot \cancel{3} \cdot ... \cdot \cancel{8} \cdot 9 \cdot ... \cdot 12 \cdot 13}{\color{green}1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot \color{blue}\cancel{1} \cdot \cancel{2} \cdot \cancel{3} \cdot ... \cdot \cancel{8}} = \frac{\color{red}9 \cdot 10 \cdot 11 \cdot 12 \cdot 13}{\color{green}1 \cdot 2 \cdot 3 \cdot 4 \cdot 5}

tổng quát lại thì được như cái hình trên:

\frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)...(n-k+1)}{1 \cdot 2 \cdot 3 \cdot ... \cdot k}

latex

\frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)...(n-k+1)}{1 \cdot 2 \cdot 3 \cdot ... \cdot k}

ở đây chạy ngược từ n về n-k+1 nhưng chạy từ n-k+1 lên n cũng được :V

rồi em quan sát:
9 chia hết cho 1
(9)x10 chia hết cho (1)x2
(9x10)x11 chia hết cho (1x2)x3
(9x10x11)x12 chia hết cho (1x2x3)x4
(9x10x11x12)x13 chia hết cho (1x2x3x4)x5
vậy là bảo đảm result = result * i / j chia ko bị bớt mất phần nào :V

chứng minh cái này cũng rất, rất dễ :V :V https://math.stackexchange.com/questions/12065/the-product-of-n-consecutive-integers-is-divisible-by-n-factorial Ví dụ tích của a, a+1, a+2, …, a+n-1 sẽ luôn chia hết cho n! vì kết quả phép chia đó chính là tổ hợp chập n của a+n-1 :V là 1 số nguyên:
9 chia hết cho 1 vì kết quả đó chính là tổ hợp chập 1 của 9
(9)x10 chia hết cho (1)x2 vì kết quả đó chính là tổ hợp chập 2 của 10
(9x10)x11 chia hết cho (1x2)x3 vì kết quả đó chính là tổ hợp chập 3 của 11
(9x10x11)x12 chia hết cho (1x2x3)x4 vì kết quả đó chính là tổ hợp chập 4 của 12
(9x10x11x12)x13 chia hết cho (1x2x3x4)x5 vì kết quả đó chính là tổ hợp chập 5 của 13

vậy là để tính tổ hợp chập 5 của 13 ta cần tính tổ hợp chập 4 của 12, rồi lấy kết quả đó nhân 13, chia 5 (nhân trước chia sau) là ra :V Đệ quy:

return k ? choose(n - 1, k - 1) * n / k : 1;

[Tiramin (Tira)]

Em cảm ơn ạ! Em nghiên cứu ngay ạ!

[Canh_Le_Van (Cảnh Lê Văn)]

lớp mấy thì học nhiều về cái này ạ

chứ cái for các thứ em chưa có hok đến
năm nay mới vào 10 à

[noname00 (HK boy)]

Chưa học thì bây giờ học thôi, lớp mấy học không quan trọng.