c语⾔列出数字1到3的全排列,C语⾔程序设计100例之
（31）：全排列问题
例31  全排列问题
题⽬描述
输出⾃然数1到n所有不重复的排列，即n的全排列，要求所产⽣的任⼀数字序列中不允许出现重复的数字。
输⼊格式
n(1≤n≤9)
输出格式
由1～n组成的所有不重复的数字序列，每⾏⼀个序列。序列中每个数字占5个宽度。
输⼊样例
3
输出样例
1    2    3
1    3    2
2    1    3
2    3    1
3    1    2
3    2    1
(1)编程思路。
采⽤递归的⽅法来⽣成全排列。
(2)源程序。
#include
int a[9],flag[10]={0};
void dfs(int pos,int n)
{
if (pos==n)  // 已有n个数
{
for (int i=0;i
printf("%5d",a[i]);
printf("\n");
编程递归函数}
else
{
for(int i=1;i<=n;i++)
{
if(flag[i])
continue;
a[pos]=i;
flag[i]=1;
dfs(pos+1,n);
flag[i]=0;
}
}
}
int main()
{
int n;
scanf("%d",&n);
dfs(0,n);
return 0;
}
习题31
31-1  选书
题⽬描述
学校放寒假时，信息学奥赛辅导⽼师有1,2,3……x本书，要分给参加培训的x个⼈，每⼈只能选⼀本书，
但是每⼈有两本喜欢的书。⽼师事先让每个⼈将⾃⼰喜欢的书填写在⼀张表上。然后根据他们填写的表来分配书本，希望设计⼀个程序帮助⽼师求出所有可能的分配⽅案，使每个学⽣都满意。
输⼊格式
第1⾏：⼀个数x
第2⾏~第1+x⾏：每⾏两个数，表⽰ai喜欢的书的序号
输出格式
只有⼀个数：总⽅案数total。
输⼊样例
5
1 3
4 5
2 5
1 4
3 5
输出样例
2
(1)编程思路。
编写递归函数void dfs(int i,int n)表⽰第i个⼈在n本书中选择⼀本书。若第j本书(1≤j≤n)没选(标记数组元素f[j]=1)且第i个⼈喜欢这本书(数组元素a[i][j]的值也为1)，则
第i个⼈选择第j本书；之后第i+1个⼈进⾏选择，递归调⽤dfs(i+1,n)。若n个⼈均选择好，则计数。
(2)源程序。
#include
int a[21][21],f[21],cnt;  // a[i][j]第i个⼈喜欢第j本书
void dfs(int i,int n)
{
int j;
for(j=1;j<=n;j++)
{
if(f[j] && a[i][j]) // 这本书没选且第i个⼈喜欢这本书
{
f[j]=0;
if(i==n)
{
cnt++;
}
else
{
dfs(i+1,n);
}
f[j]=1;
}
}
}
int main()
{
int n,i,x,y;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
a[i][x]=1;
a[i][y]=1;
f[i]=1;
}
dfs(1,n);
printf("%d\n",cnt);
return 0;
}
31-2  差三⾓形
问题描述
观察下⾯的数字组成的三⾓形：
3
1 4
5 6 2
看出什么特征吗？
1)它包含了1~6的连续整数。
2)每个数字都是其下⽅相邻的两个数字的差(当然是⼤数减去⼩数)
满⾜这样特征的三⾓形，称为差三⾓形。
编写程序，出由1~n*(n+1)/2共n*(n+1)/2个整数组成的⼀个差三⾓形。
输⼊格式
⼀个正整数n。n≤6
输出格式
输出所有满⾜要求的差三⾓形。输出时，每个数字占4列。每种解之间空⼀⾏。当⽆解的时候，请什么也不输出。
输⼊样例
4
输出样例
4
3
4  7
5  9  2
6  1  10  8
3
5  2
4  9  7
6  10  1  8
4
2  6
5  7  1
8  3  10  9
4
5  1
2  7  6
8  10  3  9
(1)编程思路。
先确定最后⼀⾏的值，即在1~ n*(n+1)/2这n*(n+1)/2个数中任意选取n个元素进⾏全排列。之后，按差三⾓形的特征依次确定上⾯其它⾏的值。在确定值的过程中，若某个值已被使⽤，则不可能是问题的解。直接剪枝，进⾏下次搜索。
(2)源程序。
#include
void judge(int take[],int n)
{
int visited[22];  // 最多6⾏，21个数
int num[6][6],i,j,x;
for (i=1;i<=n*(n+1)/2;i++)
visited[i]=0;
for(i = 0; i < n; i++)
{
num[n-1][i]=take[i];
visited[take[i]] = 1;
}
for (i=n-2; i>=0; i--)
for (j = 0; j <= i; j++)
{
x = abs(num[i+1][j] - num[i+1][j+1]);
if(visited[x])

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。