pascal基础算法

① C语言/PASCAL(算法基础)问题

数据结构算法 编程实现样例详解
请仔细阅读，建议打印。注意比较细节的差异，关于指针问题请看 “难点答疑”。

编程步骤
程序结构框架
样例源代码清单（以顺序表插入功能为例）
一：
编写公共头文件
u 引用的库文件
u 定义系统常前闹量
建议文件名前加姓名:
sjCommon.h
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
二：
编写存储郑培结构头文件
u 定义元素类型
u 定义结喊悔唯构体
顺序：sjSeqList.h
链式：sjLinList.h
顺序表的结构体
单链表的结构体
#define ElemType int
#define MAXSIZE 10
typedef struct
{
ElemType elem[MAXSIZE];
int last;
}SeqList;
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node * next;
}Node, *LinkList;
标准的线性表、栈、队列、串的存储结构样例
顺序栈的结构体
顺序队列的结构体
#define Stack_Size 50
typedef struct
{
StackElementType elem[Stack_Size];
int top;
}SeqStack;
#define MAXSIZE 50
typedef struct
{
QueueElementType element[MAXSIZE];
int front;
int rear;
}SeqQueue;
顺序串的结构体
堆分配存储的串结构体
#define MAXLEN 40
typedef struct
{
char ch[MAXLEN];
int len;
}SString;
typedef struct
{
char *ch;
int len;
}HString;
自定义结构体样例
约瑟夫环结构体
城市坐标结构体
typedef struct data{
int num; //用于存放人的序号
int pwd; //用于存放密码
}typedata;

typedef struct node{
typedata data;
struct node *next;
}YSFNode, *YSFLinkList;
typedef struct CityNode
{
char name[10];
float x;
float y;
struct CityNode *next;
}CityNode;
三：
编写实现所需功能的主程序
加载头文件
#include "sjCommon.h"
#include "sjSeqList.h"
应用教材现有的数据结构算法1：
初始化顺序表
int InitList(SeqList *L,int r) /*顺序表初始化，输入r个元素*/
{
L->last =r-1;
printf("请输入线性表的%d个元素值:\n",r);
for(int i=0; i<=L->last; i++)
{
scanf("%d",&L->elem[i]);
}
return(OK);
}
应用教材现有的数据结构算法2：
在顺序表L中第i个数据元素之前插入一个元素e
int InsList(SeqList *L,int i,ElemType e)
{
int k;
if((i<1) || (i> L->last+2)) /*首先判断插入位置是否合法*/
{
printf("插入位置i值不合法");
return(ERROR);
}
if(L->last>= MAXSIZE-1)
{
printf("表已满无法插入");
return(ERROR);
}
for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置*/
L->elem[k+1]=L->elem[k];
L->elem[i-1]=e; /*在C语言数组中，第i个元素的下标为i-1*/
L->last++;
return(OK);
}

编写用户自定义算法：
输出顺序表中的所有元素
int DisplayList(SeqList *L)
{
for(int i=0; i<L->last; i++)
{
printf("%d -> ",L->elem[i]);
}
printf("%d\n",L->elem[i]);
return(OK);
}
编程主函数main（）：
u 定义需要的基本类型和结构体类型的变量
u 调用前面的算法，实现输入、处理、输出
void main()
{
SeqList *l;
int p,q;
l=(SeqList*)malloc(sizeof(SeqList)); /*开辟顺序表存储空间，返回起始位置*/
InitList(l,4);
printf("顺序表中初始元素如下:\n");
DisplayList(l);
printf("请输入要插入的位置:\n");
scanf("%d",&p);
printf("请输入要插入的元素值:\n");
scanf("%d",&q);
InsList(l,p,q);
printf("插入后顺序表中元素如下:\n");
DisplayList(l);
system("pause");
}

难点答疑： 关于C/C++语言中的结构体与指针
1. 结构体和指针的引入原因
我们已经知道数组，它用来保存线性数据，但是它有许多缺点：
◇ 数组的大小是固定的，在程序运行期间是不能改变的。我们在定义数组时必须足够大，保证程序运行时不会溢出。但是，这也常常导致大量数组存储单元的浪费。
◇ 数组需要一块连续的内存空间。但当应用程序较大，数组需要的内存块也较大时，这可能会降低程序的效率。
◇ 如果在数组元素中，有较多的插入操作，则被插元素后的元素需要向后移位，这也浪费机器的运行时间。
链表也是表示线性数据最有用的方法之一，用链表保存线性数据，可以克服数组的问题。使用链表数据结构需要结构体和指针作为基础。
2. 结构体的特点
在实际问题中，一组数据往往具有不同的数据类型。例如，在学生登记表中，姓名应为字符型；学号可为整型或字符型；年龄应为整型；性别应为字符型；成绩可为整型或实型。由于数组还必须要求元素为相同类型，显然不能用一个数组来存放这一组数据。因为数组中各元素的类型和长度都必须一致，以便于编译系统处理。
而结构数据类型（结构体）就可以解决这个问题。为了满足程序设计的需要，我们自己定义数据类型，称之为自定义数据类型，结构是自定义数据类型中的一种，它可将多种数据类型组合在一起使用。
3. 结构体的定义方法
方法一：先定义结构体，再定义变量名
方法二：在定义类型的同时定义变量
struct Child {
double height;
char name[10];
int age;
char sex;
};
struct Child cha, chb;
struct Child {
double height;
char name[10];
int age;
char sex;
}cha,chb;
方法三： 直接定义结构体变量

struct {
double height;
char name[10];
int age;
char sex;
} cha, chb;
这样，我们就定义了一个结构类型Child，struct是关键字。Child类型包含1个double、1个int和2个char域（或成员），它可以与C++的基本数据类型一样地使用。（注意）结构类型定义也是一个语句，所以结尾必须有分号（;），否则，会产生编译错误。同时定义了两个Child类型的变量：cha, chb
几点说明：
(1) 结构体类型和结构型变量是不同的概念，要先定义结构体类型，然后把变量定义为该结构类型；只能对变量进行操作，编译时也只为变量分配存储空间；
(2) 结构体中的成员可以单独使用
(3) 成员也可以是一个结构体变量

