首页 技术 正文
技术 2022年11月24日
0 收藏 316 点赞 4,318 浏览 3504 个字

例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 <stdio.h>

int a[9],flag[10]={0};

void dfs(int pos,int n)

{

if (pos==n)  // 已有n个数

{

for (int i=0;i<n;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  选书

本题选自洛谷题库 (https://www.luogu.org/problem/P1657)

题目描述

学校放寒假时,信息学奥赛辅导老师有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 <stdio.h>

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 <stdio.h>

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 <stdio.h>

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<n;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<n;row++)

for (int col=row;col>=1;col–)

y[col]=y[col]+y[col -1];

dfs(0,0);

return 0;

}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141915.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,508
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,314
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站