Giúp Tối ưu Code Tính Tổ Hợp Chập K Của N - Dạy Nhau Học Trang chủ » To Hợp Chập K Của N ư ớ C » Giúp Tối ưu Code Tính Tổ Hợp Chập K Của N - Dạy Nhau Học Có thể bạn quan tâm Tổ Hợp Chiêu Thị Là Gì Tổ Hợp Chỉnh Hợp Tổ Hợp Chỉnh Hợp Bài Tập Tổ Hợp Chỉnh Hợp Bấm Máy Tổ Hợp Chỉnh Hợp C++ Giúp tối ưu code tính tổ hợp chập k của n programming c++ Trung_Hieu_Vu1 (Trung Hiếu Vũ) August 28, 2021, 7:56am #1 Viết chương trình tổ hợp chập k của n theo ct dưới đây: C(k,\ n)=\frac{n!}{k!×(n-k)!} Giới hạn đầu vào 1<= k <= n <= 25 Giới hạn thời gian: 1000MS Giới hạn bộ nhớ: 256 MB Đây là code của em #include<bits/stdc++.h> using namespace std; unsigned long long gt(int n) { unsigned long long tich = 1; for(int i = 1; i<=n; i++) { tich *= i; } return tich; } unsigned long long tohop(int n, int k) { return gt(n) / (gt(k)*gt(n-k)); } int main() { int n, k; cin >> n >> k; if (k>n) { cout << "Nhap lai: "; } else { cout << tohop(n, k); } return 0; } Em làm như trên nhưng vẫn bị TLE. Mong mn có code nào giúp tối ưu hóa thì giúp em với ạ rogp10 (rogp10) August 28, 2021, 1:32pm #2 Từ \large\binom n m bạn tính lên \large\binom {n+1}{m+1}. 3 Likes Trung_Hieu_Vu1 (Trung Hiếu Vũ) August 28, 2021, 2:01pm #3 Vậy sẽ là return gt(n+1)/(gt(k+1)*gt((n+1)-(k+1))) phải ko ạ rogp10 (rogp10) August 28, 2021, 2:25pm #4 Không phải. Khai triển \large \frac {\binom {n+1}{m+1}}{\binom n m} để tìm công thức truy hồi, rồi tìm điểm bắt đầu nữa là xong. 3 Likes tntxtnt () August 28, 2021, 3:38pm #5 có giải thích chi tiết ở đây nè :V Tổ hợp chập k của n phân tử mà chỉ dùng for programming 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 ý ạ :(( 3 Likes Sena (Sena Alaire) August 29, 2021, 9:39am #6 Bác tạo 1 hàm lưu lũy thừa sẽ không bị TLE nữa, vì mình không cần tính lại mà đúng không. Có gì lấy giá trị lũy thừa từ mảng lưu vào là được rồi nè. noname00 (HK boy) August 29, 2021, 11:16am #7 25! lớn hơn giới hạn của int64 nên không thể tính tổ hợp chập k của n bằng công thức giai thừa được. 2 Likes Trung_Hieu_Vu1 (Trung Hiếu Vũ) August 29, 2021, 11:21am #8 vậy tính bằng cách nào vậy ạ, em xem công thức của câu hỏi y chang em vẫn chưa hiểu lắm, mong anh giải thích rogp10 (rogp10) August 29, 2021, 11:50am #9 Trong đó giống cách mình vừa nói đấy. 2 Likes Trung_Hieu_Vu1 (Trung Hiếu Vũ) August 29, 2021, 12:09pm #10 ok để mình nghiên cứu thử xem Mle (Mle) March 17, 2023, 2:40pm #11 #include <bits/stdc++.h> using namespace std; long long NcR(int n, int r) { long long p = 1, k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; // gcd of p, k long long m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else p = 1; return p; } // Driver code int main() { int n, r; scanf("%d",&r); scanf("%d",&n); printf("%lld",NcR(n, r)); return 0; } DayNhauHoc's Discord Học C++ Free? Click Blog Dạy Nhau Học Tự Học Lập Trình 83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao? Từ khóa » To Hợp Chập K Của N ư ớ C Công Thức Tính Số Tổ Hợp Chập K Của N Phần Tử Và Ví Dụ Công Thức Tính Số Tổ Hợp Chập K Của N Phần Tử Và Tính Chất Liên Quan ... Tổ Hợp Chập K Của N C++? - Tạo Website Tính Tổ Hợp Chập K Của N - Cộng đồng C Việt Tổ Hợp Chập K Của N Phân Tử Mà Chỉ Dùng For - Dạy Nhau Học CTDL Và Giải Thuật - In Ra Tất Cả Những Tổ Hợp Chập K Của N Thuật Toán Tính Tổ Hợp - Cách Tính Tổ Hợp Trong C++ Viết Chương Trình Tính Tổ Hợp Chập K Của N Trong C Liệt Kê Tất Cả Tổ Hợp Chập K Của N Phần Tử - YouTube Tổ Hợp (toán Học) – Wikipedia Tiếng Việt Toán Học Tổ Hợp – Wikipedia Tiếng Việt Thuật Toán Đệ Quy Và Một Số Bài Toán Đệ Quy Cơ Bản - VN SEEDER Hoán Vị, Chỉnh Hợp Và Tổ Hợp: Công Thức Và Các Dạng Chi Tiết Tóm Tắt Kiến Thức đại Số Tổ Hợp - Lập Trình & Tư Duy Thuật Toán (Kì 2)