4. 结构体类型变量的引用
结构体成员的引用方法： 结构变量名.成员名
如 cha.height=1.65
5. 结构体变量的初始化
struct Child {
double height;
char name[10];
int age;
char sex;
}cha={1.62,”小诗” ,20,’F’};
6. 结构体数组
结构体类型的定义与前面的定义方法相同，只需把变量名定义成数组形式即可：如cha[2]
结构体数组初始化举例：
struct Child {
double height;
char name[10];
int age;
char sex;
}cha[2]={{1.62，”小诗”，20，’F’}，{1.78，”小飞”，22，’M’}};
7. 为什么要用指针
指针的好处在于：只要知道数据的位置就可以访问任何大小的数据。

下图是一个简单的链表示意图：

该链表由3个结点组成，其中每个结点都分为两个域，一个是数据域（即图中的大写字母A、B、C），存放各种实际的数据，如学号num、姓名name、性别sex和成绩score等。另一个域为指针域，存放下一结点的首地址。比如第一个结点的指针域存放的地址是1475，就是第二个结点的首地址。链表中的每一个结点都是同一种结构类型。
8. 指针使用说明
（1）关于指针运算符
两个运算 * 和 & 的作用正好相反，指针间接访问运算符 * 的意思是“指针指向的对象”，而地址运算符&的意思是“得到地址”，*从地址中获得数据的内容，而&获得该数据的地址。
修改指针所指向的数据时要使用间接访问运算符 *，要修改指针所指向的地址时，只需修改指针本身。例如：（*P）++ 将指针所指向的数据增加1，而P++则是将指针指向了下一个地址。
（2）关于指针的进一步介绍

9．几种线性结构的算法实现总结（C语言实现）
顺序表的建立与操作算法
单链表的建立与操作算法
栈的建立与基本操作的算法
队列的建立与基本操作算法

② 排序算法pascal

这题我前不久做过，用冒泡排序就能解决了，不信你编一个试一试。
思想，就是按照先序或者后序，将最小的放在最左边，不用管途中的任何情况，然后就移动次小的，再移动更小的，直到将倒数第二个移动到位后，最后一个也移好了。
所以，可以将这种思想看成是冒泡排序的一个变形把。
代码很简单，就不给了，如果你实在编起困难，再说把，我觉得思想比代码更重要，代码能力可以做题实现，但是思想必须自己体会了。

奖学金
program a1(input,output);
var
n,x,y,z,i,j:integer;
a:array[1..300,1..3] of integer;
procere swap(var a,b:integer); {交换过程}
var
s:integer;
begin
s:=a;
a:=b;
b:=s;
end;
begin
readln(n);
for i:=1 to n do
begin
readln(x,y,z);
a[i,1]:=i;
a[i,2]:=x;
a[i,3]:=x+y+z;
end;
for i:=1 to n-1 do {选择排序}
for j:=i+1 to n do
if (a[i,3]<a[j,3]) or ((a[i,3]=a[j,3]) and (a[i,2]<a[j,2])) or ((a[i,1]>a[j,1]) and (a[i,3]=a[j,3]) and (a[i,2]=a[j,2])) then
begin
swap(a[i,1],a[j,1]);
swap(a[i,2],a[j,2]);
swap(a[i,3],a[j,3]);
end;
for i:=1 to 5 do
writeln(a[i,1],' ',a[i,3]);
end.

③ Pascal入门

算法设计题选
（一）、算法设计：
一、筛选法

1：求1—100间的所有素数。
分析：用筛选法，先把2—100的数存到一个数组中，然后先把2的所有倍数删除掉（即让此数变为0），再删3的倍数，继续往上就是5的倍数，7的倍数……，最后，剩下的数(即数组中不为0的数)就是素数。
Var n:array[2..100] of integer;
I,j,k:integer;
Begin
For I:=2 to 100 do n[I]:=I;
I:=2;
Repeat
J:=1;
Repeat
J:=j+1;
K:=I*j;
if n[k]>0 then N[k]:=0;
Until (j+1)*i>100;
Repeat
i:=i+1;
until (n[i]>0) or (i>50);
Until i>50;
for i:=2 to 100 do if n[i]>0 then write(n[i]:4);
end.
另外，该题也可利用集合来做，同样用筛选法：
var ss:set of 2..100;
i,j,k:integer;
begin
ss:=[2..100];
for i:=2 to 50 do begin
j:=1;
repeat
j:=j+1;
k:=i*j;
if k in ss then ss:=ss-[k];
until k+i>100;
end;
for i:=2 to 100 do if i in ss then write(i:3);
end. 集合SS用来存放数

把SS中2至50的倍数全部删除

2：不相同的余数问题，即“秦王暗点兵”或“韩信点兵”：
有一楼房的楼梯级数很奇特，一步跨二级多一级，一步跨三级多二级，如果分用四、五、六、七去除级数分别余三、三、五、五。问这楼房共有多少级阶梯？（已知不超过400级）。
分析：已知级数不超过400级，我们可仿照求素数的方法，把1—400存进一个数组中，然后这些数用2、3、4、5、6、7分别清镇物去除，如果余数分别不为1、2、3、3、5、5就删除它（把它设为0），最后，答液最小的一个没有被删除的数就是解。
Var n:array[1..400] of integer;
I,j,k:integer;
Const a:array[1..6] of integer=(2,3,4,5,6,7);
b:array[1..6] of integer=(1,2,3,3,5,5);
Begin
For I:=1 to 400 do n[I]:=I;
for i:=1 to 6 do begin
for k:=1 to 400 do begin
if n[k]>0 then begin
if k mod a[i]<>b[i] then begin
n[k]:=0;
end;
end;
end;
end;
i:=0;
repeat
i:=i+1;
until n[i]>0;
write(n[i]:4);
end.

除数
余数

找最小的一个没有被删除的数
分析：用上述方法由于要删除的数非常多，因此速度较慢，我们可以反过来想，把满足余数条件的数加上记号，最后，最小的一个加上了六个记号的数旅中就是答案。
Var n:array[1..400] of integer;
I,j,k:integer;
const a:array[1..6] of integer=(2,3,4,5,6,7);
b:array[1..6] of integer=(1,2,3,3,5,5);
Begin
For I:=1 to 400 do n[I]:=0;
for k:=1 to 400 do begin
for i:=1 to 6 do begin
if k mod a[i]=b[i] then n[k]:=n[k]+1;
end;
end;
i:=0;
repeat
i:=i+1;
until n[i]=6;
write(i:4);
end.
这样，速度要快很多。大家思考一下下题：《孙子算法》有题：今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问物几何？（最小正数解）。

