老掉牙的 全排列问题

类别:VC语言 点击:0 评论:0 推荐:

这是我很早写的程序,算是灌水文章

全排列程序的一种思路

                                                      

    一个数的全排列,如2的全排列为12,21;共2个;3的全排列为123,132,213,231,312,321;共6个……。全排列在很多地方都有重要的应用,但是要产生但是一个数的全排列,却并不如我们想象的那么简单,(不信您可以先不看文章中的程序,自己编写一个的产生算法),本文笔者利用一种棋盘思路,编写了一个全排列的程序。

我们知道一个数n的全排列,就是自然数从1到n的没有重复的全部排序,排成一个排列后,以后排的排列不能与之重复。我们可以用如下方法简单地化解。

设想有一种棋,棋盘为n×n格,棋子共n个,要求每行和每列不能有两个或两个以上的棋子,要求它的棋子的全部可能的布局。下图为4×4棋盘的一种布局。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

其实用心思考以下,这就是一个数n全排列的等价命题。因为每行和每列不能有重复的棋子,而棋盘又是正方形,它的棋子的全部可能的布局,就相当于数n的一个排列。

可以用如下的思路下棋,首先在第1行第1列处放置一个棋子,然后开始放第2行,因为第1列已经放了棋子,故只能放置在第2列上,然后放第3列…..一直放到第n行。这样算是完成了一个排列,接下来排第2个排列,注意:此时的状态不要改变,将第n-1行上的棋子从左边第一个格子开始向右移动一格,看看是否与前n-2行的棋子冲突(不要管第n行的棋子),如果冲突便将棋子再向右移动一格,再看是否有冲突,直到不发生冲突为止,如果找不到这样的一个位置,可不管第n行和第n-1行棋子,用第n-2棋子作同样的实验,直到找到一个位置为止,否则,将所用的棋子行号减1,作同样的实验,直到找到一个位置后。用同样的方法排下一行的棋子,当排到第n行时便又完成一个排列。当第1行的棋子中排到最右边的一个棋格时而再排将不能排时,便完成了棋盘的全部布局,此时全排列结束。

下面是其程序,用C++语言编写。

#include <stdio.h>

#include <iostream.h>

int Row[15];///用于模拟棋盘,其中数组下标为行号,所赋的值为棋子所在的列号

int i;

int CanSet(int k) /////判断第k行上棋子能否放在当前列上

{

         int j;

         j=1;

         while(j<k){

                  if(Row[j]==Row[k])return 0;///只要和前边的行上的棋子有冲突便不成功

                  j++;

         }

         return 1;

}

void QuanPaiLie(int n)//////全排列实现函数

{

         int k;

         Row[1]=0;////第1次,第1行上也没放置棋子

         k=1;/////开始放置第1行

         while(k>0){

                  Row[k]=Row[k]+1;////将棋子向右移动一格

                  while(Row[k]<=n&&(CanSet(k)<1)){

                            Row[k]=Row[k]+1;////不能放则重复向右移动棋子

                   };

                  if(Row[k]<=n){////我们找到了一个位置,那么可以放下棋子了

                            if(k==n){

                                     for(i=1;i<=n;i++)printf("%d ",Row[i]);////已经放完了n行一个排列完成了,

                                                   ////将它们打印出来

                                     printf("\n");/////换一行

                            }else{

                                     k=k+1;////如果还没有放完,继续放

                                     Row[k]=0;////从最左边开始放

                            }

                  }else{

                                     k=k-1;/////向上一行,看看是否有别的放法

                   }

                  

         }

 

 

}

void main()

{

         int n;

         printf("enter your num to pailie:");

         cin>>n;

          QuanPaiLie(n);

 

}

 

本程序在TC++3.0和VC5.0上均调试通过。

                                            1997/6/10

                                      于合肥电子工程学院

#####完##

 

本文地址:http://com.8s8s.com/it/it2654.htm