-
- Nhắc lại một số kiến thức đại số tổ hợp:
- Chỉnh hợp lặp:
- Cho một tập X gồm n(n ∈ N*) phần tử. Một dãy có độ dài m(m ∈ N*) các phần tử của X, trong đó mỗi phần tử có thể lặp lại nhiều lần, sắp xếp theo một thứ tự nhất định gọi là một chỉnh hợp lặp chập m của n phần tử.


- Bài tập vận dụng: Ta cho tập hợp X gồn n phần tử có n phần tử (1,2,3…n)
- Ví dụ: n=2, k=3:
Liệt kê các cấu hình: 111, 112, 121, 122, 211, 212, 221, 222
Cấu hình đầu: 111
Cấu hình cuối: 222
Thuật toán:
- In ra cấu hình đầu:
- Xét từ cuối dãy về đầu dãy gặp chữ số nào chưa = n
- + Gán tất cả các số đằng sau bằng 1

- Code C++
//Sinh các chỉnh hợp lặp chập k của n phần tử
#include<bits/stdc++.h>
using namespace std;
int n,k,i,vt;
//hàm in xâu
void display(int *a, int k)
{
for (i=0;i<k;i++)
{
cout<< a[i];
}
cout<<endl;
}
//trả về 1 xét xâu tiếp theo
void replace(int *a, int k, int vt)
{
for (i=vt;i<k;i++)
{
a[i]=1;
}
}
//xây dựng và in xâu tiếp theo
void nextstring(int *a, int n, int k)
{
i=k-1;
while (i>0)
{
if (a[i]==n)
i--;
if (a[i]<n)
{
a[i]++;
replace(a,k,i+1);
display(a,k);
i=k-1;
}
}
}
int main()
{
cout<<"Nhập vào n và k: ";
cin >> n >> k;
//khai báo mảng chứa xâu con
int *a = new int[n]; //cấp mảng động cho mảng a
//Khởi tạo xâu ban đầu
for (i=0;i<=k;i++)
{
a[i] = 1;
}
//In xâu con
display(a,k);
nextstring(a, n, k);
return 0;
}
Số lượt xem: 1,587