VL07 - Tính tổ hợp
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Viết chương trình tính tổ hợp chập ~k~ của ~n~ phần tử có công thức như dưới đây:
$$C_{n}^{k} = \frac{n!}{k!(n-k)!}$$
Giới hạn
- ~ 1 \le k \le n \le 25 ~
Input
Lần lượt là 2 số n, k cách nhau bởi khoảng trắng
Output
Kết quảtổ hợp chập ~k~ của ~n~
Sample
Input #1
5 2
Output #1
10
Bình luận
full ac: #include <iostream> using namespace std;
long long dp[30][30];
long long C(int n, int k) { if (k == 0 || k == n) return 1;
}
int main() { int n, k; cin >> n >> k;
}
**#include <iostream>
include <cmath>
using namespace std;
int main() { int n;cin>>n; int k;cin>>k; if (1<=k && k<=25 && k<=n ){ long long M1 =1; long long M2 =1; for (int i=1;i<=k;i++){ M1 = (M1)i; } for (int j=n;j>=(n-k+1);j--){ M_2 = (M_2)j; } cout << ((M2)/(M1)) << endl; } return 0; } **
khoi sex voi ngan ban
k
n phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượngquyềndung tiến phượng
include <iostream>
include <iomanip>
using namespace std; int main() { int n, k; long long s1 = 1, s2 = 1; do { cin >> n; cin >> k; } while (n > 25 && k > n && k < 1); int max = k; int min = n - k; if (max <= n - k) { max = n - k; min = k; } for (int i = n; i > max; i--) s1 *= i; for (int i = 1; i <= min; i++) s2 *= i; cout << s1 / s2;
}
include<bits/stdc++.h>
using namespace std;
long long f(int n){ long long r=1; for(int i=1;i<=n;i++) r*=i; return r; }
int main(){ ios::syncwithstdio(0); cin.tie(0); int n,k; cin>>n>>k; cout<<f(n)/(f(k)*f(n-k)); return 0; }
include<stdio.h>
int main(){
}
còn case 5 check giúp e với
Case cuối:
n = 25, k = 3
Nếu bạn tính như thế thì với n = 25 chắc chắn sẽ gây tràn số
Thay vì như thế: Ông hãy áp dụng chút toán vào để giải:
Ta gọi phần n! là tử Phần k!(n - k)! là mẫu
Đầu tiên: Ta có thể rút gọn đi !k (n >= k)
Thì lúc này Tử: (k + 1)*(k + 2) * ... * n Mẫu: 1 * (n - k)!
Tiếp theo ta nhận ra là: Phần giao nhau giữa tử và mẫu, chính là từ : (k + 1) * (k + 2) * ... * (n - k); Ta có thể rút gọn tử và mẫu cho nhau, từ đó ra kết quả bài toán còn lại chính là:
Tử: tích của i chạy từ (n - k + 1) -> n Mẫu: tích của i chạy từ 1 -> n - (n - k) = k
Và đây là code mẫu của mình:
include <bits/stdc++.h>
define MOD 1000000007
define Mod7 1000000006
define en '\n'
define Siz(s) s.size()
define wel 1005
define pb push_back
define mang 1000001
using namespace std;
typedef unordered_map<long long, long long> unmap;
int main() { //freopen("", "r", stdin); //freopen("", "w", stdout); iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; // Mẫu: n - k: bắt đầu từ 1 -> n - k // Tử: bắt đầu từ a đến n // --> Dưới mẫu sẽ còn lại gia thừa từ 1 -> a // --> Trên tử sẽ còn lại : !((n - k) + 1) -> n; long long mau = 1, tu = 1; for(int i = 1 ; i <= k ; ++i) mau *= i; for(int i = (n - k + 1) ; i <= n ; ++i) tu *= i; long long ans = tu/mau; cout << ans; return 0; }
đa tạ cao nhân đã chỉ điểm
cho mình xin test 4, 5 cái
Mọi người lưu ý khi test với số 23 11. Sẽ bị tràn số, bên dưới là code tham khảo! Supplier<Long> combinationCalculator = () -> { long result = 1; for (int i = 0; i < Math.min(k, n - k); i++) result = result * (n - i) / (i + 1); return result; };
case 4 là gì thế mn :'(
test case 5 là gì v
25 3 đó
cho mình xin testcase 3 với mn ơi
n = 15 k = 10
hàm tính C bằng đệ quy cho ai cần int C(int a, int b) { if (a == 0 or a == b) return 1; if (a == 1) return b; return C(a - 1, b - 1) + C(a, b - 1); }
case cuối là gì v mn
help với ,C++20
mong admin lên cho hiện phần dữ liệu test case như các web code leet code để khi sai tìm lỗi cho dễ ạ
Công thức bên trên chỉ chạy được một phần thôi, chạy số to hơn tí là tràn bộ nhớ rồi nên phải dùng công thức truy hồi mới đúng.
testcase cuối là gì ấy nhỉ
25 voi 3 do loi tran so ban xem lai nhe