1. 遞推的遞推演算法
【例1】
植樹節那天,有五位同學參加了植樹活動,他們完成植樹的棵樹都不相同。問第一位同學植了多少棵時,他指著旁邊的第二位同學說比他多植了兩棵;追問第二位同學,他又說比第三位同學多植了兩棵;... 如此,都說比另一位同學多植兩棵。最後問到第五位同學時,他說自己植了10棵。到底第一位同學植了多少棵樹?
分析:設第一位同學植樹的棵樹為a1,欲求a1,需從第五位同學植樹的棵數a5入手,根據「多兩棵」這個規律,按照一定順序逐步進行推算:
(1) a5=10;
(2) a4=a5+2=12;
(3) a3=a4+2=14;
(4) a2=a3+2=16;
(5) a1=a2+2=18;
Pascal程序:
Program Examl;
Var i,a:byte;
begin
a:=10;
for i:= 1 to 4 do
a:=a+2;
writeln('The Num is' ,a);
readln;
end.
本程序的遞推運算可用下圖示表示:
初始值a:=10 ----- i=1,a=a+2(12) ----- i=2,a=a+2(14) ------ i=3,a=a+2(16) ----- i=4,a=a+2(18) ---- 輸出a值
例2:
十本不同的書放在書架上。現重新擺放,使每本書都不在原來放的位置。有幾種擺法?
當n個編號元素放在n個編號位置,元素編號與位置編號各不對應的方法數用M(n)表示,那麼M(n-1)就表示n-1個編號元素放在n-1個編號位置,各不對應的方法數,其它類推.
第一步,把第n個元素放在一個位置,比如位置k,一共有n-1種方法;
第二步,放編號為k的元素,這時有兩種情況.1,把它放到位置n,那麼,對於剩下的n-2個元素,就有M(n-2)種方法;2,不把它放到位置n,這時,對於這n-1個元素,有M(n-1)種方法;
綜上得到
M(n)=(n-1)[M(n-2)+M(n-1)]
遞推演算法以初始(起點)值為基礎,用相同的運算規律,逐次重復運算,直至運算結束。這種從「起點」重復相同的方法直至到達一定「邊界」,猶如單向運動,用循環可以實現。遞推的本質是按規律逐次推出(計算)先一步的結果。
2. c語言(高分)
1.相對於遞歸演算法,遞推演算法免除了數據進出棧的過程,也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.
比如階乘函數:f(n)=n*f(n-1)
在f(3)的運算過程中,遞歸的數據流動過程如下:
f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而遞推如下:
f(0)-->f(1)-->f(2)-->f(3)
由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意.
2.所謂排序,就是使一串記錄,按照其中的某個或某些關鍵字的大小,遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為:
計算的復雜度(最差、平均、和最好表現),依據串列(list)的大小(n)。一般而言,好的表現是O。(n log n),且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量(以及其他電腦資源的使用)
穩定度:穩定排序演算法會依照相等的關鍵(換言之就是值)維持紀錄的相對次序。也就是一個排序演算法是穩定的,就是當有兩個有相等關鍵的紀錄R和S,且在原本的串列中R出現在S之前,在排序過的串列中R也將會是在S之前。
一般的方法:插入、交換、選擇、合並等等。交換排序包含冒泡排序(bubble sort)和快速排序(quicksort)。選擇排序包含shaker排序和堆排序(heapsort)。
當相等的元素是無法分辨的,比如像是整數,穩定度並不是一個問題。然而,假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下,有可能產生兩種不同的結果,一個是依照相等的鍵值維持相對的次序,而另外一個則沒有:
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序,但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較,如此在其他方面相同鍵值的兩個物件間之比較,就會被決定使用在原先資料次序中的條目,當作一個同分決賽。然而,要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中,n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序(bubble sort) — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 (insertion sort)— O(n2)
桶排序 (bucket sort)— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 (merge sort)— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 (Binary tree sort) — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 (radix sort)— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 (selection sort)— O(n2)
希爾排序 (shell sort)— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 (heapsort)— O(n log n)
Smoothsort — O(n log n)
快速排序 (quicksort)— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列(longest increasing subsequence)
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多,對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序,他們對空間的要求不高,但是時間效率卻不穩定;而後面三種排序相對於簡單排序對空間的要求稍高一點,但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的:
首先新建一個空列表,用於保存已排序的有序數列(我們稱之為"有序列表")。
從原數列中取出一個數,將其插入"有序列表"中,使其仍舊保持有序狀態。
重復2號步驟,直至原數列為空。
插入排序的平均時間復雜度為平方級的,效率不高,但是容易實現。它藉助了"逐步擴大成果"的思想,使有序列表的長度逐漸增加,直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的:
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字,逐個檢查:若某一位上的數字大於他的下一位,則將它與它的下一位交換。
重復2號步驟,直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同,也是平方級的,但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的:
設數組內存放了n個待排數字,數組下標從1開始,到n結束。
i=1
從數組的第i個元素開始到第n個元素,尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n-1演算法結束,否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始,我們要接觸高效排序演算法了。實踐證明,快速排序是所有排序演算法中最高效的一種。它採用了分治的思想:先保證列表的前半部分都小於後半部分,然後分別對前半部分和後半部分排序,這樣整個列表就有序了。這是一種先進的思想,也是它高效的原因。因為在排序演算法中,演算法的高效與否與列表中數字間的比較次數有直接的關系,而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了,大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同,它是這樣的:
首先新建一個空列表,作用與插入排序中的"有序列表"相同。
找到數列中最大的數字,將其加在"有序列表"的末尾,並將其從原數列中刪除。
重復2號步驟,直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高(因為有堆這種數據結構以及它奇妙的特徵,使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度,維護需要logn的時間復雜度),但是實現相對復雜(可以說是這里7種演算法中比較難實現的)。
看起來似乎堆排序與插入排序有些相像,但他們其實是本質不同的演算法。至少,他們的時間復雜度差了一個數量級,一個是平方級的,一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
3.索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是:首先根據給定的索引值K1,在索引表上查找出索引值等於KI的索引項,以確定對應予表在主表中的開始位置和長度,然後再根據給定的關鍵字K2,茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時,若表是順序存儲的有序表,則既可進行順序查找,也可進行二分查找,否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表,數組B是具有inde)dist類型的在主表A 上建立的一個索引表,m為索引表B的實際長度,即所含的索引項的個數,KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中,不僅便於查找單個元素,而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時,只要從索引表中查找出該子表的開始位
置即可。由此開始位置可以依次取出該子表中的每一個元素,所以整個查找過程的時間復雜度為,若不是採用索引存儲,而是採用順序存儲,即使把它組織成有序表而進行二分查找時,索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置,則索引存儲也便於進行插入和刪除運算,因為其運算過程只涉及到索引表和相應的子表,只需要對相應子表中的元素進行比較和移動,與其它任何子表無關,不像順序表那樣需涉及到整個表中的所有元素,即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法,也同查找演算法類似,其過程為:首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表,確定出對應的子表,然後再根據待插入或刪除元素的關鍵字,在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲,就是鏈接存儲,所以對它們做插入或刪除操作都是很簡單的。
4.插入法排序
#define N 10
#include"stdio.h"
main()
{ int i,j,k,t,a[N];
clrscr();
printf("Please input %d numbers:\n",N);
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=1;i<N;i++)
{
for(j=0;j<i;j++)
{if(a[j]>a[i])
{t=a[i];
for(k=i;k>=j;k--)
a[k]=a[k-1];
a[j]=t;
}
}
}
printf("small to big order:\n");
for(i=0;i<N;i++)
printf("%-2d",a[i]);
printf("\n");
getch();
}
3. 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.
4. 一個遞歸演算法必須包括什麼
遞歸演算法包含的兩個部分:
1、由其自身定義的與原始問題類似的更小規模的子問題(只有數據規模不同),它使遞歸過程持續進行,稱為一般條件。
2、所描述問題的最簡單的情況,它是一個能控制遞歸過程結束的條件,稱為基本條件。(遞歸出口)
遞歸的定義:
如果一個對象部分地由它自身組成或按它自己定義,則稱它是遞歸的,所以說遞歸就是函數/過程/子過程在運行過程中直接或間接調用自身而產生的重入現象。
遞歸的基本思想:
就是把一個規模大的問題分為若干個規模較小的子問題求解,而每一個子問題又可以分為幾個規模更小的子問題。基本上,所有的遞歸問題都可以用遞推公式來表示。
最重要的一點就是假設子問題已經解決了,現在要基於已經解決的子問題來解決當前問題;或者說,必須先解決子問題,再基於子問題來解決當前問題或者可以這么理解:遞歸解決的是有依賴順序關系的多個問題。
遞歸的優缺點:
優點:邏輯清楚,結構清晰,可讀性好,代碼簡潔,效率高(拓展:DFS深度優先搜素,前中後序二叉樹遍歷)
缺點:函數調用開銷大,空間復雜度高,有堆棧溢出的風險
5. 什麼是遞推法和遞歸法兩者在思想上有何聯系
1、遞推法:遞推演算法是一種根據遞推關系進行問題求解的方法。通過已知條件,利用特定的遞推關系可以得出中間推論,直至得到問題的最終結果。遞推演算法分為順推法和逆推法兩種。
2、遞歸法:在計算機編程中,一個函數在定義或說明中直接或間接調用自身的編程技巧稱為遞歸。通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算,大大地減少了程序的代碼量。遞歸做為一種演算法在程序設計語言中廣泛應用。
3、兩者的聯系:在問題求解思想上,遞推是從已知條件出發,一步步的遞推出未知項,直到問題的解。從思想上講,遞歸也是遞推的一種,只不過它是對待解問題的遞推,直到把一個復雜的問題遞推為簡單的易解問題。然後再一步步的返回去,從而得到原問題的解。
(5)遞推演算法必須包括擴展閱讀
相對於遞歸演算法,遞推演算法免除了數據進出棧的過程,也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值。
比如階乘函數:f(n)=n*f(n-1)
在f(3)的運算過程中,遞歸的數據流動過程如下: f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而遞推如下: f(0)-->f(1)-->f(2)-->f(3) 由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推。
但是遞歸作為比較基礎的演算法,它的作用不能忽視。所以,在把握這兩種演算法的時候應該特別注意。