Ⅰ 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.