di4.txt

对有名的"跳马问题",利用递归与回朔法,通过C语言来实现

跳马问题

16.(*)( 6_24  p.197  )

int map[12][12], status[12][12]，kp;

int c[8][2]={{2,1},{2,-1},{1,2},{1,-2},

             {-2,1},{-2,-1},{-1,2},{-1,-2}};

void prt(int a[][12])  /* 打印棋盘状态 */

{int i,j,i2,j2;

 printf("\n");

 for (i=2;i<=9;i++)

  { for (j=2;j<=9;j++)  printf("%4d",a[i][j]);

    printf("\n");

  }

 }

void status2(void)  /* 计算棋盘各点条件数 */

{ int i,j,k,i2,j2,kz;

  for(i=0;i<12;i++)

    for(j=0;j<12;j++)

      status[i][j]=100;

  for(i=2;i<=9;i++)

    for(j=2;j<=9;j++)

     {kz=0;

      for (k=0;k<=7;k++)

       {i2=i+c[k][0];j2=j+c[k][1];

         if (map[i2][j2]<50)  kz++;

        }

      status[i][j]=kz;

     }

  prt(status);

 }

void sort1(int b1[],int b2[])  /* 对8个可能的方向按条件数排序 */

{int i,j,mini,t; /*b1[]记录状态值（升序），b2[]记录排序后的下标 */

 for (i=0;i<7;i++)

  {mini=i;

   for (j=i+1;j<=7;j++)

     if (b1[j]<b1[mini])   mini=j;

   t=b1[i];b1[i]=b1[mini];b1[mini]=t;

   t=b2[i];b2[i]=b2[mini];b2[mini]=t;

  }

 }

void init1(void)  /* 初始化 */

{int i,j,k;

 for(i=0;i<12;i++)

   for(j=0;j<12;j++)

      map[i][j]=100;

 for(i=2;i<=9;i++)

   for(j=2;j<=9;j++)

      map[i][j]=0;

 status2();

}

void search(int i2,int j2) /* 利用递归回溯进行搜索 */

 {int b1[8],b2[8],i,i3,j3;

  kp++;

  if(kp==65)

    {prt(map);  exit(0); }

  for(i=0;i<=7;i++)

   {b2[i]=i;

    b1[i]=status[i2+c[i][0]][j2+c[i][1]];

    }

  sort1(b1,b2);

  for(i=0;i<=7;i++)

    {i3=i2+c[b2[i]][0]; j3=j2+c[b2[i]][1];

     if (map[i3][j3]==0)

       { map[i3][j3]=kp;  search(i3,j3); map[i3][j3]=0;

      }

     }

  kp--;

 }

main()

{init1();

 map[5][2]=1; kp=1;

 search(5,2);

}

运行结果：

   2   3   4   4   4   4   3   2

   3   4   6   6   6   6   4   3

   4   6   8   8   8   8   6   4

   4   6   8   8   8   8   6   4

   4   6   8   8   8   8   6   4

   4   6   8   8   8   8   6   4

   3   4   6   6   6   6   4   3

   2   3   4   4   4   4   3   2

 

  32  17   42    3   34   19   44    5

  41   2   33   18   43    4   35   20

  16  31   64   53   38   59    6   45

   1  40   61   58   63   52   21   36

  30  15   54   39   60   37   46    7

  55  12   57   62   51   48   25   22

  14  29   10   49   24   27    8   47

  11  56   13   28    9   50   23   26

 

17. ( ex 6_32 p.201  选择排序，利用递归实现 )

void select(int a[],int begin,int n)

{int i,t,min;

 min=begin;

 for (i=begin+1;i<n;i++)

   if(a[i]<a[min])  min=i;

 t=a[begin]; a[begin]=a[min]; a[min]=t;

 if (begin<n-1)

   select(a,begin+1,n);

}

main()

{int a[10]={5,6,7,99,1,2,0,45,21,-97};

 int i,n=10;

 for(i=0;i<=n-1;i++)   printf("%5d ",a[i]);

 printf("\n");

 select(a,0,n);

 for(i=0;i<=n-1;i++)

   printf("%5d ",a[i]);

 printf("\n");

}


18.( ex 6_25 p.202  二分查找，递归方法 )

void binsearch(int b[],int x,int low,int high)

{int mid;

 if (low>high)

  {printf("\n%d dosn't exists in the array!\n",x);

   exit(0);

  }

 mid=(low+high)/2;

 if(x==b[mid])

   {printf("OK! b[%d]=%d\n",mid,x);

    exit(0);

   }

 if(x>b[mid])

   binsearch(b,x,mid+1,high);

 else

   binsearch(b,x,mid,high-1);

}

main()

{int a[10]={2,3,4,5,7,10,20,40,50,100};

 int key,n=10;;

 printf("input a number for search:\n");

 scanf("%d",&key);

 binsearch(a,key,0,n-1);

}