3：狼追兔子，兔子躲进了10个环形分布的洞的某一个中。狼在第1个洞中没有找到兔子，就间隔1个洞，到第3个洞中去找，也没找到兔子，就间隔2个洞，到第6个洞中去找。以后狼每次多隔1个洞去找兔子，……。这样狼一直找不到兔子。请问兔子可能躲在哪个洞中？
分析：该题看似简单，只要每次把狼找过的洞删除就行了，但是，（问题1）这种删除操作的结束状态（条件）是什么呢？（问题2）而且，狼的搜索过程中，如果要间隔11个洞时，我们是否可以认为就是间隔1个洞？
实际上，第一个问题应该是当狼回到第1个洞，并且又上间隔1个洞去找兔子时，就应该结束删除操作，因为此后的搜索是重复以前的搜索了，此时，那些没有被删除过的洞就是答案。这里，大家一定不能想当然地认为：结束条件就是只剩下一个洞的时候！题目中并没有说明只有一个答案，事实上是有四个洞的！
第二个问题也是可行的。因为只有10个洞，间隔11个洞和间隔1个洞的作用是相同的。
var d:array[1..10] of integer;
i,j,k,l:integer;
begin
for i:=1 to 10 do d[i]:=1;
i:=1;
j:=1;
repeat
d[i]:=0;
j:=j+1;
if j>10 then j:=j-10;
i:=i+j;
if i>10 then i:=i-10;
until (i=1) and (j=1);
for i:=1 to 10 do if d[i]>0 then write(i);
end.

习题
1、 作800—1000的素数表。
答案：809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
2、 有一堆礼物，工作人员无论是分成二个一份，还是三个、四个、五个、六个一份，总是多一个。请问这堆礼物至少多少个？ 答案：61
3、 一付扑克中拿出所有的黑桃A……K按顺序排好。第一次翻出第一张牌——A，放在一边，再拿出第二张放到牌的最下面。以后每次都翻出一张牌，再把一张牌放到最后，问第八次翻出的牌是哪一张？ 答案：4

4、六（2）班有四个数学天才，数学才能令人惊叹，每次上课时都对数学老师的讲课进度不满，甚至经常怪老师讲的内容太简单，太慢，没有顾及他们四个天才的感受。四个天才在数学课上那上活跃得不得了，基本上都是不等数学老师把课讲完就把答案给叫了出来，数学老师也没办法，大凡天才在小时候都是如此吧，数学老师安慰自己。
这天的数学课是老师公布同学们的评价后的第一节课，四位数学天才在过程性评价中得到的都是B，这下不得了了，四人一起合计，觉得数学老师欺人太甚了，非得在这节数学课上整整老师不可，大家想出了A计划、B计划甚至C计划，决定这次要给数学老师一个好看，让全班，不，是全校都知道他们四个数学天才的厉害。
可是令他们没想到的是，数学老师竟然先下手为强了，一上课还不等他们四人发难，就把他们四人叫到前面，这节课竟然是要让他们四个人做老师的道具！老师让他们每人手上拿一张写着一个自然数的纸，不许说话，由坐在位置上的其他同学进行抢答，回答的答案就是一个自然数，但是要满足以下两个条件：
1、这个数能够被他们手上四个数字整除；
2、这个数是满足条件一的数字中最大的数。
四位天才分别来自四个组，但是他们不能说话，只能是他们自己组里的同学抢答答案，答对的加1分，答错的倒扣1分，而如果哪个天才说了话，那么他的组就将被扣2分！最后得分最高的那个小组的每一位同学将获得老师的奖品——福娃，这太吸引人了，而且自己无论如何都不能说话，要不自己小组将肯定拿不到第一名了，那不得被同学们骂死才怪呢。
为了小组的荣誉，四位天才当然不能说话了，他们只能眼巴巴地看着自己的同学回答这些他们认为是简单得不得了的题，不过四位天才中的一位是位编程高手，他也没闲着，自己在大脑里把完成这个任务的程序给编了出来。你能编写出这个程序吗？
输入格式：
A B C D （四个自然数，每个数都小于32767）
输出格式：
N （满足上述条件的自然数）
输入样例：
3 6 9 12
输出样例：
3

测试数据：
序号 分值 输入 输出
1 20 1 2 3 4 1
2 20 30000 29997 29994 29991 3
3 20 16 48 24 160 8
4 20 200 400 100 300 100
5 20 204 68 85 136 17

二、排序方法

本小节讨论几种排序方法。何为排序呢？就是把一些数字按递增或递减的顺序排列。例如：4，3，5，1，2这五个数，按从小到大的顺序排列是：1，2，3，4，5；按从大到小的顺序排列是：5，4，3，2，1。

1、双数组排序法：
用一个数组存放未经排序的数，然后按顺序找出未经排序数中的最大数，按顺序存放到另一个数组中，要考虑的问题是：怎样把未经排序数组中已经找出的数删除。
程序如下：
var n,m:array[1..10] of integer;
i,j,max,k:integer;
begin
for i:=1 to 10 do read(n[i]);{读入10个数}
for i:=1 to 10 do begin
max:=0;
for j:=1 to 10 do begin {从数组N找到最大的数}
if n[j]>max then begin
max:=n[j];
k:=j; {记住该位置}
end;
end;
m[i]:=max;{存入数组M中}
n[k]:=-30000;{删除该数，把值变为-30000}
end;
for i:=1 to 10 do write(m[i]:3);{打印已排好序的数}
end.

2、插入法排序：
插入法排序是把存放在数组中的未经排序的数逐个插入到另外一个数组中。如何找到每个数的正确位置呢？我们应该用动态查找的方法，从已排序的数组中从最左边开始查找，直到找到一个数大于等于待插入的数时，该数之前就是我们要找的位置。此方法可用数组来完成，也可用链表来完成。程序如下：
把数先存放在一个数组中，再逐个插入到另一个数组中：
var n,m:array[1..10] of integer;
i,j,k,l:integer;
begin
for i:=1 to 10 do read(n[i]); {读入10个数存放到数组N中}
m[1]:=n[1]; {在数组M中存放第一个数}
for i:=2 to 10 do begin {把数组N中第2到第10个数逐个插入到数组M中}
j:=0;
repeat
j:=j+1;
until (j=i) or (m[j]>=n[i]); {找到待插入的数在M中的位置}
if j=i then m[j]:=n[i] else begin
for l:=i-1 downto j do m[l+1]:=m[l]; {把该位置后的数后移}
m[j]:=n[i]; {把待插入的数放在正确位置}
end;
end;
for i:=1 to 10 do write(m[i]:3); {打印}
end.

