论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

关于全排列算法

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:46:17

我不知道大家有没有听说,明年起程序员考试就不分初,中,高级了,而我们软件专业明年就要过程序了,据说相当于考中程,或者还要难一些,虽然不知道消息的正确性,但这的确是我们的老师告诉我们的,所以老师就出一些题给我们练,下面是一道关于数学中全排列的算法的问题,编了我4天!真是的看起来轻易,编起来难..........下面给出我的源代码,并给大家解释我的思路:

/***********************************************/
void chang(char str[],int m)  /*定义循环左移函数(我没有用左移函数)*/
 {
  int i,j;
  char temp=str[0];
  for (i=0;i<m;i++) str[i]=str[i+1];
  str[i]=temp;
 }
void pai(char str[],int m,int n) /*定义全排列函数*/
{
 int k;
 void chang(char str[],int m);
 if (m<n)        /* 定 义 递 归 调 用 出 口  */
  {
   for (k=0;k<=m;k++)
    {
     pai(str,m+1,n); /*递归调用*/
     chang(str,m); /*调用左移函数*/
    }
  }
 else printf("%s\t",str);
}
#include "stdio.h"
main()
{char str[]="ABCD"; /*全排列字符,可以任意多个(相应的下面排列函数中参数"4"改成全排列字符的个数)*/
clrscr();
pai(str,0,4); /*这里参数0(下标)表示从第一个元素开始,4表示元素个数(不是下标)*/
getch();
}
/*********************************************/

下面我来解释一下,我花了近1天的时间,找到这样一个规律如下:
                           ┏ ABCD
                           ┣ BCDA
                 ┏ ABCD ━┫
                 ┃        ┣ CDAB
       ┏ ABCD ━╋ BCAD   ┗ DABC
       ┃        ┃         .
       ┃        ┗ CABD    .
ABCD ━┫                   .               
       ┃        ┏ BACD    .
       ┃        ┃         .
       ┗ BACD ━╋ ACBD   ┏ CBAD
                 ┃        ┣ BADC
                 ┗ CBAD ━┫
                           ┣ ADCB
                           ┗ DCBA
简化图如下所示 ==>
                     ┏ ABCD
                     ┣ BCDA
            ┏ ABC ━┫
            ┃       ┣ CDAB
    ┏ AB ━╋ BCA   ┗ DABC
    ┃      ┃        .
    ┃      ┗ CAB    .
A ━┫                .               
    ┃      ┏ BAC    .
    ┃      ┃        .
    ┗ BA ━╋ ACB   ┏ CBAD
            ┃       ┣ BADC
            ┗ CBA ━┫
                     ┣ ADCB
                     ┗ DCBA
大家看到了,以上就是一步一步循环左移就能得到所有全排列的数了.以上程序在Trubo C 2.0 中运行通过,假如大家还有什么疑问,请加我QQ:156301529,Email:rodgersnow@163.com,我们共同讨论.另外,我在想,假如是n个数或字符中取m个进行排列的话,该怎么改呢?目前正在考虑中,本人觉得难度很大,希望大家能帮帮我,请加我QQ,谢谢!
另附我在网上找到的经典全排列算法,叫"后补法",大家自己好好研究吧,在Trubo C 2.0 中运行通过了的.

#include <stdio.h>
void permutation(char a[], int m, int n)
{
int i;
char t;
if (m<n-1) {
permutation(a, m+1, n);
for (i=m+1;i<n;i++) {
t=a[m]; a[m]=a[i]; a[i]=t;
permutation(a, m+1, n);

t=a[m]; a[m]=a[i]; a[i]=t;
}
} else
{
 printf("%s\n", a);
}
}
int main() {
char a[]="ABCDE";
permutation(a, 0,5);
return 0;
}

视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058