例31全序列问题
主题说明
输出自然数1到n的所有不重叠的排列，即n的全排列，需要在任何产生的数字序列中不允许重复的数字。
输入格式
n(1n9 )
输出格式
由1~n构成的所有不重复的数字串，每行一个列。 序列中的每个数字占五个宽度。
输入样品
3
输出样本
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
)1)编程思路。
用递归方法生成全数组。
)2)源程序。
#包含
int a[9]，flag[10]={0}；
voidDFS(intpos，int n ) )。
{
if(pos==n ) /现有的n个
{
for(intI=0； I
printf ()、a(I )；
打印((n )；
}
else
{
for(intI=1； i=n； I )
{
if(flag[I] ) ) ) )。
连续；
a[pos]=i；
flag[i]=1；
DFS(pos1，n )；
flag[i]=0；
}
}
}
int main () )
{
int n；
scanf('%d '，n )；
DFS(0，n )；
返回0；
}
习题31
31-1选书
正题选自洛谷试题库(https://www.Luo gu.org/problem/p 1657 )
主题说明
学校放寒假的时候，信息学奥林匹克指导老师有一、二、三……x本书。 必须分给参加研修的x人。 虽然每人只能选择一本书，但是每人有两本喜欢的书。 老师事先让每个人把自己喜欢的书填成一张表。 然后根据他们填写的表格发放书，老师寻求所有可能的发放方案，想设计一个程序让所有的学生都满意。
输入格式
第一行：一个数x
第2行~第1x行：每行2个个数，表示ai喜欢的书的号码
输出格式
只有一个数：总方案数total。
输入样品
5
1 3
4 5
2 5
1 4
3 5
输出样本
2
)1)编程思路。
写递归函数voidDFS(intI，int n )意味着第I个人会从n本书中选择一本书。 未选择第j本书(1jn ) (标记数组元素f[j]=1)，且第I个人喜欢这本书)的数组元素a[i][j]的值也为1 )的情况下
第I个人选择第j本书，然后第i 1个人进行选择，递归地调用DFS(I1，n )。 如果n个人都选择好的话，我会计数。
)2)源程序。
#包含
int a[21][21]、f[21]、cnt； //a[i][j]第一个人喜欢第j本书
voidDFS(intI，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(I1，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 )；
返回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个元素进行全排列。之后，按差三角形的特征依次确定上面其它行的值。在确定值的过程中，ggdhj个值已被使用，则不可能是问题的解。直接剪枝，进行下次搜索。
(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])
return;
if(x>=1 && x<= n*(n+1)/2)
{
visited[x] = 1;
num[i][j] = x;
}
}
if (num[n-1][0]>num[n-1][n-1]) return ;
for (i = 0; i < n; i++)
{
for(j = 0; j<=i; j++)
printf("%4d",num[i][j]);
printf("n");
}
printf("n");
}
void dfs(int take[], int index,int vis[],int n)
{
int i, j;
if (index==n)
{
judge(take,n);
return;
}
for(i = 1; i <= n*(n+1)/2; i++)
{
if(!vis[i])
{
vis[i] = 1;
take[index]= i;
dfs(take, index+1,vis,n);
vis[i] = 0;
}
}
}
int main()
{
int n,take[6],i;
int vis[22];
scanf("%d",&n);
for(i = 1; i <= n*(n+1)/2; i++)
vis[i]=0;
dfs(take,0,vis,n);
return 0;
}
31-3 数字和
问题描述
写出一个1至n的排列a1,a2,…,an，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：
3 ,1,2,4
4,3,6
7,9
16
最后得到16这样一个数字。
如果知道n和最后得到的数字的大小sum，请你求出最初序列a1,a2,…,an，这个序列为1至n的一个排列。若答案有多种可能，则输出字典序最小的那一个。
注意：本题字典序指的是1,2,3,4,5,6,7,8,9,10,11,12，而不是1,10,11,12,2,3,4,5,6,7,8,9。
输入格式
两个正整数n,sum。n≤12,sum≤12345。
输出格式
输出包括1行，为字典序最小的那个答案。
当无解的时候，请什么也不输出。
输入样例
4 16
输出样例
3 1 2 4
(1)编程思路。
以题目示例来说明。4个数a1、a2、a3、a4
第1次得到： a1+a2、a2+a3、a3+a4
第2次得到：a1+a2+a2+a3、a2+a3+a3+a4
第3次得到：(a1+a2+a2+a3)+(a2+a3+a3+a4)
即最后总和为：a1+3*a2+3*a3+a4
系数1、3、3、1正好四杨辉三角形的第4行的值。因此，需要先求出杨辉三角形第n行的值，以便于最后总和的计算。
生成1~n的全排列，对生成的排列进行判断，看是否满足和值等于输入的sum，如果找到的答案，置标记found为1，之后各排列直接返回。
(2)源程序。
#include
int a[12],flag[13]={0},y[13]={0};
int n,sum,found=0;
void dfs(int pos,int cursum)
{
if (cursum>sum|| found==1) return;
if (pos==n)
{
if (cursum==sum)
{
for (int i=0;i
printf("%d ",a[i]);
printf("n");
found=1;
}
}
else
{
for(int i=1;i<=n;i++)
{
if(flag[i])
continue;
a[pos]=i;
flag[i]=1;
dfs(pos+1,cursum+a[pos]*y[pos]);
flag[i]=0;
}
}
}
int main()
{
scanf("%d%d",&n,&sum);
y[0]=1;
for (int row=1;row
for (int col=row;col>=1;col--)
y[col]=y[col]+y[col -1];
dfs(0,0);
return 0;
}