3、冒泡法排序
冒泡法：这是最常用的一种排序方法，其实质是：先把数据存放在数组中，然后从第一个开始，分别与其后所有数据进行比较，如果第一个比其后某个数据小，则交换它们的值，一直到第一个与其后所有数据比较完，这时第一个数据就是最大的一个；然后再把第二个数据再与其后数据进行比较，比较完后，第二个数据则为第二大的，这样直到倒数第二个数据比较完后，整个数组就已经按从大到小的顺序排列了。其作用示意如下：
假设我们已经把6个数据分别存放在N[1]至N[6]中，其值分别为：3,1,5,9,2,6。
交换前的值为： 3，1，5，9，2，6
第一步，把第一个值与其后第一个进行比较，这时3>1，所以值不变： 3，1，5，9，2，6
第二步：把第一个值与其后第二个进行比较，这时3<5，所以值交换： 5，1，3，9，2，6
第三步：把第一个值与其后第三个进行比较，这时5<9，所以值交换： 9，1，3，5，2，6
…… ……
当第一个值与其后所有值比较完后，第一个值已经是最大的，数组值为： 9，1，3，5，2，6
这时，重复上述第一步的操作，只是把第一个值换成第二个值，第一个值即第二个值与其后第一个值进行比较，这时1<3，所以交换其值： 9，3，1，5，2，6
第二个值与其后所有值比较完后，数组值为： 9，6，1，3，2，5
再重复进行第三个值与其后值的比较，直到第五个值与第六个值比较完后，这时数组的值已经变为： 9，6，5，3，2，1
至此，数组已经按从大到小的顺序排好了。
程序如下 ：[例6、1]
Var n:array[1..10] of integer;
I,j,t:integer;
Begin
For I:=1 to 10 do Readln(n[I]);
For I:=1 to 9 do begin
For j:=I+1 to 10 do begin
If n[I]<n[j] then begin
T:=n[I];
N[I]:=n[j];
N[j]:=t;
End;
End;
End;
For I:=1 to 10 do begin
Write(n[I]:5);
End;
End. 说明一个数组型变量

从键盘读入10个数据存放在数组N中
参加比较的第一个数据为第1至第9个。
第二个数据为第一个数据之后所有的数据
如果n[I]<n[j]则用以下三句来交换其位置

打印排序后的结果

四、选择排序：
设数组中有N个数，取I=1，2，3，……N-1，每次找出后N-I+1个数字中最小的与第I个数字交换位置。程序如下：
var n:array[1..10] of integer;
i,j,k,t,min:integer;
begin
for i:=1 to 10 do read(n[i]);
for i:=1 to 9 do begin
min:=30000;
for j:=i to 10 do begin {在第I到第10个数中找到最小的一个}
if n[j]<min then begin
min:=n[j];
k:=j; {记录该位置}
end;
end;
t:=n[i];
n[i]:=n[k];
n[k]:=t;
end;
for i:=1 to 10 do write(n[i]:4);
end.

5、快速排序：
（1）把N个数存放在数组S中，当前集合为S中所有数。
（2）把当前集合第一个数定为标准数K，把S分为两个子集，左边子集S1为小于等于K的数，右边子集S2为大于等于K的数。这一操作是这样完成的：（A）、设定集合第一个数作为标准数K，设定指针I、J，I指向集合第一个数，J指向集合最后一个数；（B）、把J向左移（J：=J-1），直到找到一个S[J]<=K，则交换S[I]与S[J]的位置，并把I后移（I：=I+1）；（C）、把I向右移（I：=I-1），直到找到一个S[I]>=K，则交换S[I]与S[J]的位置，并把J前移（J：=J-1）；（D）、重复B、C直到I=J。
（3）依次把S1、S2作为当前集合，以第一个数作为标准数K，重复第2步，直到S1、S2及其产生的子集元素个数为1。
详细过程举例如下：
原序： [26 5 37 1 61 11 59 15 48 19]
一： [19 5 15 1 11] 26 [59 61 48 37]
二： [11 5 15 1] 19 26 [59 61 48 37]
三： [1 5] 11 [15] 19 26 [59 61 48 37]
四： 1 5 11 [15] 19 26 [59 61 48 37]
五： 1 5 11 15 19 26 [59 61 48 37]
六： 1 5 11 15 19 26 [37 48] 59 [61]
七： 1 5 11 15 19 26 37 48 59 [61]
八： 1 5 11 15 19 26 37 48 59 61

快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：
var n:array[1..10] of integer;
a:integer;
procere dg(x,y:integer);{X，Y表示集合的左右边界，即把第X到第Y个数进行排序}
var i,j,b,c,d,e,f,k:integer;
begin
k:=n[x];{标准数}
i:=x; {I，J为指针}
j:=y;
repeat
j:=j+1;
repeat {从J往左找到一个n[j]<=k}
j:=j-1;
until (n[j]<=k) or (i>j);
if i<=j then begin
b:=n[i]; {交换}
n[i]:=n[j];
n[j]:=b;
i:=i+1; {左指针右移}
end;
i:=i-1;
repeat {从I往右找到一个n[i]>=k}
i:=i+1;
until (n[i]>=k) or (i>j);
if i<=j then begin
b:=n[i]; {交换}
n[i]:=n[j];
n[j]:=b;
j:=j-1;
end;
until i>j;
if j-x>0 then dg(x,j); {如果集合中不止一个数则进入下一层递归，X，J为新边界}
if y-i>0 then dg(i,y); {如果集合中不止一个数则进入下一层递归，I，Y为新边界}
end;

begin
for a:=1 to 10 do read(n[a]);
dg(1,10);
for a:=1 to 10 do write(n[a]:4);
end.

三、数论问题

1、设有一块1X1正方形钢板，现需将它分成N个小正方形的钢板。
例如：

输出格式例：0.25X0.25:7
0.75X0.75:1 （表示分割成0.25X0.25的正方形7个，0.75X0.751个）
分析： （1）将一个正方形分成4个，则可增加3个正方形。
（2）以6、7、8个正方形时为基础，则可得到增加的结果：
6 7 8
9 10 11
12 13 14
…………
因此由上述递增关系可推得一个递归关系。

