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 ý ạ :((
Bạn đang xem: Tổ hợp chập k của n c++
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 sẽ chia hết cho 1n(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
Xem thêm: Cách Gộp Phân Vùng Ổ Cứng Không Mất Dữ Liệu ? Cách Gộp Ổ Cứng Không Mất Dữ Liệu
khó hiểu quá ạ
\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:
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(9×10)x11 chia hết cho (1×2)x3(9x10x11)x12 chia hết cho (1x2x3)x4(9x10x11x12)x13 chia hết cho (1x2x3x4)x5vậ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(9×10)x11 chia hết cho (1×2)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:
