Một số bài tập C _C++ NC 2026P23
BÀI 68. Kiểm tra một sâu có phải là sâu đối xứng
BÀI LÀM
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
cout<
cin>>s;
string check="";
for(int i=s.length()-1;i>=0;i--){
check+=s[i];
}
if(check==s) cout<
else cout << "day khong phai day doi xung";
return 0;
}
CÁCH 2
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
cout<
cin>>s;
bool check=true;
int l=s.length();
for(int i=0;i<s.length()/2;i++){
if(s[i]!=s[l-1-i]){
check=false;
break;
}
}
if(check==true) cout<
else cout << "day khong phai day doi xung";
return 0;
}
Bài 69. Cho mảng gồm n phần tử . Hãy liệt kê các cặp phần tử có tổng bằng s.
Input | Output |
10 12 4 5 6 7 8 9 10 12 11 15
|
4,8 5,7 |
BÀI LÀM
#include<bits/stdc++.h>
using namespace std;
long long n,a[100005];
long long s;
long long dem=0;
int main(){
cin>>n;
cin>>s;
for (int i= 1; i
cin>>a[i];
for (int i=1; i< n; i++)
for (int j= i+1; j
if((a[i]+a[j])==s) dem++;
if((a[i]+a[j])==s) cout <<a[i]<<","<<a[j]<<endl;
}
if(dem!=0) cout<<endl;
else cout<<"-1";
return 0;
}
Bài 69.b. Cho mảng gồm n phần tử . Hãy đếm các cặp phần tử có tổng bằng s.
( trong dãy có tổng không bằng s thì đưa ra -1)
Input | Output |
8 10 234 55 66 88 99 12 18 11 (10 12 2 3 4 5 6 7 8 9 10 11) | -1
4 |
BÀI LÀM
#include<bits/stdc++.h>
using namespace std;
long long n,a[100005];
long long s, dem;
int main(){
cin>>n;
cin>>s;
for (int i= 1; i
cin>>a[i];
for (int i=1; i< n; i++)
for (int j= i+1; j
if((a[i]+a[j])==s) dem ++;
}
if(dem> 0)cout<<dem;
else cout<< "-1";
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love06.07.2026
////////////////////
Bài 70
Cho dãy số gồm n số nguyên a1, a2, …, an và 2 số nguyên không âm L, R (L ≤ R).
Yêu cầu: Đếm số cặp (i, j) thỏa mãn điều kiện: i < j và L ≤ |ai+…+aj| ≤ R .
Dữ liệu vào: Từ file văn bản cb70.txt gồm:
Hai số nguyên đầu file là giá trị L, R (0 ≤ L ≤ R ≤ 107)
Các số nguyên tiếp theo là mảng: a1, a2,…, an (ai ≤ 107)
Kết quả: Ghi ra file văn bản cb70out.txt thông báo kết quả (i,j) >>tong
#include
#include
#include
using namespace std;
vectorTM(vectoraa){
vectorvi={0};
int sum=0;
for(int c:aa){
sum+=c;
vi.push_back(sum);
} return vi;
}
int main(int argc, char** argv) {
cout<
cout<
ifstream fin("cb70.txt");
if (!fin.is_open()) {
cerr<
return 0;}
int L, R, x;
fin>>L>>R;
if(L*RR||L>1e7||R>1e7){
cerr<
for (int i=1;i<=n-1;i++){
for (int j=i+1;j<=n;j++){
int y=abs(vv[j]-vv[i-1]);
if(y>=L&&y
}
}
ofstream fout("cn70out.txt");
fout<
for (int i=1;i<=n-1;i++){
for (int j=i+1;j<=n;j++){
int y=abs(vv[j]-vv[i-1]);
if(y>=L&&y
}
}
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love05.07.2026
////////////////////
Bài 71. ( dãy con tăng dài nhất và chia hết cho số trước nó không liên tiếp)
Một dãy gồm N số nguyên dương a1,a2,...,an được gọi là dãy con hoàn toàn nếu aj chia hết cho ai với mọi j>i, ví dụ dãy 3, 15, 60, 720 là dãy con hoàn toàn (dãy không liên tiếp)
Yêu cầu: Tìm dãy con hoàn toàn có độ dài lớn nhất.
Dữ liệu vào: dãy số nguyên a1,a2,...,an. Mỗi số cách nhau một dấu cách.
Dữ liệu ra: ghi ra file kqcb71.txt độ dài lớn nhất dãy con hoàn toàn.
Ví dụ: file cb71.txt 10 2 3 4 8 9 27 145 81 320 1 3 5 7 9 2 4 8 16 1 23 79 14 39 145 76 320
Gợi ý code:
#include
#include
#include
using namespace std;
int ddc(vectordc){
int max=0;
int l=0;
int r=dc.size()-1;
for(int j=dc.size()-1;j>0;j--){
int max1=0;
for (int i=0; i<=j;i++){
if(dc[j]%dc[i]==0) max1++;
} if(max
max=max1;
r=j;
l=r-max1+1;
}
} return max;
}
int main(int argc, char** argv){
cout<
cout<
ifstream fin("cb71.txt");
if (!fin.is_open()) {
cerr<
return 0;}
int x;
vectorv;
while(fin>>x){
if(x2e8) {
cerr<<"so "<<x<
continue;}
v.push_back(x);
} fin.close();
int zv=v.size()-1;
vectorvv;
int L,R,max=0;
for (int i=0;i<zv;i++){
vv.clear();
L=i;R=i;
vv.push_back(v[i]);
for(int j=i+1;j<=zv;j++){
if(v[j]>v[R]){
vv.push_back(v[j]);
R=j;
}
}
if(max
}
cout<
ofstream fout("kqcb71.txt");
fout<
fout.close();
return 0;
}
/////////////////
Cách 2: thông báo độ dài dãy con hoàn toàn và các phần tử mảng
#include
#include
#include
using namespace std;
vectorddc(vectordc){
vectortemp;
int max=0;
int l=0;
int r=dc.size()-1;
for(int j=dc.size()-1;j>0;j--){
int max1=0;
for (int i=0; i<=j;i++){
if(dc[j]%dc[i]==0) max1++;
} if(max
max=max1;
r=j;
}
}
for (int i=0;i
if(dc[r]%dc[i]==0) temp.push_back(dc[i]);}
return temp;
}
int main(int argc, char** argv){
cout<
cout<
ifstream fin("cb71.txt");
if (!fin.is_open()) {
cerr<
return 0;}
int x;
vectorv;
while(fin>>x){
if(x2e8) {
cerr<<"so "<<x<
continue;}
v.push_back(x);
} fin.close();
int zv=v.size()-1;
vectorvv,kq;
int L,R,max=0;
for (int i=0;i<zv;i++){
vv.clear();
L=i;R=i;
vv.push_back(v[i]);
for(int j=i+1;j<=zv;j++){
if(v[j]>v[R]){
vv.push_back(v[j]);
R=j;
}
}
if(max
max=ddc(vv).size();
kq=ddc(vv);
}}
cout<
cout<
cout<<endl;
ofstream fout("kqcb71.txt");
fout<
fout<
for(int val : kq) fout<<val<<" ";
fout<<endl;
fout.close();
return 0;
}
//////////////////////////
Cách 3:
#include
#include
#include
using namespace std;
vectorddc(vectordc){
vectorbest;
vectortemp;
for (int i = 0; i < dc.size(); i++) {
temp.clear();
temp.push_back(dc[i]);
for (int j = i+1; j < dc.size(); j++) {
if (dc[j] % temp.back() == 0 /*&& dc[j] > temp.back()*/) {
temp.push_back(dc[j]);
}
}
if (temp.size() > best.size()) best = temp;
}
return best;
}
int main(){
cout<
ifstream fin("cb71.txt");
if (!fin.is_open()) {
cerr<
return 0;
}
int x;
vectorv;
while(fin>>x){
if(x2e8) {
cerr<<"so "<<x<
continue;
}
v.push_back(x);
}
fin.close();
vectorresult = ddc(v);
cout<
cout<
for(int val : result) cout<<val<<" ";
cout<<endl;
ofstream fout("kqcb71.txt");
fout<
fout<
for(int val : result) fout<<val<<" ";
fout<<endl;
fout.close();
return 0;
}
Chú ý:
Nếu em muốn giữ đúng ý bài toán (chỉ tăng dần, không cho phép bằng nhau), thì cần thêm điều kiện dc[j] > temp.back() vào đoạn kiểm tra:
if (dc[j] % temp.back() == 0 && dc[j] > temp.back()) {
temp.push_back(dc[j]);
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love06.07.2026
////////////////////
Bài 72. Cho dãy gồm số nguyên a1, a2, a3, ..... (|ai|<=10 9 ) Hãy đếm và đưa ra số đặc biệt trong dãy a. Số đặc biệt là số chỉ xuất hiện đúng 1 lần trong dãy số.
Vd: Đầu vào file: Cb72.txt có dữ liệu: 2 3 4 8 9 7 5 8 3 5
Đầu ra: file: KQcb72.txt sẽ là: 4 || 2 4 9 7
BÀI LÀM
#include
#include
#include
#include
// #include <bits/stdc++.h>
using namespace std;
int main(){
mapma;
vectorv;
cout<
ifstream fin("Cb72.txt");
if (!fin.is_open()) {
cerr<
return 0;
}
long long x;
int dem;
while(fin>>x){
if(abs(x>1e9)) {
cerr<<"so "<<x<
continue;
}
v.push_back(x);
ma[x]++;
if(ma[x]==1) dem++;
if(ma[x]==2) dem--;
}
fin.close();
cout<
}
cout<<endl;
ofstream fout("KQcb72.txt");
fout<
} fout<<endl;
fout.close();
return 0;
}
/////////////////////////
Cách 2: unordered_map (nhanh hơn map)
#include
#include
#include
#include
using namespace std;
int main(){
unordered_mapfreq;
vectorv;
ifstream fin("Cb72.txt");
if(!fin.is_open()){
cerr<
return 0;
}
long long x;
while(fin>>x){
if(abs(x)>1e9){
cerr<<"So "<<x<
continue;
}
v.push_back(x);
freq[x]++;
}
fin.close();
int dem=0;
for(auto &p:freq) if(p.second==1) dem++;
cout<
for(auto c:v) if(freq[c]==1) cout<<c<<" ";
cout<<endl;
ofstream fout("KQcb72.txt");
fout<
for(auto c:v) if(freq[c]==1) fout<<c<<" ";
fout<<endl;
fout.close();
}
///////////////////////////
Cách 3: sort + duyệt tuyến tính
#include
#include
#include
#include
using namespace std;
int main(){
vectorv;
ifstream fin("Cb72.txt");
if(!fin.is_open()){
cerr<
return 0;
}
long long x;
while(fin>>x){
if(abs(x)>1e9){
cerr<<"So "<<x<
continue;
}
v.push_back(x);
}
fin.close();
sort(v.begin(), v.end());
vectorspecial;
for(int i=0;i<v.size();){
int j=i+1;
while(j
if(j-i==1) special.push_back(v[i]);
i=j;
}
cout<
for(auto c:special) cout<<c<<" ";
cout<<endl;
ofstream fout("KQcb72.txt");
fout<
for(auto c:special) fout<<c<<" ";
fout<<endl;
fout.close();
}
//////////////////////////
Cách 4: Xử lý như chuỗi (stringstream)
#include
#include
#include
#include
#include
using namespace std;
int main(){
ifstream fin("Cb72.txt");
if(!fin.is_open()){
cerr<
return 0;
}
stringstream buffer;
buffer << fin.rdbuf();
fin.close();
string s;
mapfreq;
vectorv;
stringstream ss(buffer.str());
while(ss >> s){
freq[s]++;
v.push_back(s);
}
int dem=0;
for(auto &p:freq) if(p.second==1) dem++;
cout<
for(auto &c:v) if(freq[c]==1) cout<<c<<" ";
cout<<endl;
ofstream fout("KQcb72.txt");
fout<
for(auto &c:v) if(freq[c]==1) fout<<c<<" ";
fout<<endl;
fout.close();
}
Chú ý:
ü fin.rdbuf()
fin là một ifstream (luồng đọc file).
rdbuf() trả về con trỏ tới buffer bên trong của luồng đó.
Khi ta viết buffer << fin.rdbuf(); tức là ta lấy toàn bộ nội dung file và đẩy vào stringstream buffer.
Kết quả: buffer chứa nguyên văn nội dung file dưới dạng chuỗi.
Nói nôm na: fin.rdbuf() là cách nhanh để copy toàn bộ nội dung file vào một stringstream.
ü stringstream ss(buffer.str())
buffer.str() lấy ra chuỗi string từ stringstream buffer.
Sau đó ta khởi tạo một stringstream ss mới từ chuỗi đó.
stringstream ss cho phép ta dùng toán tử >> để tách chuỗi thành từng token (số hoặc từ), giống như đọc từ file.
Ví dụ: nếu file có "2 3 4 8 9", thì buffer.str() sẽ là "2 3 4 8 9".
Rồi stringstream ss(buffer.str()) cho phép ta đọc lần lượt 2, 3, 4, 8, 9 bằng ss >> s.
Tóm lại
- fin.rdbuf() → lấy toàn bộ nội dung file.
- buffer.str() → chuyển nội dung đó thành một chuỗi.
- stringstream ss(buffer.str()) → tạo luồng đọc từ chuỗi, để dễ tách từng số/từ.
Cách rdbuf() + stringstream chỉ hữu ích khi muốn xử lý file như một chuỗi text (ví dụ tìm kiếm, thay thế, phân tích cú pháp).
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love07.07.2026
////////////////////
Bài 72. Em hãy viết chương trình nhập dữ liệu từ file “mang72.txt” chứa dãy số nguyên rồi đếm số nhóm gồm 3 số mà tổng của 2 số trong nhóm có hàng đơn vị lần lượt là các số 8, 9, 5 hoặc 8,9,3 hoặc 8,9,0 .VD: đầu vào: 3 4 5 6 1 2 7 8 9 5 60 10 20 70 40 30 -1 9 11.
Đầu ra: file “kqcb72.txt”
#include
#include
#include
#include
using namespace std;
bool thoa(int a, int b, int c){
int x = abs((a+b) % 10);
int y = abs((b+c) % 10);
int z = abs((a+c) % 10);
if((x+y==17)&&(z==5||z==3||z==0)) return true;
if((z+y==17)&&(x==5||x==3||x==0)) return true;
if((x+z==17)&&(y==5||y==3||y==0)) return true;
return false;
}
int main(int argc, char** argv) {
vectorv,kq;
cout<
ifstream fin("mang72.txt");
if (!fin.is_open()) {
cerr<
return 0;
}
int x, dem=0;
while(fin>>x){
if(abs(x) > 1e9) {
cerr<<"so "<<x<
continue;
}
v.push_back(x);
}
fin.close();
int n=v.size();
for(int i=0; i
for(int j=i+1; j
for(int k=j+1; k
if(thoa(v[i], v[j], v[k])){
dem++;
kq.push_back(v[i]);
kq.push_back(v[j]);
kq.push_back(v[k]);
}
}
}
}
cout<
int mi=0;
if(kq.size()>0){cout<
mi+=3;
}}
ofstream fout("kqcb72.txt");
int mii=0;
fout<
if(kq.size()>0){fout<
mii+=3;
}}
fout.close();
return 0;
}
Chú ý: Hầu như không nhóm nào thỏa mãn trường hợp bộ (8, 9, 0)
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love07.07.2026
////////////////////
Bài 73. Tìm độ dài của dãy con tăng có độ dài lớn nhất ( dãy con không liên tiếp) và thông báo các phần tử dãy con đó.
VD: input: cb73.txt 1 2 5 4 6 2
Output: Kqcb73.txt
#include
#include
#include
using namespace std;
int main(int argc, char** argv) {
vectorv,kq;
cout<
ifstream fin("cb73.txt");
if (!fin.is_open()) {
cerr<
return 0;
}
int x,L, maxL=0;
while(fin>>x){
if(abs(x) > 1e9) {
cerr<<"so "<<x<
continue;
}
v.push_back(x);
}
fin.close();
for (int i=0;i<v.size()-1;i++){
int dem=1,max=v[i];
for(int j=i+1;j<v.size();j++){
if(v[j]>max){
dem++;
max=v[j];
}
} if(maxL
maxL=dem;
L=i;
}
} int dmax=v[L];kq.push_back(dmax);
for (int i=L+1;i<v.size();i++){
if(v[i] >dmax) {
dmax=v[i];
kq.push_back(dmax);
}}
cout<
cout<
}
ofstream fout("Kqcb73.txt");
fout<
fout<
}
fout.close();
return 0;
}
///////////////////////////////////
Bài tham khảo:
#include
#include
#include
using namespace std;
int LIS(vector& v) {
vectortail;
for (int x : v) {
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
}
return tail.size();
}
int main() {
vectorv = {10, 22, 9, 33, 21, 50, 41, 60};
cout << "Do dai LIS: " << LIS(v) << endl;
return 0;
}
Chú ý:
lower_bound(tail.begin(), tail.end(), x)
Đây là hàm trongdùng binary search để tìm vị trí đầu tiên trong mảng tail mà giá trị ≥ x.
Nếu tất cả phần tử trong tail đều nhỏ hơn x, thì it sẽ trỏ tới tail.end().
Nếu có phần tử nào đó ≥ x, thì it sẽ trỏ tới vị trí đó.
if (it == tail.end()) tail.push_back(x);
Trường hợp này nghĩa là x lớn hơn tất cả phần tử trong tail.
→ Ta thêm x vào cuối tail, tức là ta vừa mở rộng dãy tăng.
else *it = x;
Nếu tìm thấy vị trí có phần tử ≥ x, ta thay thế phần tử đó bằng x.
→ Việc này giữ cho tail luôn chứa các phần tử nhỏ nhất có thể ở mỗi độ dài LIS.
Nhờ vậy, ta tối ưu khả năng mở rộng dãy tăng về sau.
Ví dụ: v = [10, 22, 9, 33, 21, 50]
Bước 1: tail = [10]
Bước 2: gặp 22 → lớn hơn 10 → tail = [10, 22]
Bước 3: gặp 9 → thay thế 10 bằng 9 → tail = [9, 22]
Bước 4: gặp 33 → lớn hơn 22 → tail = [9, 22, 33]
Bước 5: gặp 21 → thay thế 22 bằng 21 → tail = [9, 21, 33]
Bước 6: gặp 50 → lớn hơn 33 → tail = [9, 21, 33, 50]
Kết quả: độ dài LIS = 4.
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love07.07.2026
////////////////////
Bài 74. Cho một dãy gồm n phần tử nguyên dương |ai|
VD: file input: cb74i.txt 92 69 16 82 170 31 24 45 112 200 40 92 68 1 2 3 4 5 6 7 8 9 hoặc 100000 20 99974 1 2 3 4 5 6 7 8 9 0
Cách 1:
#include
#include
#include
using namespace std;
void Try(int s, vector& arr, int start, int &dem) {
if (s == 0) {
dem++;
return;
}
for (int i = start; i < arr.size(); i++) {
if (s - arr[i] >= 0) {
Try(s - arr[i], arr, i+1, dem);
}
}
}
int main() {
vectorv;
cout << "Chuong trinh tim so day con co tong bang S:\n";
ifstream fin("cb74i.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file cb74i.txt\n";
return 0;
}
int s;
fin >> s; // phần tử đầu tiên là S
if (s1e7) {
cerr << "So " << s << " khong hop le\n";
return 0;
}
int x;
while (fin >> x) {
if (x1e9) {
cerr << "So " << x << " khong hop le\n";
continue;
}
v.push_back(x);
}
fin.close();
if (v.size() > 100) {
cerr << "Mang co qua nhieu phan tu (>100)\n";
return 0;
}
int dem = 0;
Try(s, v, 0, dem);
cout << "So day con co tong bang " << s << " la: " << dem << endl;
ofstream fout("Kqdcb74o1.txt");
fout << "So day con co tong bang " << s << " la " << dem << endl;
fout.close();
return 0;
}
///////////////////////
Cách 2: Bài 74b. Cho một dãy gồm n phần tử nguyên |ai|
VD: file input: cb74i.txt 92 69 16 82 170 31 24 45 112 200 40 92 68 1 2 3 4 5 6 7 8 9 hoặc 100000 20 99974 1 2 3 4 5 6 7 8 9 0 hoặc 0 20 99974 1 2 3 4 5 6 7 8 9 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 hoặc 0 9 0 -1 -8 -9 0
File output: Kqdcb74o.txt
#include
#include
#include
#include
using namespace std;
void Try(long long s, const vector& arr, int start, long long &dem) {
if (start >= arr.size()) return;
for (int i = start; i < arr.size(); i++) {
Try(s - arr[i], arr, i+1, dem);
}
if (s == 0) {
dem++;
return;
}
}
int main() {
vectorv;
cout << "Chuong trinh tim so day con co tong bang S:\n";
ifstream fin("cb74i.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file cb74i.txt\n";
return 0;
}
long long s;
fin >> s;
if (abs(s) > 1e7) {
cerr << "Tong S vuot qua gioi han 10^7\n";
return 0;
}
long long x;
while (fin >> x) {
if (abs(x) > 1e7) {
cerr << "So " << x << " khong hop le (vuot 10^7)\n";
continue;
}
v.push_back(x);
}
fin.close();
if (v.size() > 100) {
cerr << "Mang co qua nhieu phan tu (>100)\n";
return 0;
}
long long dem = 0;
Try(s, v, 0, dem);
cout << "So day con co tong bang " << s << " >= " << dem << endl;
ofstream fout("Kqdcb74o.txt");
fout << "So day con co tong bang " << s << " >= " << dem << endl;
fout.close();
return 0;
}
////////////////////////////
Cách 3:
#include
#include
#include
#include
using namespace std;
void Try(long long s, const vector& arr, int start, long long &dem, int countChosen) {
if (s == 0 && countChosen > 0) {
dem++;
}
if (start >= arr.size()) return;
for (int i = start; i < arr.size(); i++) {
Try(s - arr[i], arr, i+1, dem, countChosen+1);
}
}
int main() {
vectorv;
cout << "Chuong trinh tim so day con co tong bang S:\n";
ifstream fin("cb74i.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file cb74i.txt\n";
return 0;
}
long long s;
fin >> s;
if (abs(s) > 1e7) {
cerr << "Tong S vuot qua gioi han 10^7\n";
return 0;
}
long long x;
while (fin >> x) {
if (abs(x) > 1e7) {
cerr << "So " << x << " khong hop le (vuot 10^7)\n";
continue;
}
v.push_back(x);
}
fin.close();
if (v.size() > 100) {
cerr << "Mang co qua nhieu phan tu (>100)\n";
return 0;
}
long long dem = 0;
Try(s, v, 0, dem,0);
cout << "So day con co tong bang " << s << " >= " << dem << endl;
ofstream fout("Kqdcb74o2.txt");
fout << "So day con co tong bang " << s << " la " << dem << endl;
fout.close();
return 0;
}
//////////////////
Cách 4: tối ưu:
#include <bits/stdc++.h>
using namespace std;
int n;
long long S;
vectora;
vectorcurrentSubset;
ofstream fout;
void Try(int idx, long long sum) {
if (sum == S) {
// In ra một tập con hợp lệ
fout << "{ ";
for (auto x : currentSubset) fout << x << " ";
fout << "}\n";
return;
}
if (idx >= n || sum > S) return; // dừng nếu vượt quá
// Chọn phần tử a[idx]
currentSubset.push_back(a[idx]);
Try(idx + 1, sum + a[idx]);
currentSubset.pop_back();
// Bỏ qua phần tử a[idx]
Try(idx + 1, sum);
}
int main() {
cout << "Chuong trinh in ra cac tap con co tong bang S:\n";
ifstream fin("cb74i.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file cb74i.txt\n";
return 0;
}
fin >> S;
long long x;
while (fin >> x) {
if (abs(x) > 10000000) {
cerr << "Gia tri " << x << " khong hop le (vuot 10^7)\n";
continue;
}
a.push_back(x);
}
fin.close();
n = a.size();
fout.open("Kqcb74i.txt");
fout << "Tong S = " << S << "\n";
fout << "Cac tap con co tong bang S:\n";
Try(0, 0);
fout.close();
cout << "Ket qua da duoc ghi vao file Kqcb74i.txt\n";
return 0;
}
Giải thích
- Hàm Try(idx, sum) duyệt đệ quy:
- Nếu sum == S → in ra tập con hiện tại.
- Nếu sum > S hoặc hết mảng → dừng.
- Gọi tiếp với việc chọn hoặc bỏ phần tử a[idx].
- currentSubset lưu tập con đang xét.
- Kết quả được ghi vào file Kqcb74i.txt.
///////////////////////
Cách 5 tham khảo:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long S;
cout << "Nhap so phan tu n va tong S can tim: ";
cin >> n >> S;
if (n100) {
cerr << "So phan tu phai trong khoang 1..100\n";
return 0;
}
if (abs(S) > 10000000) {
cerr << "Tong S khong duoc vuot qua 10^7\n";
return 0;
}
vectora(n);
cout << "Nhap " << n << " phan tu cua mang (chi so nguyen duong):\n";
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i]10000000) {
cerr << "Chi ho tro so nguyen duong
return 0;
}
}
// dp[t] = số tập con có tổng bằng t
vectordp(S + 1, 0);
dp[0] = 1; // có 1 cách chọn tập rỗng để được tổng 0
// Quy hoạch động: duyệt từng phần tử
for (int i = 0; i < n; i++) {
for (int j = S; j >= a[i]; j--) {
dp[j] += dp[j - a[i]];
}
}
cout << "So tap con co tong bang " << S << " la: " << dp[S] << endl;
ofstream fout("Kqcb74i.txt");
fout << "So tap con co tong bang " << S << " la: " << dp[S] << endl;
fout.close();
return 0;
}
Giải thích
- dp[t] lưu số lượng tập con có tổng bằng t.
- Khởi tạo dp[0] = 1 (tập rỗng).
- Với mỗi phần tử a[i], duyệt ngược từ S về a[i]:
- Nếu đã có dp[j - a[i]] tập con, thì thêm a[i] vào sẽ tạo thêm dp[j - a[i]] tập con có tổng bằng j.
- Cộng dồn vào dp[j].
Khi dp[S]=1 hoặc true với boolean thì kết luận có tập con.
Vd: 100000
20 99974 1 2 3 4 5 6 7 0
Dp[100000]=1 >> có tập con có tong = 100000
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love08.07.2026
////////////////////ok
Nhận xét
Đăng nhận xét