mình làm bài này thì mắc vào 1 vấn đề mà mãi kô giải quyết được, (hình như có liên quan đến Quy hoạch động, mà mình chưa học).
với 1 xâu có n kí tự thì sẽ có 2^n -2 tập kt con (bỏ rỗng và chính nó)
giả sử
Input : ABCD
Output: A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ABD,ACD,BCD
có (2^4)-2 =14.
mình làm theo hướng mỗi tập kt con sẽ được biểu diễn = 1 số nhị phân đúng n bit. (n là số p tử xâu).
ví dụ 0001 = D, 0011 = CD ..v..v
nhưng bị hạn chế bộ nhớ lưu các xâu con vì nó lại phụ thuộc vào độ dài n.
đây là code, đoạn này chỉ chạy đc với n=10, trên 10 là lỗi ngay
PHP Code:
#include <stdio.h>
#include <string.h>
#include <math.h>
char N[100]; // Luu xau ban dau can tim xau con.
char M[100]; // Luu xau nhi phan
char xaucon[1024][100]; //Luu cac xau con
int main(void)
{
int in,i,m;
//bien in dung luu so trung gian khi tim nhi phan
//Bien i,m dung chay vong lap
int num;
//Bien num dung luu so xau con cua 1 xau, num=2^(strlen)
int x, y, j, k,l;
//Bien x luu 2 gia tri 0,1
//bien y de lap
//Bien j,k de tang
printf("Nhap xau N: ");
fflush(stdin);gets(N);
num = pow(2,strlen(N));
printf("Se co %d xau con\n",num-2);
for(m=1;m<num-1;m++)
{
x = y = j =0;
k=0;
in=m;
for(y = strlen(N)-1; y >= 0; y--)
{
x = in / (1 << y);
in = in - x * (1 << y);
if(x==0)
{
M[j]='0';
}
else
{
M[j]='1';
}
j++;
}
for(i=0;i<strlen(M);i++)
{
if(M[i]=='1')
{
xaucon[m-1][k]=N[i];
k++;
}
}
printf("\n---> Xau con so %d = %s ",m,xaucon[m-1]);
}
return 1;
}
vấn đề là ở biến xaucon, làm sao để không bị hạn chế vì độ dài n nhỉ, mình không rành C cho lắm nên bó tay
thanks