Ⅰ pascal 由键盘上输入任意n个一位数数输出它的全排列
一、 引入：
fpc-2.0.0.i386-win32
程序一：已知长方形的长、宽，求长方形的周长
program circle; 该程序的首部，program是保留字
var chang,kuan,zhouchang:real; 定义变量：设定长，宽，周长为实数类型
begin 开始语句
readln(chang); 读语句，读入长(chang)和宽(kuan)
readln(kuan);
zhouchang:=2*(chang+kuan); 赋值语句，将计算结果赋给zhouchang
write(zhouchang); 写语句，将结果（zhouchang）
end. 结束语句，与begin成对出现
程序二：已知长方形的长、宽，求长方形的周长，并求出长方形的面积。
rogram circle;
var chang,kuan,zhouchang,mianji:real;
begin
readln(chang);
readln(kuan);
zhouchang:=2*(chang+kuan);
mianji:=chang*kuan;
write(zhouchang,mianji);
end.
小结：一个完整的pascal程序结构
Program 程序名（程序参数表）；
var
变量说明；
Begin
语句；
语句；
……
End.
编译：Alt+F9
运行 Ctrl+F9
返回看结果Alt+F5
思考练习:
1、已知长方体的长、宽、高，求长方体的表面积及体积。
2、已知正方体的边长，求正方体的表面积及体积。
3、已知圆半径，求圆的周长及面积。
作业
已知圆半径，求圆的周长及面积。3.14若改成3.14159
第一句为程序首部，每个pascal程序都必须以它开头。
增加程序的可读性，用pi表示
一、常量说明
Const pi=3.14159
变量说明
VAR 单个变量或用逗号分开的多个变量
<变量表>：<类型>
二、标准数据类型
（一）、实型（real）
1、两种表示方法：小数表示法和指数表示法
小数表示法：1.25，0.0025，258.2，253.0
科学表示法：1.25e0，1.3654e+2，2.5e-3，
0e0，1e2
2、说明方式
const k=1.26
var m,n:real;
3、运算：+（加），—（减），*（乘），/（除）
标准函数：
abs(绝对值)，sqr（平方），sqrt（开方），
trunc(取整），round（舍入取整）
（二）、整型（integer）
1、表示方法：25，-456，0
2、说明方法：
const long=150；
wide=65；
var I,j,k：integer；
3、整型量的运算：
+（加），—（减），*（乘），div（整除）
/（除）得到的值为实型，mod（取余） 4、用于整数的标准函数
abs（绝对值），sqr（平方），pred（前导）
succ（后续），
三、
读语句一：read
用于在程序执行时，从外部输入数据给变量
一般形式：read(变量表) 其中变量表是一些由逗号分开的变量
程序一、读入2个整数和1个实数，并将这三个数输出。
Program shu;
Var
x,y:integer;
z:real;
begin
read(x);
read(y);
read(z);
write(x);
write(y);
write(z);
end. Program shu;
Var
x,y:integer;
z:real;
begin
read(x,y,z);
write(x,y,z);
end.
可以将读入与写出语句合并成一句。
注意：从键盘上输入的数据必须与程序中设定的输入变量的类型相同。例如上题，x,y是整型，我们从键盘上输入就必须是整型数，例如：14、-6，而不能是实型数，例如：1.9、98.0；而z是实型数，输入可以是小数也可以是整数，例如：2.36666 ，或者是10。
读语句二：readln
在完成该语句的最后一个变量值的输入以后，将结束包括这个数据值的输入行，使下一个read语句（或readln语句）从下一个新行开始输入数据。
例：
Program shu2;
Var a,b:real;
begin
Read(a,b);
Read(c,d,e,f);
Read(g,h);
Writeln(a,b,c,d,e,f,g,h);
End. Program shu2;
Var a,b:real;
begin
Readln(a,b);
Readln(c,d,e,f);
Readln(g,h);
Writeln(a,b,c,d,e,f,g,h);
End.
从键盘上输入以下数据：
1.5 3.7 2.4
5.7 2.1 8.9
9.2 1.7 5.3
2.8 3.4 2.9
得到的结果：
a=1.5 b=3.7
c=2.4 d=5.7 e=2.1 f=8.9
g=9.2 h=1.7 得到的结果：
a=1.5 b=3.7
c=5.7 d=2.1 e=8.9 f=9.2
g=2.8 h=3.4
四、表达式与赋值语句
一般形式：<变量>:=<表达式>
表达式可以是简单的常数、常量、变量、函数或它们之间的算术运算、逻辑运算、关系运算等
例如：2+3x
1.25×10-5
写表达式时，要注意以下几点：
1、所有表达式必须以线形写出。
2、只能使用合法的标志符
3、乘号必须用符号“*”明确地指出，不得省略
4、函数的自变量可以是任意表达式。
注意：赋值语句中，表达式的类型必须与左端变量的类型赋值相容。
（1）、表达式的类型与左端变量的类型相同
（2）、表达式为整型，左端变量为实型
var I,j,k:integer
k:=I/j
X:=x+1 I:=I+1
写语句一：Write语句
将计算结果通过屏幕或打字机输出显示。
例如：write(aa,bb);
一般形式：write(<输出表>：场宽：小数位数)
输出表是一些由逗号分开的输出项。
输出项可以是变量或表达式，或用引号括起来的字符串。
若为变量，则输出变量的值。
若为表达式，则先计算表达式的值，然后将值输出。
若为字符串，则输出字符串本身。
若为用符号’ x+y= ’ ，则将单引号内的值原样输出
例如：输入：x=5,y=6
write(x,y,x+y,x*y)
输出结果：5，6，11,30
write(‘x=‘,x,’y=‘,y,’x+y=‘,x+y,’x*y=‘,x*y);
输出结果：x=5y=6x+y=11x*y=30
写语句二：Writeln语句
结果将输出在不同的行上。
在印出输出表的最后一个输出项后，结束当前输出行，使得下一个write（或writeln）语句从下一个新行的开头输出。即：印出输出项后，回车换行，光标移到下一行的首位。
例如：
Writeln 可以单独使用，用于结束当前输出行，指向下一行的开始
writeln(‘x=‘,x,’y=‘,y);
Writeln(’x+y=‘,x+y,’x*y=‘,x*y);
例：
1、写一程序读入三角形的三个边a，b，c，计算并输出三角形的面积S。可利用下列公式计算：S= ，其中p= 。
2、输入一个三位整数，将它反向输出。例如输入127，输出应为721。
常量说明，不一定要有
三、字符型
1、表示方法： ‘A’,’B’,’C,’,…… ‘a’,’b’,’c’,…… ‘0’，’1’，’2’，’3’，…… ‘+’,’-’,’*’,…… ‘’代表空格字符
2、说明方法
const black=‘’ star=‘*’ var ch1,ch2:char;
3、用于字符的标准函数
ord（取序号），pred（前导），succ（后继）
chr（65）=‘A’ chr(97)=‘a’ ord(‘A’)=65 ord(‘a’)=97
四、布尔型(boolean)
1、说明
const f=false;
t=true;
var b1,b2,flag:boolean;
2、标准函数
odd(取序号)、pred（前导）、succ（后继）、
odd(false)=0 odd(true)=
pred(true)= succ(false)=
3、用于布尔量运算有布尔逻辑运算（即逻辑运算）
AND(与)OR(或) NOT(非)
B1 B2 NOT B1 B1 AND B2 B1 OR B2
FALSE FALSE
FALSE TRUE
TRUE FALSE
TRUE TRUE
4、关系运算
<（小于），<=（小于等于），=（等于）
>（大于），>=（大于等于），<>（不等于）
关系运算可以用于整型、实型、字符型、布尔类型。
结果均为布尔型
例：3<6=
3<7.8=
false<true=
‘a’>=‘b’=
判断(x,y)是否在第一象限
6、表达式按下列运算优先规则计算
（1）、所有括起来的子表达式必须首先计算，且子表达式必须从里到外计算。
（2）、在同一表达式中的运算符按下列次序计算：
①函数
②not
③AND,*,/,DIV,MOD
④OR,+,-
⑤<，<=，=，>，>=，<>
（3）、同一个表达式中，同一优先级按从左到右注意：赋值语句中，表达式的类型必须与左端变量的类型赋值相容。
a、表达式的类型与左端变量的类型相同
b、表达式为整型，左端变量为实型
var I,j,k:integer
k:=I/j
X:=x+1 I:=I+1
Write语句
将计算结果通过屏幕或打字机输出显示。
例如：write(aa,bb);
一般形式：write(<输出表>：场宽：小数位数)
输出表是一些由逗号分开的输出项。
输出项可以是变量或表达式，或用引号括起来的字符串。
若为变量，则输出变量的值。
若为表达式，则先计算表达式的值，然后将值输出。
若为字符串，则输出字符串本身。
若为用符号’ x+y= ’ ，则将单引号内的值原样输出
例如：输入：x=5,y=6
write(x,y,x+y,x*y)
输出结果：5，6，11,30
write(‘x=‘,x,’y=‘,y,’x+y=‘,x+y,’x*y=‘,x*y);
输出结果：x=5y=6x+y=11x*y=30
1、 输入三个字符，然后按输入字符次序输出这三个字符，再输出每个字符的序号，最后按与输入字符相反的次序输出这三个字符。
2、 输入两组x，y值，由程序根据它们是否在斜线区域内，输出不同的值。若在斜线区域内，输出true，否则输出false。
三、选择结构程序设计
程序一：期末成绩,如果成绩在60分以上的为合格,60分以下的为不及格,如何表示?
program pd;
var
x:real;
begin
read(x); 读入成绩
if x>=60 then write(‘pass’)
else write(‘not pass’); 用if语句进行判断，如果>=60打印“pass ” 否则打印“not pass”
End.
选择结构语句一：If语句格式
IF语句格式1：IF〈条件〉THEN 〈语句1〉
ELSE 〈语句2〉
IF语句格式2：IF〈条件〉THEN 〈语句1〉
程序二：火车托运行李，要根据重量按不同的标准收费。例如不超过50kg，按每公斤0.35元收费。若超过50k按每公斤0.35元收费，其余超过部分按每公斤0.50远收费。现输入托运行李重量，要求计算并输出托运费。
Program compay;
var
weight,pay:real;
begin
readln(weight); 读入行李重量
if weight<=50 then pay:=weight*0.35 判断语句
else pay:=50*0.35+(weight-50)*0.5;
Writeln(‘pay=‘,pay); 打印付费结果
end.
注意：If语句中，如果<语句一>或者<语句二>，执行的内容无法用一个语句实现，可以使用复合语句，用begin 和end将执行的语句合并成一个复合语句。
复合语句格式：BEGIN
〈语句1〉；
〈语句2〉；
……；
END；
程序三：输入一个数字，如果该数字大于100，则先输出这个数，并将该数减去100，并将减去100后的结果输出，否则输出“no”。
Program number;
Var x,y:real;
Begin
read(x); 读入该数x
If x>100 then 对x进行判断
Begin 用begin和end将三个语句合并成一个复合语句
writeln(x);
x:=x-100;
writeln(x);
end
else writeln(“no”);
End.
复合判断条件语句：当<条件>中包含的不仅只有一个语句，而是多个条件时，可以使用and\or\not复合判断条件
AND：与、和 ，条件都成立时为真
OR：或者，只要有一个条件成立时为真
NOT：非，
程序四：输入一个成绩，如果该成绩小于90并且大于等于70，则输出“ok”
程序：Program score;
var k:real;
begin
read(k);
if (k>=70) and (k<90) then write(‘ok’);
end.
复合IF语句
程序五、输入某学生成绩，若成绩在85分以上，输出“A”，若成绩在60分到85分之间，包含60和85，输出“B”，若成绩低于60分，输出“C”。
该题有三重判断，如何实现？
应用复合IF语句：
read(成绩)
IF 成绩>85 then write（’A’） 第一重IF
Else if 成绩>=59 then write (‘B’) 第二重IF
Else write(‘C’);
复合IF语句格式：
IF〈条件1〉 THEN 〈语句1〉
ELSE IF〈条件2〉 THEN〈语句2〉
ELSE〈语句3〉
If语句练习题：
1、 从键盘上输入一个正整数，判断奇数、偶数。如果为奇数则输出“YES”，如果为偶数则输出“NO”。
2、 读入两个数，找出其中最大的数，并输出。
3、 输入一个数，判断该数是正数、负数还是零，为正数输出“zheng”，为负数输出“fu”，为零输出“0”。
Program circle;
Var num:integer;
Begin
Read(num);
If num>0 then writeln(‘zheng’)
Else if num<0 then writeln(‘fu’)
Else writeln(‘0’);
End.
4、 对一批货物征收税收。价格在1万元以上的货物征税5%，在5000元以上，1万元以下的货物征税3%，5000元以下的货物征税2%，1000元以下的货物免税。编一程序，读入货物价格，计算并输出税金。
Program test;
Var price,tax:real;
Begin
Read(price);
If price>=10000 then tax:=price*0.05
Else if price>=5000 then tax:=price*0.03
Else if price>=1000
then tax:=price*0.02
Else tax:=0;
Writeln(‘tax=’,tax);
End.
5、 输入一个数，如果这个数能同时满足用3除余2，用5除余3，用7除余2的所有整数，则输出“yes”。
Program sum;
Var a:integer;
Begin
If (a mod 3=2) and (a mod 5=3) and (a mod 7=2) then write(‘yes’);
End.
6、输入3个字母，按字母表顺序从小到大输出这3个字母。
7、读两个数将大数存于X，小数存于Y。
8、输入一个年份，判断是否是闰年，如果是则输出“yes”，否则输出“no”
目前公认的闰年判断算法，满足下列二者之一，即为闰年：
① 能被4整除，但不能被100整除
② 能被4整除，且能被400整除
9、输入一个加减式，根据输入的式子，判断运算符号，求出结果。例如从键盘上输入：+，5 ， 3，则输出为8；例如输入：-，10 ， 6，则输出为5。
10、输入一个1000以内的任意一个数，如果这个数中至少有一位数字是5，则输出“yes”，否则输出“no”。
11、输入一个三位的数，判断该数是否为水仙花数，是则输出“flower”。（水仙花数：若三位数abc，a^3+b^3+c^3=abc ,则称该数为水仙花数）
12、输入一个1000以内的数，判断该数是否为守行数（若某数的平方，其低位与该数本身相同，则称该数为守行数。例如25，252=625，62=36，平方值的低位与原数相同，25、6为守行数）。
选择结构语句二：CASE语句：是实现选择结构程序设计的另一种语句。
程序一：输入班号，输出该班学生人数。
班号： 1 2 3 4 5 6
人数： 50 52 50 50 52 55
使用IF语句：
Program number;
Var x:integer;
Begin
Read(x);
If (x=1) or (x=3) or (x=4) then write(50)
Else if x=6 then write(55)
Else write(52);
End.
使用CASE语句：
Program number;
Var x:integer;
Begin
Read(x);
Case x of
1, 3, 4:write(50);
6 :write(55);
2, 5 :write(52);
end
end.
CASE语句的一般形式是：
CASE <表达式> OF 表达式：必须是有序类型（整型、字符型、布尔型）
<值表1>：<语句1>； 值表1：为具体的值列表，用逗号隔开
<值表2>：<语句2>；
……
<值表n>：<语句n>
END
练习：
1、输入年、月，输出该月有几天。（每年的1、3、5、7、8、10、12，每月有31天；4、6、9、11月，每月有30天；2月闰年有29天，平年有28天。年号能被4整除，但不能被100整除，或者年号能被400整除的年份均是闰年）
2、输入两个运算量及一个运算符（+，-，*，/），输出运算结果。
例如：输入 6 9 +
输出 15
3、若已知x在1到8之间，要按如下公式计算y。
y=
4、 输入实数x(已知0<=x<=10)，计算y并输出。
2x2+3x+5 x<3
y= (x-3)2 3<=x<6
x>=6
用两种方法编程：
（1） 用IF语句编程；
（2） 用CASE语句编程
<循环体>
循环过程:首先将初值赋给循环变量,然后将循环变量与终值比较,当循环变量的值小于等于终值时,执行循环体。每次执行循环体以后，将循环变量自动加1（即后继值）赋给循环变量，然后再与终值比较，如果与（终值+1）的值相等则退出循环结束For语句，否则再次执行循环体，重复该过程直到循环变量的值与（终值+1）相等。
注意：
1、循环变量必须是有序类型的，且必须与初值与终值的类型相同，例如：整数，字符，而不能是实型。
2、循环变量的初值、终值可以是表达式。
3、循环体可以是任何单个语句或由多个语句组成的复合语句（begin……end）。
4、在循环体内不要随意改变循环变量的值，否则可能会造成死程序循环。
3、 在循环体中，对初、终值表达式值的改变不会影响循环次数及循环变量的取值。
FOR <循环变量>:=<初值> to <终值> do
<循环体>
循环过程:首先将初值赋给循环变量,然后将循环变量与终值比较,当循环变量的值大于等于终值时,执行循环体。每次执行循环体以后，将循环变量自动减1（即前导值）赋给循环变量，然后再与终值比较，如果与（终值-1）的值相等则退出循环结束For语句，否则再次执行循环体，重复该过程直到循环变量的值与（终值-1）相等。
例题二：在1——500中，找出能同时满足用3整除余2，用5整除余3，用7整除余2的所有整除,打印出来。
程序二：
program sunzi;
var I:integer; 仅需一个变量i
begin
for I:=1 to 500 do 直接利用循环变量，对其进行判断
if (I mod 3=2) and (I mod 5=3) and (I mod 7=2) then write（I）;
end.
例题三：例题二改进：找出满足条件的数打印出，并统计其个数，最后将总个数打印出来。
程序三：program sunzi;
var I,num:integer;
begin
num:=0; 利用变量num统计符合条件的个数，初始化num=0
for I:=1 to 500 do
if (I mod 3=2) and (I mod 5=3) and (I mod 7=2) then
begin write（I）;
num:=num+1; 符合条件时，记数自动累加1
end;
writeln(num); 500次判断后将计算结果打印出来
end.
多重循环概念:
如果一个循环结构的内部(循环体)又包括一个循环结构,就称为多重循环结构。
注意：多重循环的嵌套次数可以是任意的。可以按照嵌套层次数，分别叫做二重循环、三重循环等。处于内部的循环叫做内循环，处于外部的循环叫做外循环。
练习：
1、打印如下图形：
* * * * *
* * * * *
* * * * *
* * * * * * * * * *
* * * * *
* * * * *
* * * * * * * * * *
* * * * *
* * * * *
* * * * * *
* *
* * *
* * * * *
* *
* * *
* * * *
(1) (2) (3) (4) (5)
* * * *
* * *
* *
* * * * *
* * *
* *
* *
* * *
* * * * *
* * * * * * * *
* *
* * *
* * * * * * * * * * *
* * * * *
* * *
*
(6) (7) (8) (9) (10)
2、打印出如下图形：
1
12
123
1234
12345 1
2 2 2
3 3 3 3 3
4 4 4 4 4 4 4 1
2 3 4
5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23 24 25
A
AB
ABC
ABCD
ABCDE A
A B
A B C
A B C D
……
A B C …… Z 1
1 2 1
1 2 3 2 1
1 2 3 4 3 2 1
1 2 3 4 5 4 3 2 1
3、打印杨辉三角形
一、WHILE循环
对于for循环有时也称为计数循环，当循环次数未知，只能根据某一条件来决定是否进行循环时，用while 语句或repeat语句实现循环要更方便。
while语句的形式为：
while <布尔表达式> do <语句>；
其意义为：当布尔表达式的值为true时，执行do后面的语句。
while语句的执行过程为：
①判断布尔表达式的值,如果其值为真,执行步骤2,否则执行步骤4;
②执行循环体语句(do后面的语句);
③返回步骤1;
④结束循环,执行while的下一个语句。
说明：这里while和do为保留字，while语句的特点是先判断，后执行。 当布尔表达式成立时，重复执行do后面的语句(循环体)。
例1 、求恰好使s=1+1/2+1/3+…+1/n的值大于10时n的值。
分析：“恰好使s的值大于10”意思是当表达式s的前n-1项的和小于或等于10，而加上了第n项后s的值大于10。从数学角度，我们很难计算这个n的值。故从第一项开始，当s的值小于或等于10时，就继续将下一项值累加起来。当s的值超过10时，最后一项的项数即为要求的n。
程序如下：
var
s : real;
n : integer;｛n表示项数｝
begin
s:=0.0;n:=0;
while s<=10 do｛当s的值还未超过10时｝
begin
n:=n+1;｛项数加1｝
s:=s+1/n;｛将下一项值累加到s｝
end;
writlen('n=',n);｛输出结果｝
end.
例2、求两个正整数m和n的最大公约数。
分析：求两个正整数的最大公约数采用的辗转相除法求解。以下是辗转的算法：
分别用m,n,r表示被除数、除数、余数。
①求m/n的余数r.
②若r=0,则n为最大公约数.若r≠0,执行第③步.
③将n的值放在m中,将r的值放在n中.
④返回重新执行第①步。
程序如下:
program ex4_4;
var m,n,a,b,r:integer;
begin
write('Input m,n:');
readln(m,n);
a:=m;b:=n;r:=a mod b;
while r<>0 do
begin
a:=b;b:=r;
r:=a mod b;
end;
writeln('The greatest common divide is:',b:8);
end.
二、直到循环（REPEAT－until语句）
用while语句可以实现“当型循环”，用repeat-until 语句可以实现“直到型循环”。repeat-until语句的含义是：“重复执行循环，直到指定的条件为真时为止”。
直到循环语句的一般形式:
Repeat
<语句1>;
:
<语句n>;
until <布尔表达式>;
其中Repeat、until是Pascal保留字，repeat与until之间的所有语句称为循环体。
说明：
①repeat语句的特点是：先执行循环，后判断结束条件，因而至少要执行一次循环体。
②repeat-until是一个整体，它是一个（构造型）语句，不要误认为repeat是一个语句，until是另一个语句。
③repeat语句在布尔表达式的值为真时不再执行循环体，且循环体可以是若干个语句，不需用begin和end把它们包起来， repeat 和until已经起了begin和end的作用。while循环和repeat循环是可以相互转化的。
对于例2中求两个正整数的最大公约数，程序可用repeat-until循环实现如下：
var
m,n,a,b,r : integer;
begin
write('Input m,n=');
readln(m,n);
a:=m;b:=n;
repeat
r:=a mod b;
a:=b;b:=r;
until r=0;
writeln('The greatest common divide is',a);
end.
以上我们已介绍了三种循环语句。一般说来，用for 循环比较简明，只要能用for循环，就尽量作用for循环。只在无法使用for循环时才用while循环和repeat-until循环， 而且 while 循环和repeat-until循环是可以互相替代的。for 循环在大多数场合也能用whiel和repeat-until循环来代替。
一般for循环用于有确定次数循环，而while和repeat-until循环用于未确定循环次数的循环。
当一个循环的循环体中又包含循环结构程序时，我们就称之为循环嵌套。
三、循环结构程序设计
例3 求1!+2!+…+10!的值。
分析：这个问题是求10自然数的阶乘之和，可以用for 循环来实现。程序结构如下：
for n:=1 to 10 do
begin
①N!的值àt
②累加N!的值t
end
显然,通过10次的循环可求出1!,2!…,10!,并同时累加起来, 可求得S的值。而求T=N!,又可以用一个for循环来实现:
t=1;
for j:=1 to n do
t:=t*j;
因此,整个程序为:
program ex4_5;
var t,s:real;
i,j,n:integer;
begin
S:=0;
for n:=1 to 10 do
begin
t:=1;
for j:=1 to n do
t:=t*j;
S:=S+t;
end;
writeln(‘s=’,s:0:0);
end.
以上的程序是一个二重的for循环嵌套。这是比较好想的方法，但实际上对于求n!，我们可以根据求出的(n-1)!乘上n即可得到，而无需重新从1再累乘到n。
程序可改为：
program ex4_5;
var t,s:real;
i,j,n:integer;
begin
S:=0;t:=1;
for n:=1 to 10 do
begin
t:=t*n;
S:=S+t;
end;
writeln(‘s=’,s:0:0);
end.
显然第二个程序的效率要比第一个高得多。第一程序要进行1+2+…+10=55次循环，而第二程序进行10次循环。如题目中求的是1！＋2！＋…＋1000！，则两个程序的效率区别更明显。
Ⅱ pascal全排列算法，急！！！急！！！
简单回溯：
这个代码是我刚编的，通过了：
const max=9;
var m,n :longint;
a:array[1..max] of longint;
procere work(j,k:longint);//j 为枚举第j个数字，k 为上次的枚举值
var i :longint;
begin
if j=m+1 then
begin
for i:=1 to m-1 do write(a[i],' ');//输出
writeln(a[m]);
end
else
for i:=k+1 to n-m+j do//第 i 个的范围是如此，k+1好理解，n-m+j可以通过数学方法证明。例 8 3，则第一个最大范围是1~6，第二个是2~7，3~8，如此
begin
a[j]:=i;
work(j+1,i);//回溯
end;
end;
begin
readln(n,m);
work(1,0);
end.
应该能看懂！！
Ⅲ Pascal算法之回溯及递推详细介绍、
在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第N项数或所有的数列元素（如果可以枚举的话），或求前N项元素之和。这种从已知数据入手，寻找规则，推导出后面的数的算法，称这递推算法。
在处理递推问题时，我们有时遇到的递推关系是十分明显的，简单地写出递推关系式，就可以逐项递推，即由第i项推出第i+1项，我们称其为显示递推关系。但有的递推关系，要经过仔细观察，甚至要借助一些技巧，才能看出它们之间的关系，我们称其为隐式的递推关系。
递推算法的关键是认真分析题意，发现递推关系，正确写出递推公式，求得边界条件，然后用循环实现即可。总结
1.递推算法的基本形式，是指编程者让计算机循环求得一序列数值，而后一项的计算结果是由上一项或多项推导出来的。有时，我们为求得一个数列的某一项，我们不得不从第一项开始，逐个计算前面每一项的值。虽然这样做的效率不很高，但它能帮助我们解决许多实际问题。
2.无论是顺着还是逆着递推，其关键是递推公式是否正确，边界条件是否正确。二者有一个出错。则所有递推结果将都是错误的。
【】
例1：已知数列1，2，5，10，17，26，37...求数列的第n项。
通过分析，我们可以发现，数列后面的数在前一项的基础上以1，3，5，7，9，11的规律增长，则可以得出增长规律的表达式为2*n-3,也就是a(1)=1,a(n)=a(n-1)+2*n-3;
还有一个规律，我们可以发现每一项依次为从0开始的自然数的平方再加1，即
(n-1)2+1,第一项（1-1）2+1，第二项（2-1）2+1，第三项（3-1）2+1... 例2:阶梯问题：题目的意思是：有N级阶梯，可以一步走上一级，也可以一步走两级，求从阶梯底走到顶端可以有多少种不同的走法。
这是一个隐式的递推关系，如果编程者不能找出这个递推关系，可能就无法做出这题来。我们来分析一下：走上第一级的方法只有一种，走上第二级的方法却有两种（两次走一级或一次走两级），走上第三级的走法，应该是走上第一级的方法和走上第二级的走法之和（因从第一级和第二级，都可以经一步走至第三级,也就是说增加的第三级有两种处理方法，第一种就是直接作为一级走一步，那么就和两级的走法一致，另一种就是与第二级合并作一步走，那么就和一级的走法一致，加起来就是一级的方法和二级的走法之和），推广到走上第i级，是走上第i-1级的走法与走上第i-2级的走法之和。很明显，这是一个菲波拉契数列。到这里，读者应能很熟练地写出这个程序。在以后的程序习题中，我们可能还会遇到菲波拉契数列变形以后的结果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。
例3：猴子吃桃问题：山中住有五只猴。一天，老大看见一堆桃子，想把桃子据为已有，却担心让老二老三知道了说自己太贪心。于是将桃分成相等的两份，却发现剩余一个，于是，老大吃掉这一个以后，再带走这堆桃的二分之一。第二天，老二也看到了这堆桃，其想法和做法与老大一样，老三老四老五也和他们的兄长想到一块去了。结果等老五吃完一个，带走一半以后，这堆桃还剩余11个。请编程计算当初这堆桃共有多少个。
这个下题目明眼人一看便知，我们如果按兄弟吃桃把桃的相反顺序倒推过去，就能知道当初桃子的总数。其递推的公式是a[n-1]=a[n]*2+1。递推的初始值是a[5]=11（又称边界条件），待求a[0]的值。相信现在大家能很容易就能写出正确的程序。在这里不过是想说明一下，递推算法不仅可以顺着推、也可逆着推的道理。
【】
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
用回溯算法解决问题的一般步骤为：
一、定义一个解空间，它包含问题的解。
二、利用适于搜索的方法组织解空间。
三、利用深度优先法搜索解空间。
四、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.
[递推是学习材料，回溯是网络]
江静
游客 回答于：2010-8-29 15:05:18
递归
递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写
程序能是程序变得简洁和清晰.
2.1 递归的概念
1.概念
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).
如:
procere a;
begin
.
.
.
a;
.
.
.
end;
这种方式是直接调用.
又如:
procere b; procere c;
begin begin
. .
. .
. .
c; b;
. .
. .
. .
end; end;
这种方式是间接调用.
例1计算n!可用递归公式如下:
1 当 n=0 时
fac(n)={n*fac(n-1) 当n>0时
可编写程序如下:
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
设n阶台阶的走法数为f(n)
显然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n>2
可编程序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
2.2 如何设计递归算法
1.确定递归公式
2.确定边界(终了)条件
练习:
用递归的方法完成下列问题
1.求数组中的最大数
2.1+2+3+...+n
3.求n个整数的积
4.求n个整数的平均值
5.求n个自然数的最大公约数与最小公倍数
6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
2.3典型例题
例3 梵塔问题
如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子
从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上
不能出现大盘压小盘.找出移动次数最小的方案.
程序如下:
program fanta;
var
n:integer;
procere move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'--->',c)
else begin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
练习:
1.计算ackerman函数值:
n+1 m=0
ack(m,n)={ ack(m-1,1) m<>0 ,n=0
ack(m-1,ack(m,n-1)) m<>0,n<>0
求ack(5,4)回溯
回溯是按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索.
3.1 回溯的设计
1.用栈保存好前进中的某些状态.
2.制定好约束条件
例1由键盘上输入任意n个符号;输出它的全排列.
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
例2.n个皇后问题:
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
回溯算法的公式如下:
3.2 回溯算法的递归实现
由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。
上述例1的递归方法实现如下：
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.
例2：n皇后问题的递归算法如下：
程序1：
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.
程序2：
说明:当n=8 时有30条对角线分别用了l和r数组控制，
用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:
program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.练习：
1.找出所有从m个元素中选取n(n<=m)元素的组合。
2.设有A,B,C,D,E 5人从事j1,j2,j3,j4,j5 5项工作每人只能从事一项,它们的
效益表如下:求最佳安排,使效益最高.
3.N个数中找出M个数(从键盘上输入正整数N,M后再输入N个正数),要求从N个数中
找出若干个数,使它们的和为M,把满足条件的数组找出来,并统计组数.
4.地图着色。如下图12个区域用4种颜色着色要求相邻的区域着不同的颜色
5.将任意一正整数(1<n<100)分解成若干正整数的和.
如:4=1+1+1+1
=2+1+1
=2+2
=3+1.
Ⅳ pascal全排列算法的得出过程
找到第一个非递减数
和他后面比它大的数中最小的一个，交换
后面的再按递减排列
比如对数列168753
3<5 5<7 7<8 但8>6，不符合递减
所以68753->73568，就是下一个数了
Ⅳ 求 free Pascal 程序设计的一道题，关于全排列
全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何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。
Ⅵ PASCAL算法知识题~~高分~紧急~
6.1 穷举策略的概念
所谓枚举法，指的是从可能的解的集合中一一枚举各元素， 用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。
有些问题可以用循环语句和条件语句直接求解，有些问题用循环求解时循环次数太多，无法编写程序，怎么办？下面是用“千军万马过独木桥，适者存”的方式实现穷举策略的。
6.2 典型例题与习题
例1.将2n个0和2n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。
例如，当n=2时，即22个0和22个1排成如下一圈：
比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，...可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。
程序说明：
以n=4为例，即有16个0，16个1，数组a用以记录32个0，1的排法，数组b统计二进制数出现的可能性。
程序清单
PROGRAM NOI00;
VAR
A :ARRAY[1..36] OF 0..1
B :ARRAY[0..31] OF INTEGER;
I,J,K,S,P:INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1; A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27
WHILE A[J]=1 DO J:=J-1;
( A[J]:=1 )
FOR I:=J+1 TO 27 DO ( A[i]:=0 )
FOR I:=0 TO 31 DO B[I]:=0;
FOR I:=1 TO 32 DO
BEGIN
( S:=0)
FOR K:=I TO I+4 DO S:=S*2+A[k];
( B[S]:=1 )
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF ( S=32 ) THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.
例2：在A、B两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数<=20，且每条路段上的距离均为一个整数)。
A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离<=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。
例如：下图所示是当N=1时的情况：
从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。
算法说明：本题采用穷举算法。
数据结构：N：记录A，B间路站的个数
数组D[I，0]记录第I-1个到第I路站间路段的个数
D[I，1]，D[I，2]，…记录每个路段距离
数组G记录可取到的距离
程序清单：
program CHU7_6;
var i,j,n,s:integer;
b:array[0..100] of integer;
d:array[0..100,0..20] of integer;
g:array[0..1000] of 0..1;
begin
readln(n);
for i:=1 to n+1 do
begin
readln(d[i,0]);
for j:=1 to d[i,0] do read(d[i,j]);
end;
d[0,0]:=1;
for i:=1 to n+1 do b[i]:=1;
b[0]:=0;
for i:=1 to 1000 do g[i]:=0;
while b[0]<>1 do
begin
s:=0;
for i:=1 to n+1 do
s:= s+d[i,b[i]];
g[s]:=1;j:=n+1;
while b[j]=d[j,0] do j:=j-1;
b[j]:=b[j]+1;
for i:=j+1 to n+1 do b[i]:=1;
end;
s:=0;
for i:=1 to 1000 do
s:=s+g[i];
writeln(s);readln;
end.
2.1 递归的概念
1.概念
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).
如:
procere a;
begin
.
.
.
a;
.
.
.
end;
这种方式是直接调用.
又如:
procere b; procere c;
begin begin
. .
. .
. .
c; b;
. .
. .
. .
end; end;
这种方式是间接调用.
例1计算n!可用递归公式如下:
1 当 n=0 时
fac(n)={n*fac(n-1) 当n>0时
可编写程序如下:
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
设n阶台阶的走法数为f(n)
显然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n>2
可编程序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
2.2 如何设计递归算法
1.确定递归公式
2.确定边界(终了)条件
练习:
用递归的方法完成下列问题
1.求数组中的最大数
2.1+2+3+...+n
3.求n个整数的积
4.求n个整数的平均值
5.求n个自然数的最大公约数与最小公倍数
6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
2.3典型例题
例3 梵塔问题
如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子
从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上
不能出现大盘压小盘.找出移动次数最小的方案.
程序如下:
program fanta;
var
n:integer;
procere move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'--->',c)
else begin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
3.1 回溯的设计
1.用栈保存好前进中的某些状态.
2.制定好约束条件
例1由键盘上输入任意n个符号;输出它的全排列.
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
例2.n个皇后问题:
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
回溯算法的公式如下:
3.2 回溯算法的递归实现
由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。
上述例1的递归方法实现如下：
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.
例2：n皇后问题的递归算法如下：
程序1：
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.
程序2：
说明:当n=8 时有30条对角线分别用了l和r数组控制，
用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:
program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.
7.1 贪心策略的定义
贪心策略是：指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。
其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
例1：在n行m列的正整数矩阵中，要求从每一行中选一个数，使得选出的n个数的和最大。
本题可用贪心策略：选n次，每一次选相应行中的最大值即可。
例2：在一个N×M的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。
本题用贪心策略不能得到最优解，我们以2×4的矩阵为例。 3 4 6
1 2 10
若按贪心策略求解，所得路径为：1,3,4,6；
若按动态规划法求解，所得路径为：1,2,10,6。
例3:设定有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短?
本题不能用贪心算法求解:理由是若n=3,m=6 各作业的时间分别是11 7 5 5 4 7
用贪心策略解(每次将作业加到最先空闲的机器上)time=15,用搜索策略最优时间应是14,但是贪心策略给我们提供了一个线索那就是每台处理上的时间不超过15,给搜索提供了方便。
总之：
1. 不能保证求得的最后解是最佳的；
2. 只能用来求某些最大或最小解问题；
3. 能确定某些问题的可行解的范围，特别是给搜索算法提供了依据。
7. 2 贪心策略的特点
贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：
1、贪心选择性质：
所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。
2、局部最优解：
我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，但贪心策略比动态规划时间效率更高站用内存更少，编写程序更简单。
7.3 典型例题与习题
例4：背包问题：
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
程序如下：
program beibao;
const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;
procere init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;
procere make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i]<bi[j] then begin
temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;
begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]>xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i<=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.
例5：旅行家的预算问题：
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，给定两个城市间的距离d1，汽车油箱的容量是c，每升汽油能行驶的距离d2，出发时每升汽油的价格是p，沿途加油站数为n（可为0），油站i离出发点的距离是di，每升汽油的价格是pi。
计算结果四舍五入保留小数点后两位，若无法到达目的地输出“No answer"
若输入：
d1=275.6 c=11.9 d2=27.4 p=8 n=2
d[1]=102 p[1]=2.9
d[2]=220 p[2]=2.2
output
26.95
本问题的贪心策略是：找下一个较便宜的油站，根据距离确定加满、不加、加到刚好到该站。
程序如下:
program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil[i-1]^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procere buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procere solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do
begin
inc(j);
s:=s+oil[j]^.way-oil[j-1]^.way
end;
if s<=maxway+zero then
if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then
oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else
begin
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.
例6:n个部件,每个部件必须经过先A后B两道工序。
以知部件i在A,B 机器上的时间分别为ai，bi。如何安排加工顺序，总加工时间最短？
输入：
5 部件 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9
输出：
34
1 5 4 2 3
本问题的贪心策略是A机器上加工短的应优先，B机器上加工短的应靠后。
程序如下：
program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procere init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].a<c[i].b then c[i].m:=c[i].a else c[i].m:=c[i].b;
c[i].o:=i;
end;
end;
procere sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].m<t then begin t:=c[j].m;k:=j end ;
if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procere playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procere calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2<t1 then t2:=t1;
t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.