pascal遞歸演算法

① PASCAL 遞歸演算法的非遞歸實現問題 高分！

手寫一個stack,
然後每當需要recursive
call的時候push
stack,
stack非空的時候pop並處理.
相當於模擬一個call
stack.
即:
procere
make1_non_rec(tx,ty:integer);
var
i,x,y:integer;
begin
stack.clear();
stack.push(tx,ty);
while(!stack.empty())
begin
x:=stack.top().x;
y:=stack.pop().y;
g[x,y]:=p;
for
i:=1
to
8
do
if
(g[x+u[i],y+v[i]]=0)
and
(a[x+u[i],y+v[i]]=a[x,y])
then
stack.push(x+u[i],y+v[i]);
end
end;

② Pascal演算法之回溯及遞推詳細介紹、

遞歸 遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫程序能是程序變得簡潔和清晰.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;varn:integer;function fac(n:integer):real;beginif n=0 then fac:=1 else fac:=n*fac(n-1)end;beginwrite('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;beginif x=1 then f:=1 elseif x=2 then f:=2 else f:=f(x-1)+f(x-2);end;beginwrite('n=');read(n);writeln('f(',n,')=',f(n))end.2.2 如何設計遞歸演算法
1.確定遞歸公式2.確定邊界(終了)條件練習:用遞歸的方法完成下列問題1.求數組中的最大數2.1+2+3+...+n3.求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;varn:integer;procere move(n,a,b,c:integer);beginif n=1 then writeln(a,'--->',c)else beginmove(n-1,a,c,b);writeln(a,'--->',c);move(n-1,b,a,c);end;end;beginwrite('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 遞歸的方法做問題

我直接寫出最重要的把，只寫子程序好了。
3：
procere f（x，s:longint);
begin
if x=0 then begin writeln(s);exit;end;
f(x div 10,s*10+x mod 10);
end;
主程序中： f(x,0);(x是要顛倒的數）；

6：
procere f（x，s，t:longint);
begin
if t=0 then begin writeln(s);exit;end;(我直接用顛倒數字，為了防止最後的零不輸出，我就設定了位數）
f(x div 10,s*10+x mod 10,t-1);
end;
procere f1（x，s:longint);
var
t:longint;
begin
if x=0 then begin f(s,0,t);end;
t:=t+1;
f(x div m,s*10+(x mod m)）;
end;

主程序中：readln（m）；（進制）；f1（x，0）；（x是要換進制的數）；
如果用數組的話可以更好一點，我這樣直接

④ 【Pascal遞歸函數】計算ackerman函數值；

兩個問題：
1、Integer太小了，數據早就爆了；
2、棧的調用過頭了，「exitcode = 201」的意思就是棧溢出。

事實上，阿克曼函數的值是極大的。
Ackermann(0,n)=n+1
Ackermann(1,n)=n+2
Ackermann(2,n)=2*n+3
Ackermann(3,n)=2^(n+3)-3
Ackermann(4,n)=2^2^2^……^2-3，乘冪中共有n+3個2。
當m≥4，Ackermann函數的增長快得驚人。Ackermann(4,0)=13，Ackermann(4,1)=65533，Ackermann(4,2)=2^65536-3有19729位，而Ackermann(4,3)則即使是位數也不易估計。Ackermann(5,0)=65533，Ackermann(5,1)=Ackermann(4,65533)……

針對於小數據，你的程序沒問題。

⑤ PASCAL 遞歸演算法的非遞歸實現問題 高分！

手寫一個stack, 然後每當需要recursive call的時候push stack, stack非空的時候pop並處理. 相當於模擬一個call stack. 即:

procere make1_non_rec(tx,ty:integer);
var
i,x,y:integer;
begin
stack.clear();
stack.push(tx,ty);
while(!stack.empty())
begin
x:=stack.top().x;
y:=stack.pop().y;
g[x,y]:=p;
for i:=1 to 8 do
if (g[x+u[i],y+v[i]]=0) and (a[x+u[i],y+v[i]]=a[x,y]) then
stack.push(x+u[i],y+v[i]);
end
end;

⑥ 10道pascal的遞歸習題，簡單一點啊

1. 有5個人坐在一起，問第5個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第3個人，又說比第2個人大2歲。問第2個人，說比第1個人大2歲。最後問第1個人，他說是10歲。請問第5個人多大。顯然，這是一個遞歸問題。要求第5個人的年齡，就必須先知道第4個人的年齡，而第4個人的年齡也不知道，要求第4個人的年齡必須先知道第3個人的年齡，而第3個人的年齡又取決於第2個人的年齡，第2個人的年齡取決於第1個人的年齡。而且每一個人的年齡都比其前1個人的年齡大2。
2.用遞歸方法求n！
3.用遞歸方法求斐波那契數列
4.有1*n的一個長方形，用一個1＊1、1＊2、1＊3的骨牌鋪滿方格。例如當n=3時為1＊3的方格。此時用1＊1，1＊2，1＊3的骨牌鋪滿方格，共有四種鋪法。圖4.4.3列出了四種鋪法。
5.設s是一個具有n個元素的集合s={a1,a2,…an},現將s集合劃分成k個滿足下列條件的子集合s1,s2，s3。。。。；
1、si<>空；
2、si∩sj=空；
3、s1∪s2∪s3…. ∪sn=s (1<=i,j<=k,i<>j)
則稱s1,s2…sn是集合s的一個劃分，它相當於把集合s中的n個元素放入k個無標號的盒子中，使得沒有一個盒子為空，試確定n個元素的集合放入k個無標號盒的劃分數s(n,k)
6.設有一個背包，可以放入的重量為s。現有n件物品，重量分別為t1 , t2 , t3 … ti … tn ，ti (1≤ i≤n)，均為正整數。從n件物品中挑選若干件，使得放入背包的重量之和正好為s
【輸入樣例】 【輸出樣例】
the number of object:5 number:1 weight:1
total weight=10 number:3 weight: 2
1 6 2 7 5 number:4 weight:7
7.輸出n個元素的無重復的全排列。N個元素有n！種不同排列
8.任何一個正整數都可以用2的冪次方表示.例如：137=2^7+2^3+2^0。同時約定次方用括弧來表示，即a^b可表示為a(b)。由此可知，137可表示為：2(7)+2(3)+2(0)，進一步：7=2^2+2+2^0 (2^1用2表示)；3=2+2^0；所以最後137可表示為：2(2(2)+2+2(0))+2(2+2(0))+2(0)。又如：1315=2^10+2^8+2^5+2+1；所以1315最後可表示：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
輸入：正整數(n≤20000)
輸出：符合約定的n的0，2表示(在表示中不能有空格)
9.。一個正整數的數字的乘積N的定義是：這個整數中非零數字的乘積。例如，整數999的數字乘積為9*9*9，即729。729的數字乘積為7*2*9，即126。126的數字乘積為1*2*6，即12。12的數字乘積為1*2，即2。一個正整數的數字乘積根N是這樣得到的：反復取該整數的數字乘積，直到得到一位數字為止。例如，在上面的例子中數字的乘積根是2。
編寫一個程序，輸入一個正整數（長度不超過200位數字），輸出計算其數字乘積根的每一步結果。
10.輸入N個字元，然後以倒序輸出（用遞歸實現）

⑦ pascal語言：用」遞歸演算法」求2個自然數的最大公約數與最小公倍數

{
不是整數的2b數據別給啊

}

var
a,b:longint;
function gcd(a,b:longint):longint; //（遞歸）最大公約數
begin
if b=0 then gcd:=a
else gcd:=gcd(b,a mod b);
end;
begin
readln(a,b);
writeln('GCD=',gcd(a,b),' ACM=',a*b div gcd(a,b)); //a*b div gcd(a,b)為最小公倍數
end.

⑧ PASCAL 2的冪次方 遞歸演算法

不要求高精的話2的冪用shl（左移）運算最快

你是不是想要用快速冪
function f(x:longint):qword;
var
a:qword;
begin
if x=1 then f:=2 else
begin
a:=f(x div 2);
f:=a*a*(x mod 2+1)
end;
end;

⑨ 哪位高手給我講一下pascal遞歸與回朔

一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。因此，在考慮使用遞歸演算法編寫程序時，應滿足兩點：1）該問題能夠被遞歸形式描述；2）存在遞歸結束的邊界條件。
遞歸的能力在於用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。

[例2] 給出一棵二叉樹的中序與後序排列。求出它的先序排列。
[分析] 通過對比二叉樹的中序與後序排列，我們可以找出根節點及左右子樹。同樣的，有可以通過對比左子樹的中序與後序排列，找出左子樹的根節點……可見，該問題能夠被遞歸描述。當找到最後一個根節點時，遞歸無法再進行下去，這就是遞歸結束的邊界條件。由此可見，遞歸演算法中常常隱含了分治思想。程序如下：
program chu01_3;
var z,h: string;
procere find(a,b:string);
var
s,l : integer;
begin
l:=length(b);
if l=1 then Write(b) {邊界條件及遞歸返回段}
else
begin {遞歸前進段}
Write(b[l]);
s:=pos(b[l],a);
if s-1>0 then find((a,1,s-1),(b,1,s-1)); {遞歸左子樹}
if l-s>0 then find((a,s+1,l-s),(b,s,l-s)); {遞歸右子樹}
end;
end;
begin
Readln(z);
Readln(h);
Find(z,h);
Readln;
end.
[遞歸的應用]

1.經典遞歸
例如hanoi塔問題：經典的遞歸，原問題包含子問題。有些問題或者數據結構本來就是遞歸描述的，用遞歸做很自然。

2.遞歸與遞推
利用遞歸的思想建立遞推關系，如由兔子生崽而來的fibonacci數列。但遞推由於沒有返回段，因此更為簡單，有時可以直接用循環實現。

3.分治
不少分治方法是源於遞歸思想，或是遞歸分解+合並處理。

4.回溯
規模較小的問題用回溯解決比較自然。注意遞歸前後要保證現場的保存和恢復，即正確的轉化問題。

5.動態規劃
動態規劃的子問題重疊性質與遞歸有某種相似之處。遞歸+動態修改查表是一種不錯的建立動態規劃模型的方法。

6.其他
其他么，就是不好歸類。例如表達式處理，排列組合等。附帶說一下，用遞歸來處理列印方案的問題還是很方便的。

[例3] 求把一個整數n無序劃分成k份互不相同的正整數之和的方法總數。
[分析] 這是一道動態規劃題，動態方程如下：
f[i-1,j]+f[i,j-i]+1 （(j mod i=0) and (j div i=1)）
f[i,j]:= f[i-1,j] (i>=j)
f[i-1,j]+f[i,j-i] （else）
s:=f(k,n-k)
本題可以用循環來實現遞推,也可以考慮用遞歸求解。主過程如下：

方案一：
Procere work(I,j:longint; var s:longint);
Var t:longint;
Begin
If (i=1) or (j=1) then s:=1
Else if (i=0) or (j=0) then s:=0
Else begin
if (j mod i=0) and (j div i=1) then
begin
work(i-1,j,s);
t:=s;
work(i,j-1,s);
s:=s+t+1;
end
else if (i>=j) then
work(i-1,j)
else begin
work(i-1,j,s);
t:=s;
work(I,j-1,s);
s:=s+t;
end;
End;

方案二：procere search(v,w,last:byte);
var i:byte;
begin
if w=0 then inc(count)
else
if w=1 then
if v>=last then search(0,0,0) else
else for i:=last to v-1 do search(v-i,w-1,i);
end;

可以看出，方案一的程序較為冗長，消耗棧空間較大；而方案二較為簡潔明了，所用的棧空間也較小，效率較高。因此，使用遞歸演算法也有一個優化問題。演算法的簡潔與否直接制約了程序的可行性和效率。

[總結]
遞歸使一些復雜的問題處理起來簡單明了，尤其在學習演算法設計、數據結構時更能體會到這一點。但是，遞歸在每一次執行時都要為局部變數、返回地址分配棧空間，這就降低了運行效率，也限制了遞歸的深度。因此，在必要的時候可以只使用遞歸的思想來求解，而程序則轉用非遞歸的方式書寫。

回溯法也稱為試探法，該方法放棄關於問題規模大小的限制，並將問題的方案按某種順序逐一枚舉和試驗。發現當前方案不可能有解時，就選擇下一個方案，倘若當前方案不滿足問題的要求時，繼續擴大當前方案的規模，並繼續試探。如果當前方案滿足所有要求時，該方案就是問題的一個解。在回溯中，放棄當前方案，尋找下一介方案的過程稱為回溯，
在一般情況下需要用計算機解決的問題有兩種類型：
1、 以用精確的數學公式或明確的演算法語言來描述的問題。如圓周率的計算、多位數的階乘等。
2、 完成一件事情的過程中，要經過若干個步驟，而每一個步驟都有若干種可能的分支，為了圓滿地完成任務，必須遵守一些規則，但這些規則又無法精確地用數學公式或語言來描述的。
對於第二類問題，一般採用窮舉或回溯的方法來解決。窮舉法是將問題的所有可能性都一一例舉出來，而回溯是窮舉演算法的一種控制策略，是把有可能圓滿地完成任務的解法進行例舉，是一種組織得井井有條的，能避免不必要的窮舉搜索演算法。它的基本思想是：在搜索過程中，由於方案在當前狀態下求解不到，需返回搜索進程中的上一環節，並重新尋求解答。
如何學會用回溯的方法解題，先來看下題用窮舉法是如何解題的：我們為了便於對問題進一步分析，以下題為例（皇後問題）：
問題描述：在一個4×4的棋盤上放置4個皇後，並使她們不能互相攻擊，既在同一個行，同一個列上，同一個對角線不能有多於一個以上的皇後,問有多少種放置的方法。
窮舉法：
列出4個皇後在棋盤上的所有可能性，然後一一判斷是否互相攻擊，程序如下
回溯法：
在尋找解答時需要一個環節一個環節地考慮，當某一個環節的各個方案都已試驗過但仍未找到合適的解，得退到上一個環節，對未有試探過的方案繼續試探，程序如下：
program qi16;
var
i,t,an:word;
co,bo:boolean;
a:array[1..4] of byte;
const
n=4;ct=4;
begin
t:=0;an:=0;
repeat
inc(t); a[t]:=0;
repeat
inc(a[t]);
bo:=false;
co:=false;
if a[t]>ct then bo:=true
else begin
co:=true;
for i:=t-1 downto 1 do {與已放了皇後的行逐行比較}
if (t-i=abs(a[t]-a[i])) or (a[t]=a[i]) then
co:=false;
end;
if bo then begin dec(t); {如果各個方案都已試驗過但仍未找到合適的解則回溯}
if t=0 then co:=true;
end;
until co;
if t>=n then
begin {輸出結果}
inc(an);
write('#',an,' ':10);
for i:=1 to n do write(chr(64+i),':',a[i],' ');
writeln
end
until t=0;
if an=0 then writeln('No Answer');
end.

⑩ 在PASCAL語言中，該如何理解遞歸這一過程

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)