2、在平面上有N条直线，且无三线共点，问这些直线能组成多少种不同的交点数。例如：
分析：（1）N条无三条直线交于一点的直线最多可能有Cn2个交点，即1/2*N*(N-1)个交点。
（2）对于N条直线，如果N条全部平行，则交点数为0；
如果一条不平行，则交点数为N-1；
如果有两条不与其它平行，则有两种情况，一种这两条直线平行，则交点有（N-2）*2；一种是这两条直线不平行，则交点有（N-2）*2+1。
(3)由上述可知：N条直线如果有R条直线平行，相当于（N-R）条直线的各种情况再加上R*（N-R）个交点。也就是说：
我们已知： 2条直线的交点情况是：0，1；
3条直线的交点情况是：0，2，3；
4条直线的交点情况可分为：（1）4条直线平行，0个交点；（2）3条直线平行，1条直线的情况+3*1=3个交点；（3）2条直线平行，2条直线的情况+2*2个交点，也就是有0+4，1+4两种情况；（4）1条直线平行，3条直线的情况+1*3，也就是有3，5，6三种情况。综合上述分析，可知：4条直线的交点情况有：0，3，4，5，6五种情况。
也就是说，要计算N条直线的情况，应先计算N-1、N-2、……、2条直线的情况。我们可以用数组来存放2、3、……N条直线的各种情况。

3、哈夫曼编码：给定一个字符串（假定全由26个小写字母中的前若干个字母组成，总长度不超过50个字符），对字符串每个字符进行编码，编码原则如下：
（1）只能用0，1字符串对字符进行编码；
（2）要求根据编码识别字符串时不会出现混乱、无法识别的情况；
（3）要求字符串编码后的总长度最短。
例如：对于字符串：abbabcdefcdabeg，其编码方式可以如下：
a-000, b-001, c-010, d-011, e-100, f-101, g-110
这时总长度为45。
但其编码方式也可以如下：
a-01, b-00, c-100, d-101, e-110, f-1110, g-1111
这时总长度为42。
分析： （1）字符串中共有多少个不同的字符，以及每个字符出现的次数。毫无疑问，要使总长度最小，出现次数越多的字符的编码应该越短。
（2）位数少的编码与位数多的编码如何才能不混乱呢？应该从左边前若干位进行区别。例如，编码有一个为“0”时，就不能出现“00”，“01”，“001”，“010”等等编码。当编码中有一个为10时，就不能出现100，101，1000等编码。

四、递 归

这里我们将再一次讨论PASCAL语言的递归算法设计方法。一般的，用BASIC语言实现递归是非常困难的，而用PASCAL语言的自定义函数或过程来实现就要方便、快捷的多，这就是为什么在信息学竞赛中同学们广泛使用PASCAL语言的原因。
我们已经学习自定义函数、过程的编写以及递归的实现方法，这里再简单重复一下。

递归函数
递归函数是PASCAL语言编程中通向高级算法的必由之路，要掌握递归函数必须要先掌握递归这个概念。
什么是递归呢？我们来看一个例题，在此之前我们先学会什么是数列。数列即一序列数的总称，如：1，2，3，4，5，6，7，8……是自然数数列；2，4，6，8，10，……是自然偶数数列；象这种以某种关系定义的数的序列就叫数列。数列的名称可任取，象上述第一个数列如果名为A，第二个数列名为B，则第一个数列的各个数字的名字就为：A1，A2，A3，A4……或A（1），A（2），A（3）……。数列A的数字关系是：（1）A（N）=A（N-1）+1（N>1）；（2）A（1）=1；由此两个关系，我们只要知道该数列中任何一个数的序号，就可推知该数的数值。
那么如果对于数列A，我想知道A（100）是多少该如何推算呢？
由上述关系我们已经知道：
A（100）=A（99）+1，即要知道A（100），我们就必须先知道A（99）；而
A（99）=A（98）+1；即要知道A（99）就必须先知道A（98）；由此类推
A（98）=A（97）+1；
………………
A（3）=A（2）+1；
A（2）=A（1）+1；而此时就已经不用继续推算下去了，因为A（1）是已知的了。
而实际上，上述推算过程就是递归过程。即要完成某个计算，必须先完成其前的另一个计算，以此类推，直到推到一个已知的值为止。

[例1]有一个数列N，已知：N（1）=1，N（X）=N（X-1）*3-1（X>1），求N（20）；
我们已经知道，由递归关系，我们要求N（20），就必须知道N（19）……N（1），而最终N（1）是已知的，所以这个递归关系我们就可以用PASCAL语言很好地表现出来。以下我们用递归函数来完成，请大家注意递归的实现方法，即自己调用自己。
Var n20:integer;
Function dg(n:integer):longint;
Begin
If n:=1 then dg:=1
Else begin
Dg:=dg(n-1)*3-1;
End;
End;
Begin
N20:=dg(20);
Writeln(n20);
End. 定义程序主体中的变量
定义自定义函数DG，形式参数1个，用以记录现在是推算到了第几个数。
递归出口是当N等于1时，DG的值为1

如果N不等于1，我们就继续递归，这就是递归关系式

程序主体
调用递归函数
由上可以看出，用递归函数来实现算法，程序主体可以变得非常简单，只需少数几句即可。而递归函数就显得至关重要了，由上述程序可以看出，递归函数的实现实际上就是一个自己调用自己的函数。直到调用到已知的数为止。递归问题我们还将在递归过程中详细分析。
由上可见，递归过程实际上只有一句，IF 条件 THEN 出口 ELSE 调用下一次递归；

递归过程

我们从一个例题中来看看递归的实际实现及运行过程。

[例2]打印‘A’、‘B’、‘C’、‘D’、‘E’这五个字符任意排列的所有情况。
分析，此题可用五重循环来做，但那样就把此题给复杂化了，运行速度也要慢很多，而此题用递归过程来做的话就要简单许多。我们把递归过程定为每次从五个字符中取一个字符，当然这个字符必须与已经取得的字符全不相同，而我们取得的字符存放在一个字符串中，并把它作为形式参数（这一点至关重要，否则答案将完全错误）。当我们已经取完五个字符后，在取第六个字符时，递归过程就将结束。这就是递归的出口。这样我们就能把所有结果找出来。程序如下：
Var t:longint;
Procere dg(n:integer;s:string);
Var I:char;
Begin
If n=6 then begin
T:=t+1;
Writeln(t:5,’ ‘,s);
End else begin
For I:=’A’ to ‘E’ do begin
If pos(I,s)=0 then begin
Dg(n+1,s+I);
End;
End;
End;
End;
Begin
T:=0;
Dg(1,’’);
End. 计算答案总数的计数器
递归过程有两个形式参数，N表示当前取第N个字符，S存放已经取得的N-1个字符；

