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個皇後。要求每行，每列，各對角線上的皇後都不能互相攻擊，給出所可能的擺法。