dungnv
» dequy
» dequyctdlgt
» Liệt kê các xâu tạo bởi hoán vị của các chữ A,B,C,D,E,F mà D,E,F đứng cạnh nhau.
Liệt kê các xâu tạo bởi hoán vị của các chữ A,B,C,D,E,F mà D,E,F đứng cạnh nhau.
Friday, December 19, 2014
giải thuật đệ quy, hoán vị
Liệt kê các xâu tạo bởi
hoán vị của các chữ A,B,C,D,E,F mà D,E,F đứng cạnh nhau.
Bài sử dụng giải thuật đệ quy quay lui. Tạo 2
lớp đệ quy lồng nhau để liệt kê các hoán vị.
Ø Hoán vị 4 chữ cái
có 4!=24 xâu.
Ø Hoán vị của 3 chữ
cái có 3!=6 xâu.
Ø Tổng cộng có 24 x 6 = 144
xâu.
Code c/c++
#include <stdio.h>
#include <conio.h>
char s[5]="ABCX",a[5],
d[4], ss[4]="DEF";
int b[5],bb[4],dem=0;
void xuat()
{
char c[7];
int i=0,j=0;
c[6]=NULL;
while(a[i]!=NULL)
{
if (a[i]=='X')
{
c[j]=d[0];
c[j+1]=d[1];
c[j+2]=d[2];
j=j+3;
}
else
{
c[j]=a[i];
j++;
}
i++;
}
dem++;
printf("\n%d",dem);
printf("\n%s",c);
}
void hoanvi3(int
n)
{
for(int
k=0;k<3;k++)
if (bb[k])
{
d[n]=ss[k];
if (n==2) xuat();
else
{
bb[k]=0;
hoanvi3(n+1);
bb[k]=1;
}
}
}
void hoanvi(int
i)
{
for(int
j=0;j<4;j++)
if (b[j])
{
a[i]=s[j];
if (i==3) hoanvi3(0);
else
{
b[j]=0;
hoanvi(i+1);
b[j]=1;
}
}
}
int main()
{
a[4]=NULL;
for(int
i=0;i<5;i++) b[i]=1;
for(int
i=0;i<4;i++) bb[i]=1;
hoanvi(0);
getch();
}
Mong các bạn
góp ý ở phía dưới. Nhớ bấm G+ ủng hộ
nguyenvandung.net
All comments [ 0 ]
Your comments