N等于6时，递归到了一个答案
答案总数加1
把答案数及答案打印出来
从此句中返回调用此过程的上一过程
从A—E五个字符中取一个
如果这个字符在已经取得的N-1个字符中没有出现
就调用下一次递归，即调用自己，只不过参数N变为N+1，即下次将取第N+1个字符（相对于当前来说），而输入的S参数也变为已经加入第N个字符的新字符串。

程序主体开始
答案总数初值为0
调用递归过程，输入值1表示要找第1个字符，’’表示已经找到的0个字符
上述程序的运行过程如下：
过程步骤 N的值 S的值
1.以参数1，’’输入递归过程DG，开始递归第一层 1 ‘’
2.取到第一个字符，’A’ 1 ‘A’
3.以参数(N+1,S+I), 即(2,’A’)调用第二层递归,即第一层过程尚未结束, 就调用第二层递归过程, 此时,第一层过程保留在内存中,程序执行到循环语句的’A’, 程序返回此过程中时,将继续执行此循环语句,而此时此循环已被挂起 2 ‘A’
4.进入第二层递归,取到第二个字符,此时’A’已不能取, 只能取’B’ 2 ‘AB’
3.以参数(N+1,S+I), 即(3,’AB’)调用第三层递归,即第一层及第二层过程尚未结束, 就调用第三层递归过程, 此时,第一,二层过程保留在内存中, 3 ‘AB’
5.进入第三层递归,取到第三个字符,此时’A’和’B’已不能取, 只能取’C’ 3 ‘ABC’
…………
接上. 以参数(N+1,S+I), 即(5,’ABCD’)调用第五层递归,即第一层到第四层过程尚未结束, 就调用第五层递归过程, 此时,第一至四层过程留在内存中, 5 ‘ABCD’
接上. 进入第五层递归,取到第五个字符,此时只能取’E’ 5 ‘ABCDE’
接上. 以参数(N+1,S+I),即(6,’ABCDE’)调用第六层递归,即第一层到第五层过程尚未结束, 就调用第六层递归过程, 此时,第一至四层过程留在内存中 6 ‘ABCDE’
接上. 进入第六层递归过程, 此时N=6条件满足,将不执行下一层递归,而是打印出第一个答案’ABCDE’, 并结束此次递归过程, 这意味着,程序将回到调用第六层递归的第五层递归的循环语句中 6 ‘ABCDE’

④ 求PASCAL的算法

学习计算机语言不是学习的最终目的。语言是描述的工具，如何灵活地运用语言工具，设计和编写能解决实际问题的程序，算法是程序设计的基础。算法的作用是什么呢？着名数学家高斯（GAUSS）从小就勤于思索。1785年，刚上小学二年级的小高斯，对老师出的计算题S=1+2+3+…+99+100，第一个举手报告S的结果是5050。班上的同学都采用依次逐个相加的“算法”，要相加99次;而小高斯则采用首尾归并，得出S=（1+100）*50的“算法”，只需加一次和乘一次，大大提高了效率。可见，算法在处理问题中的重要性。学习计算机编程，离不开基本算法。刚开始学习程序设计时，就应注重学习基本算法。
第一节 递推与递归算法

递推和递归是编程中常用的基本算法。在前面的解题中已经用到了这两种方法，下面对这两种算法基本应用进行详细研究讨论。

一、递推
递推算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。

[例1] 植树节那天，有五位参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10棵。到底第一位同学植了多少棵树？
解：设第一位同学植树的棵数为a1，欲求a1，需从第五位同学植树的棵数a5入手，根据“多两棵”这个规律，按照一定顺序逐步进行推算：
①a5=10;
②a4=a5+2=12;
③a3=a4+2=14;
④a2=a3+2=16;
⑤a1=a2+2=18;
Pascal程序：
Program Exam1;
Var i, a: byte;
begin
a:=10; {以第五位同学的棵数为递推的起始值}
for i :=1 to 4 do {还有4人，递推察升计算4次}
a:= a+2; {递推运算规律}
writeln(’The Num is’, a);
readln
end.
本程序的递推运算可用如下图示描述：

递推算法以初始{起点}值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运敏凳动，用循环可以实现。递推的本质是按规律逐次推出（计算）下一步的结果。
二、递归
递归算法是把处理问题的方法定义成与原问题处理方法相同的过程，在处理问题的过程中又调用自身定义的函数或过程。
仍用上例的计算植树棵数问题来说明递归算法：
解：把原问题求第一位同学在植树棵数a1，转化为a1=a2+2;即求a2；而求a2又转化为a2=a3+2; a3=a4+2; a4=a5+2;逐层转化为求a2,a3,a4,a5且都采用与求a1相同的方法；最后的a5为已知,则用a5=10返回到上一层并代入计算出a4；又用a4的值代入上一层去求a3;...,如此,直到求出a1。
因此：

