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.

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 = 144xâ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(intn)

{

     for(intk=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(inti)

{

     for(intj=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(inti=0;i<5;i++) b[i]=1;

     for(inti=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