C语言-回溯例3

时间：2014-05-26 12:18:46 阅读：390 评论：0 收藏：0 [点我收藏+]

排列问题

1、实现排列A(n,m)
对指定的正整数m,n(约定1<m<=n),具体实现排列A(n,m)。
2、回溯算法设计
设置一维数组a，a(i)（i=1,2,…,m）在1—n中取值。首先从a(1)=1开始,逐步给a(i)(1≤i≤m)赋值,每一个a(i)赋值从1开始递增至n。
为判断数字是否重复,设置中间变量g：先赋值g=1；若出现某两数字相同(即a(i)=a(j)),则赋值g=0(重复标记)。
若i=m与g=1同时满足,则为一组解,用s统计解的个数后,格式打印输出这组解。
若i<m 且g=1,表明不到m个数字,下一个a(i)从1开始赋值，继续。
若a(i)=n ,则返回前一个数组元素a(i-1)增1赋值。直到a(1)=9时,已无法返回,意味着已全部试毕,求解结束。

3、算法描述
输入正整数n,m,(n≥m);
i=1;a[i]=1;
while (1)
{ g=1;for(j=1;j<i;j++)
if(a[j]==a[i] ) g=0;    /* 检测,不满足返回 */
if(g && i==m)
     printf(a[1-m]);       /* 输出一个解 */
if(i<n && g) {i++;a[i]=1;continue;}
while(a[i]==n && i>1) i--;   /* 回溯 */
if(a[i]==n && i==1) break; /* 退出循环，结束 */
else a[i]=a[i]+1;
}

4、代码实现

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 int main()
 5 {
 6     int a[100];
 7     int num;
 8     int flag;
 9     int i,j,k;
10     int m,n;
11     printf("输入n(A(n,m)):");
12     scanf("%d",&n);
13     printf("输入m(A(n,m)):");
14     scanf("%d",&m);
15     i=1;
16     a[i]=1;
17     num=0;
18     while(1)
19     {
20         flag=1;
21         for(k=i-1;k>=1;k--)
22         {
23             if(a[i]==a[k])
24             {
25                 flag=0;
26             }
27         }
28         if(flag&&i==m)
29         {
30             num++;
31             for(j=1;j<=m;j++)
32             {
33                 printf("%d",a[j]);
34             }
35             printf(" ");
36             if(num%6==0)
37             {
38                 printf("\n");
39             }
40         }
41         if(flag&&i<n)
42         {
43             i++;
44             a[i]=1;
45             continue;
46         }
47         while(a[i]==n&&i>1)i--;
48         if(a[i]==n&&i==1)
49         {
50             break;
51         }
52         else
53         {
54             a[i]++;
55         }
56     }
57     printf("\n排列数A(%d,%d)=%d",n,m,num);
58     return 0;
59 }