其中求a x+1 又采用求ax 的方法。所以:
①定义一个处理问题的过程Num(x)：如果X < 5就递归调用过程Num(x+1);
②当递归调用到达一定条件(X=5)，就直接执行a :=10，再执桥没旅行后继语句，遇End返回到调用本过程的地方，将带回的计算结果(值)参与此处的后继语句进行运算（a:=a+2）;
③最后返回到开头的原问题，此时所得到的运算结果就是原问题Num(1)的答案。
Pascal程序：
Program Exam1_1;
Var a: byte;
Procere Num(x: integer);{过程Num(x)求x的棵数｝
begin
if x=5 then a:=10
else begin
Num(x+1); ｛递归调用过程Num(x+1)｝
a:=a+2 {求(x+1)的棵数｝
end
end;
begin
Num(1); ｛主程序调用Num(1)求第1个人的棵数｝
writeln(’The Num is ’, a);
readln
end.
程序中的递归过程图解如下：

参照图示，递归方法说明如下：
①调用原问题的处理过程时，调用程序应给出具体的过程形参值（数据）;
②在处理子问题中，如果又调用原问题的处理过程，但形参值应是不断改变的量(表达式）;
③每递归调用一次自身过程，系统就打开一“层”与自身相同的程序系列;
④由于调用参数不断改变，将使条件满足（达到一定边界），此时就是最后一“层”，不需再调用（打开新层），而是往下执行后继语句，给出边界值，遇到本过程的END，就返回到上“层”调用此过程的地方并继续往下执行;
⑤整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。
[例2] 用递归算法求X n 。
解：把X n 分解成: X 0 = 1 ( n =0 )
X 1 = X * X 0 ( n =1 )
X 2 = X * X 1 ( n >1 )
X 3 = X * X 2 ( n >1 )
…… ( n >1 )
X n = X * X n-1 ( n >1 )
因此将X n 转化为：

其中求X n -1 又用求X n 的方法进行求解。
①定义过程xn(x,n: integer)求X n ;如果n >1则递归调用xn (x, n-1) 求X n—1 ;
②当递归调用到达n=0，就执行t t :=1, 然后执行本“层”的后继语句;
③遇到过程的END就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt:=tt*x;
④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序，输出tt的值。
Pascal程序：
Program Exam2;
Var tt, a, b: integer;
Procere xn(x, n: integer); ｛过程xn(x, n)求xn ｝
begin if n=0 then tt:=1
else begin
xn(x, n-1); ｛递归调用过xn(x,n-1)求x n-1｝
tt:=tt*x
end;
end;
begin
write(’input x, n:’); readln(a,b); ｛输入a, b｝
xn(a,b); ｛主程序调用过程xn(a, b)求a b｝
writeln(a, ’^’, b, ’=‘, tt);
readln
end.
递归算法，常常是把解决原问题按顺序逐次调用同一“子程序”(过程)去处理，最后一次调用得到已知数据，执行完该次调用过程的处理，将结果带回，按“先进后出”原则，依次计算返回。
如果处理问题的结果只需返回一个确定的计算值，可定义成递归函数。

[例3]用递归函数求x!
解：根据数学中的定义把求x! 定义为求x*(x-1)! ,其中求(x-1)! 仍采用求x! 的方法，需要定义一个求a！的过程或函数，逐级调用此过程或函数，即：
(x-1)!= (x-1)*(x-2)! ;
(x-2)!= (x-2)*(x-3)! ;
……
直到x=0时给出0!=1，才开始逐级返回并计算各值。
①定义递归函数：fac(a: integer): integer;
如果a=0，则fac:=1;
如果a>0，则调用函数fac:=fac(a-1)*a;
②返回主程序，打印fac(x)的结果。
Pascal程序：
Program Exam3;
Var x: integer;
function fac(a: integer): integer; ｛函数fac(a) 求a !｝
begin
if a=0 then fac:=1
else fac:=fac(a-1)*a ｛函数fac(a-1)递归求(a-1) !｝
end;
begin
write(’input x’); readln(x);
writeln(x, ’!=’, fac(x)); ｛主程序调用fac(x) 求x !｝
readln
end.
递归算法表现在处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。

[例4]用递归算求自然数A，B的最大公约数。
解：求最大公约数的方法有许多种，若用欧几里德发明的辗转相除方法如下：
①定义求X除以Y的余数的过程;
②如果余数不为0，则让X=Y，Y=余数，重复步骤①，即调用过程;
③如果余数为0，则终止调用过程;
④输出此时的Y值。
Pascal程序：
Program Exam4;
Var a,b,d: integer;
Procere Gdd(x, y: nteger);{过程}
begin
if x mod y =0 then d :=y
else Gdd(y, x mod y) {递归调用过程}
end;
begin
write(’input a, b=’); readln(a, b);
Gdd(a, b);
writeln(’(’, a, ’,’, b, ’)=’, d );
readln
end.
简单地说，递归算法的本质就是自己调用自己，用调用自己的方法去处理问题，可使解决问题变得简洁明了。按正常情况有几次调用，就有几次返回。但有些程序可以只进行递归处理，不一定要返回时才进行所需要的处理。

[例5] 移梵塔。有三根柱A，B，C在柱A上有N块盘片，所有盘片都是大的在下面，小片能放在大片上面。现要将A上的N块片移到C柱上，每次只能移动一片，而且在同一根柱子上必须保持上面的盘片比下面的盘片小，请输出移动方法。
解：先考虑简单情形。
如果N=3，则具体移动步骤为：

假设把第3步，第4步，第6步抽出来就相当于N=2的情况（把上面2片捆在一起，视为一片）：

所以可按“N=2”的移动步骤设计：
①如果N=0，则退出，即结束程序;否则继续往下执行;
②用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程sub(n-1, a,b,c);
③将A柱上剩下的一片直接移到C柱上;
④用A柱作为协助过渡，将B柱上的（N-1）移到C柱上，调用过程sub(n-1,b,c,a)。

Pascal程序：
Program Exam65;
Var x,y,z : char;
N, k : integer;
Procere sub(n: integer; a, c , b: char);
begin
if n=0 then exit;
sub(n-1, a,b,c);
inc(k);
writeln(k, ’: from’, a, ’--＞’, c);
sub(n-1,b,c,a);
end;
begin
write(’n=’; readln(n);
k:=0;
x:=’A’; y:=’B’; Z:=’C’;
sub(n,x,z,y);
readln
end.
程序定义了把n片从A柱移到C柱的过程sub(n,a,c,b)，这个过程把移动分为以下三步来进行：
①先调用过程sub(n-1, a, b, c)，把(n-1)片从A柱移到B柱, C柱作为过渡柱;
②直接执行 writeln(a, ’--＞’, c），把A柱上剩下的一片直接移到C柱上，;
③调用sub(n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。
对于B柱上的(n-1)片如何移到，仍然调用上述的三步。只是把(n-1)当成了n，每调用一次，要移到目标柱上的片数N就减少了一片，直至减少到n=0时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。

习题6.1
1.过沙漠。希望一辆吉普车以最少的耗油跨越1000 km的沙漠。已知该车总装油量500升，耗油率为1升/ km，必须利用吉普车自己沿途建立临时加油站，逐步前进。问一共要多少油才能以最少的耗油越过沙漠？
2.楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？
提示：如N级楼梯有S(N)种不同走法，则有：
S(N)=S(N-2)+S(N-1)
3.阿克曼(Ackmann)函数A(x,y)中，x,y定义域是非负整数，函数值定义为：
A(x,y)=y+1 (x = 0)
A(x,0)=A(x-1,1) (x > 0, y = 0)
A(x,y)=A(x-1, A(x, y-1)) (x, y > 0)
设计一个递归程序。
4.某人写了N封信和N个信封，结果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。可用下面公式：
Dn=(n—1) ( D n—1+D n—2)
写出递归程序。

第二节 回溯算法

在一些问题求解进程中，有时发现所选用的试探性操作不是最佳选择，需退回一步，另选一种操作进行试探，这就是回溯算法。

例[6.6] 中国象棋半张棋盘如下，马自左下角往右上角跳。现规定只许往右跳，不许往左跳。比如下图所示为一种跳行路线。编程输出所有的跳行路线，打印格式如下：
<1> (0,0)—(1,2)—(3,3)—(4,1)—(5,3)—(7,2)—(8,4)

解：按象棋规则，马往右跳行的方向如下表和图所示：

水平方向用x表示; 垂直方向用y表示。右上角点为x=8, y=4, 记为(8, 4) ; 用数组tt存放x方向能成行到达的点坐标;用数组t存放y方向能成行到达的点坐标;
①以(tt(K), t(k))为起点，按顺序用四个方向试探，找到下一个可行的点(x1, y1);
②判断找到的点是否合理 (不出界)，若合理，就存入tt和t中;如果到达目的就打印，否则重复第⑴步骤;
③如果不合理，则换一个方向试探，如果四个方向都已试过，就退回一步(回溯)，用未试过的方向继续试探。重复步骤⑴;
④如果已退回到原点，则程序结束。
Pascal程序：
Program Exam66;
Const xx: array[1..4] of 1..2 =(1,2,2,1);
yy: array[1..4] of -2..2=(2,1,-1,-2);
Var p: integer;
t, tt : array[0..10] of integer;
procere Prn(k: integer);
Var i: integer;
Begin
inc(p); write(‘< ‘, p: 2, ’ > ‘, ’ ‘:4, ’0,0’);
for i:=1 to k do
write(‘— ( ‘, tt[ I ], ’ , ’, t[ I ], ’)’ );
writeln
End;
Procere Sub(k: integer);
Var x1, y1, i: integer;
Begin
for I:=1 to 4 do
Begin
x1:=tt[k-1]+xx[ i ]; y1:=t[k-1]+yy[ i ];
if not( (x1 > 8) or (y1 < 0) or (y1 > 4) ) then
Begin
tt[k]:=x1; t[k]=y1;
if (y1=4) and (x1=8) then prn(k);
sub(k+1);
end;
end;
end;
Begin
p:=0; tt[0]:=0; t[0]:=0;
sub(1);
writeln( ‘ From 0,0 to 8,4 All of the ways are ’, p);
readln
end.

例[6.7] 输出自然数1到n所有不重复的排列，即n的全排列。
解：①在1～n间选择一个数，只要这个数不重复，就选中放入a数组中;
②如果这个数巳被选中，就在d数组中作一个被选中的标记 (将数组元素置1 );
③如果所选中的数已被占用（作了标记），就另选一个数进行试探;
④如果未作标记的数都已试探完毕，那就取消最后那个数的标记，退回一步，并取消这一步的选数标记，另换下一个数试探，转步骤①;
⑤如果已退回到0，说明已试探全部数据，结束。
Pascal程序：
Program Exam67;
Var p,n: integer;
a,d: array[1..500] of integer;
Procere prn (t : integer);
Var i: integer;
Begin
write(‘ < ‘, p:3, ’ > ‘, ’ ‘:10);
for I:=1 to t do
write(a[ I ]:4);
writeln;
end;
Procere pp(k: integer);
var x: integer;
begin
for x:=1 to n do
begin
a[k]:=x; d[x]:=1;
if k < n then pp(k+1)
else
begin
p:=p+1;
prn(k);
end;
end;
end;
Begin
write(‘Input n=‘); readln(n);
for p:=1 to n do d[p]=0;
p:=0;
pp(1);
writeln(‘All of the ways are ‘, p:6);
End.

例[6.8] 设有一个连接n个地点①—⑥的道路网，找出从起点①出发到过终点⑥的一切路径，要求在每条路径上任一地点最多只能通过一次。

解：从①出发，下一点可到达②或③，可以分支。具体步骤为：
⑴假定从起点出发数起第k个点Path[k]，如果该点是终点n就打印一条路径;
⑵如果不是终点n，且前方点是未曾走过的点，则走到前方点，定(k+1)点为到达路径，转步骤⑴;
(3)如果前方点已走过，就选另一分支点;
(4)如果前方点已选完，就回溯一步，选另一分支点为出发点;
(5)如果已回溯到起点，则结束。
为了表示各点的连通关系，建立如下的关系矩阵：

第一行表示与①相通点有②③，0是结束 标志;以后各行依此类推。

集合b是为了检查不重复点。

Program Exam68;
const n=6;
roadnet: array[1..n, 1..n] of 0..n=( (2,3,0,0,0,0),
(1,3,4,0,0,0),
(1,2,4,5,0,0),
(2,3,5,6,0,0),
(3,4,6,0,0,0),
(4,5,0,0,0,0) );
var b: set of 1..n;
path: array[1..n] of 1..n;
p: byte;
procere prn(k: byte);
var i: byte;
begin
inc(p); write(’<’, p:2, ’>’, ’ ’:4);
write (path[1]:2);
for I:=2 to k do
write (’--’, path[ i ]:2);
writeln
end;
procere try(k: byte);
var j: byte;
begin
1 2 3 4 5
6 X 8 9 10
11 12 13 14 15
j:=1;
repeat
path[k]:=roadnet [path [k-1], j ];
if not (path [k] in b) then
begin b:=b+[path [k] ];
if path [k]=n then prn (k)
else try(k+1);
b:=b-[path [k] ];
end;
inc(j);
until roadnet [path [k-1], j ]=0
end;
begin
b:=[1]; p=0; path[1]:=1;
try(2);
readln
end.

习题[6.2]
1. 有A,B,C,D,E五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本。事先让每个人将自己喜爱的书填写在下表中。希望你设计一个程序，打印分书的所有可能方案，当然是让每个人都能满意。
A B C D E
张 Y Y
王 Y Y Y
刘 Y Y
赵 Y

钱 Y Y

2. 右下图所示的是空心框架,它是由六个单位正方体组成,问:从框架左下外顶点走到右上内顶点共有多少条最短路线?

3.城市的街道示意图如右:问从甲地去到乙地可以有多少条最短路线?

4.有M×N张(M行, N列)邮票连在一起,
但其中第X张被一个调皮的小朋友控掉了。上图是3×5的邮票的形状和编号。从这些邮票中撕出四张连在一起的邮票,问共有多少种这样四张一组的邮票?注:因为给邮票编了序号,所以1234和2345应该看作是不同的两组。
5.有分数12 ，13 ，14 ，15 ，16 ，18 ，110 ，112 ，115 ， 求将其中若干个相加的和恰好为1的组成方案，并打印成等式。例如：
<1> 12 +13 +16 = 1
<2> ...
6.八皇后问题。在8*8的国际象棋盘上摆上8个皇后。要求每行，每列，各对角线上的皇后都不能互相攻击，给出所可能的摆法。