求free Pascal 程序设计的一道题,关于全排列
发布网友
发布时间:2022-04-25 09:29
我来回答
共1个回答
热心网友
时间:2022-04-25 10:58
全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1~n的n个数字的排列一一对应,因此在此就以n个数字的排列为例说明排列的生 ...
全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1~n的n个数字的排列一一对应,因此在此就以n个数字的排列为例说明排列的生成法。
n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外,都有一个后继;除第一个排列外,都有一个前驱。每个排列的后继都可以从 它 的前驱经过最少的变化而得到,全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。
全排列的生成法通常有以下几种:
字典序法
递增进位数制法
递减进位数制法
邻位交换法
递归类算法
1.字典序法
字典序法中,对于数字1、2、3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列12354和12345,排列12345在前,排列12354在后。按照这样的规定,5个数字的所有的排列中最前面的是12345,最后面的是54321。
字典序算法如下:
设P是1~n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1)从排列的右端开始,找出第一个比右边数字小的数字的序号j(j从左端开始计算),即 j=max{i|pi<pi+1}
2)在pj的右边的数字中,找出所有比pj大的数中最小的数字pk,即 k=max{i|pi>pj}(右边的数从右至左是递增的,因此k是所有大于pj的数字中序号最大者)
3)对换pi,pk
4)再将pj+1......pk-1pkpk+1pn倒转得到排列p’’=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1,这就是排列p的下一个下一个排列。
例如839647521是数字1~9的一个排列。从它生成下一个排列的步骤如下:
自右至左找出排列中第一个比右边数字小的数字4 839647521
在该数字后的数字中找出比4大的数中最小的一个5 839647521
将5与4交换 839657421
将7421倒转 839651247
所以839647521的下一个排列是839651247。
2.递增进位数制法
在递增进位制数法中,从一个排列求另一个排列需要用到中介数。如果用 ki表示排列p1p2...pi...pn中元素pi的右边比pi小的数的个数,则排列的中介数就是对应的排列k1 ...... ki...... kn-1。
例如排列839647521的中介数是72642321,7、2、6、......分别是排列中数字8、3、9、......的右边比它小的数字个数。
中介数是计算排列的中间环节。已知一个排列,要求下一个排列,首先确定其中介数,一个排列的后继,其中介数是原排列中介数加1,需要注意的是,如果中介数的末位kn-1+1=2,则要向前进位,一般情形,如果ki+1=n-i+1,则要进位,这就是所谓的递增进位制。例如排列839647521的中介数是72642321,则下一个排列的中介数是67342221+1=67342300(因为1+1=2,所以向前进位,2+1=3,又发生进位,所以下一个中介数是67342300)。
得到中介数后,可根据它还原对应得排列。
算法如下:
中介数k1、k2、......、kn-1的各位数字顺序表示排列中的数字n、n-1、......、2在排列中距右端的的空位数,因此,要按k1、k2、......、kn-1的值从右向左确定n、n-1、......、2的位置,并逐个放置在排列中:i放在右起的ki+1位,如果某位已放有数字,则该位置不算在内,最后一个空位放1。
因此从67342300可得到排列849617523,它就是839647521的后一个排列。因为9最先放置,k1=6,9放在右起第7位,空出6个空位,然后是放8,k2=7,8放在右起第8位,但9占用一位,故8应放在右起第9位,余类推。
3.递减进位制数法
在递增进位制数法中,中介数的最低位是逢2进1,进位频繁,这是一个缺点。把递增进位制数翻转,就得到递减进位制数。
839647521的中介数是67342221(k1k2...kn-1),倒转成为12224376(kn-1...k2k1),这是递减进位制数的中介数:ki(i=n-1,n-2,...,2)位逢i向ki-1位进1。给定排列p,p的下一个排列的中介数定义为p的中介数加1。例如p=839647521,p的中介数为12224376,p的下一个排列的中介数为12224376+1=12224377,由此得到p的下一个排列为893647521。
给定中介数,可用与递增进位制数法类似的方法还原出排列。但在递减进位制数中,可以不先计算中介数就直接从一个排列求出下一个排列。具体算法如下:
1)如果p(i)=n且i<>n,则p(i)与p(i-1)交换
2)如果p(n)=n,则找出一个连续递减序列9、8、......、i,将其从排列左端删除,再以相反顺序加在排列右端,然后将i-1与左边的数字交换
例如p=893647521的下一个排列是983647521。求983647521的下一个排列时,因为9在最左边且第2位为8,第3位不是7,所以将8和9从小到大排于最右端364752189,再将7与其左方数字对调得到983647521的下一个排列是367452189。又例如求987635421的下一个排列,只需要将9876从小到大排到最右端并将5与其左方数字3对调,得到534216789。
4.邻位对换法
邻位对换法中下一个排列总是上一个排列某相邻两位对换得到的。以4个元素的排列为例,将最后的元素4逐次与前面的元素交换,可以生成4个新排列:
1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3
然后将最后一个排列的末尾的两个元素交换,再逐次将排头的4与其后的元素交换,又生成四个新排列:
4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4
再将最后一个排列的末尾的两个元素交换,将4从后往前移:
3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2
如此循环既可求出全部排列。
5.元素增值法(n进制法)
1)从原始排列p=p1p2......pn开始,第n位加n-1,如果该位的值超过n,则将它除以n,用余数取代该位,并进位(将第n-1位加1)
2)再按同样方法处理n-1位,n-2位,......,直至不再发生进位为止,处理完一个排列就产生了一个新的排列
3)将其中有相同元素的排列去掉
4)当第一个元素的值>n则结束
以3个数1、2、3的排列为例:原始排列是1 2 3,从它开始,第3个元素是3,3+2=5,5 Mod 3=2,第2个元素是2,2+1=3,所以新排列是1 3 2。通过元素增值,顺序产生的排列是:1 2 3,1 3 2,2 1 1,2 1 3,2 2 2,2 3 1,2 3 3,3 1 2,3 2 1
有下划线的排列中存在重复元素,丢弃,余下的就是全部排列。
6.递归类算法
全排列的生成方法用递归方式描述比较简洁,实现的方法也有多种。
1)回溯法
回溯法通常是构造一颗生成树。以3个元素为例;树的节点有个数据,可取值是1、2、3。如果某个为0,则表示尚未取值。
初始状态是(0,0,0),第1个元素值可以分别挑选1,2,3,因此扩展出3个子结点。用相同方法找出这些结点的第2个元素的可能值,如此反复进行,一旦出现新结点的3个数据全非零,那就找到了一种全排列方案。当尝试了所有可能方案,即获得了问题的解答。
2)递归算法
如果用P表示n个元素的排列,而Pi表示不包含元素i的排列,(i)Pi表示在排列Pi前加上前缀i的排列,那么,n个元素的排列可递归定义为:
如果n=1,则排列P只有一个元素i
如果n>1,则排列P由排列(i)Pi构成(i=1、2、....、n-1)。
根据定义,容易看出如果已经生成了k-1个元素的排列,那么,k个元素的排列可以在每个k-1个元素的排列Pi前添加元素i而生成。例如2个元素的排列是1 2和2 1,对与个元素而言,p1是2 3和3 2,在每个排列前加上1即生成1 2 3和1 3 2两个新排列,p2和p3则是1 3、3 1和1 2、2 1,按同样方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。
3)循环移位法
如果已经生成了k-1个元素的排列,则在每个排列后添加元素k使之成为k个元素的排列,然后将每个排列循环左移(右移),每移动一次就产生一个新的排列。
例如2个元素的排列是1 2和2 1。在1 2 后加上3成为新排列1 2 3,将它循环左移可再生成新排列2 3 1、3 1 2,同样2 1 可生成新排列2 1 3、1 3 2和3 2 1。
求free Pascal 程序设计的一道题,关于全排列
全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1~n的n个数字的排列一一对应,因此在此就以n个数字的排列为例说明排列的生 ... 全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n...
用FREE PASCAL编程 2011年长沙市小学生信息学奥林匹克竞赛决赛试题
1.(全排列)下面程序的功能是利用递归方法生成从1到n(n<10)的n个数的全部可能的排列(不一定按升序输出)。例如,输入3,则应该输出(每行输出5个排列): 123 132 213 231 321 312 程序: Program ex401; Var i,n,k:integer; a:array[1..10] of integer; count:longint; Procedure perm(k:integer); var...
2008信息学奥赛初赛答案(山东)?
17.面向对象的程序设计(Object-Oriented Programming)是一种程序设计的方法论,它将对象作为程序设计的基本单元,将数据和程序封装在对象中,以提高软件的重用性、灵活性、和扩展性。下面关于面向对象的程序设计说法中正确的是( )。 A.面向对象的程序设计方法通常采用自顶向下的设计方法进行设计。 B.面向对象的程序设计...
第十二届全国青少年信息学奥林匹克联赛初赛试题讲解
他先取1那一堆,则变为(2,3),由上面的分析,对手必胜。 他从2那一堆中取1个,就变成了(1,1,3),对手可以将3那一堆全部取走,变成了(1,1),于是必胜。 他将2那一堆全部取走,就变成了(1,3),对手必胜。 他从3那一堆中取1个,就变成了(1,2,2),对手必胜。 他从3那一堆中取2个,就变成了(1,2,1...
有谁有noip2008普及组初赛官方答案?
3. 132/213/231/312/321/ (全排列) 4. defghijxyzabc/hfizxjaybcccc (字符串……还有很WC的ASCII) 五、完形填空 (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不一定上报科学委员会审查) 1. ① a[left] ② a[j] < value (或a[j] <= value) (不过好像“<=”有...
14届全国青少年信息学奥赛初赛
C.T是无环的,有n-1条边 D.以上都不对 19.NOIP竞赛推荐使用的语言环境有( )。A.Dev-C++ B.Visual C++ C.Free Pascal D.Lazarus 20.在下列防火墙(Firewall)的说法中,正确的有( )。A.防火墙是一项协助确保信息安全的设备,其会依照特定的规则,允许或是限制数...
急求怎样把硬盘分为整数区???
硬盘整数分区计算方法一般算法:分区大小=(分区大小-1)×4+1024×分区大小 已经有专业的计算工具可以直接使用,请下载附件.下面是理论部分,你也可以跟着做,有相应的公式.如果按照硬盘分区整数G计算公式:(X-1)*4+1024*X=Y 其中X就是你想要得到的整数分区的数值,单位是G,Y是你分区时应该输入的数字,...
第十二届全国青少年信息学奥林匹克联赛普及组P语言试题及答案!_百度...
Turbo Pascal C. RHIDE D. free pascal 3. 以下断电之后仍能保存数据的有( )。 A. 寄存器 B. ROM C. RAM D. 高速缓存 4.Linux是一种( )。 A. 绘图软件 B. 程序设计语言 C. 操作系统 D. 网络浏览器 5. CPU是( )的简称。 A. 硬盘 B. 中央处理器 C. 高级程序语言 D. 核心寄存器 6. 在...
2006年全国信息学奥赛初赛普及组(pascal)试题
Turbo Pascal C. RHIDE D. free pascal 3. 以下断电之后仍能保存数据的有( )。 A. 寄存器 B. ROM C. RAM D. 高速缓存 4.Linux是一种( )。 A. 绘图软件 B. 程序设计语言 C. 操作系统 D. 网络浏览器 5. CPU是( )的简称。 A. 硬盘 B. 中央处理器 C. 高级程序语言 D. 核心寄存器 6. 在...
第十四届全国青少年信息学联赛(提高组)初赛试题及答案
( 提高组 Pascal语言 二小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一、单项选择题(共10题,每题1.5分,共计15分。每题有且仅有一个正确答案)。 1.在以下各项中,( )不是操作系统软件。 A.Solaris B.Linux C.Sybase D.Windows Vista E.Symbian 2.微型计算机中,控制器...