演算法擴展遞歸

『壹』 演算法除了遞歸還有什麼

演算法的分類分為七類，分別是：

1、基本演算法 : 包括枚舉和搜索兩種，分為深度優先搜索，廣度優先搜索，啟發式搜索和遺傳演算法；

2、數據結構的演算法數論；

3、代數演算法；

4、計算幾何的演算法，求凸包；

5、圖論演算法：包括哈夫曼編碼，樹的遍歷，最短路徑演算法，最小生成樹演算法，最小樹形圖，網路流演算法和匹配演算法 ；

6、動態規劃；

7、其他演算法：包括數值分析，加密演算法，排序演算法，檢索演算法和隨機化演算法。

『貳』 遞歸演算法一般用什麼實現

遞歸演算法一般用遞歸函數實現，依靠系統棧完成遞歸的返回計算。

『叄』 擴展歐幾里德演算法的擴展演算法

對於不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數，必然存在無數組整
數對 x，y ，使得 gcd（a，b）=ax+by。
c++語言實現 intexgcd(lla,llb,ll&x,ll&y){if(a==0){x=0;y=1;returnb;}else{lltx,ty;lld=exgcd(b%a,a,tx,ty);x=ty-(b/a)*tx;y=tx;returnd;}}求解 x，y的方法的理解
設 a>b。
1，顯然當 b=0，gcd（a，b）=a。此時 x=1，y=0；
2，a>b>0 時
設 ax1+ by1= gcd(a,b);
bx2+ (a mod b)y2= gcd(b,a mod b);
根據樸素的歐幾里德原理有 gcd(a,b) = gcd(b,a mod b);
則:ax1+ by1= bx2+ (a mod b)y2;
即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2;
也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2);
根據恆等定理得：x1=y2; y1=x2- [a / b] *y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基於 x2，y2.
上面的思想是以遞歸定義的，因為 gcd 不斷的遞歸求解一定會有個時候 b=0，所以遞歸可以結束。
擴展歐幾里德演算法
擴展歐幾里德演算法是用來在已知a, b求解一組x，y使得ax+by = Gcd(a, b) =d(解一定存在，根據數論中的相關定理)。擴展歐幾里德常用在求解模線性方程及方程組中。下面是一個使用C++的實現： intexGcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intr=exGcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;returnr;}把這個實現和Gcd的遞歸實現相比，發現多了下面的x,y賦值過程，這就是擴展歐幾里德演算法的精髓。
可以這樣思考:
對於a'=b,b'=a%b 而言，我們求得 x, y使得 a'x+b'y=Gcd(a',b')
由於b'=a%b=a-a/b*b (註：這里的/是程序設計語言中的除法)
那麼可以得到:
a'x+b'y=Gcd(a',b') ===>
bx+(a - a / b * b)y = Gcd(a', b') = Gcd(a, b) ===>
ay +b(x - a / b*y) = Gcd(a, b)
因此對於a和b而言，他們的相對應的p，q分別是 y和(x-a/b*y)
使用擴展歐幾里德演算法解決不定方程的辦法
對於不定整數方程pa+qb=c，若 c mod Gcd(a, b)=0,則該方程存在整數解，否則不存在整數解。
上面已經列出找一個整數解的方法，在找到p * a+q * b = Gcd(a, b)的一組解p0,q0後，p * a+q * b = Gcd(a, b)的其他整數解滿足：
p = p0 + b/Gcd(a, b) * t
q = q0 - a/Gcd(a, b) * t(其中t為任意整數)
至於pa+qb=c的整數解，只需將p * a+q * b = Gcd(a, b)的每個解乘上 c/Gcd(a, b) 即可，但是所得解並不是該方程的所有解，找其所有解的方法如下：
在找到p * a+q * b = Gcd(a, b)的一組解p0,q0後，可以
得到p * a+q * b = c的一組解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，p * a+q * b = c的其他整數解滿足：
p = p1 + b/Gcd(a, b) * t
q = q1 - a/Gcd(a, b) * t(其中t為任意整數)
p 、q就是p * a+q * b = c的所有整數解。
編程時 exgcd 更多用於求解「中國剩餘定理」相關知識 舉個例子比如n除以5餘2 除以13餘3 那麼n最小是多少，所有的n滿足什麼條件？
n（min)=42
n=42+k*65
歐幾里德演算法的擴展
擴展歐幾里德演算法不但能計算(a，b)的最大公約數，而且能計算a模b及b模a的乘法逆元，用C語言描述如下： intgcd(inta,intb,int&ar,int&br){intx1,x2,x3;inty1,y2,y3;intt1,t2,t3;if(0==a)//有一個數為0,就不存在乘法逆元{ar=0;br=0;returnb;}if(0==b){ar=0;br=0;returna;}x1=1;x2=0;x3=a;y1=0;y2=1;y3=b;intnk;for(t3=x3%y3;t3!=0;t3=x3%y3){k=x3/y3;t2=x2-k*y2;t1=x1-k*y1;x1=y1;x2=y2;x3=y3;y1=t1;y2=t2;y3=t3;}if(y3==1)//有乘法逆元{ar=(y2+b)%b;//對求出來負的乘法逆元進行處理，使之在模b的完全剩餘集里br=(y1+a)%a;//原來這里是錯的return1;}else//公約數不為1,無乘法逆元{ar=0;br=0;returny3;}}擴展歐幾里德演算法對於最大公約數的計算和普通歐幾里德演算法是一致的。計算乘法逆元則顯得很難明白。我想了半個小時才想出證明他的方法。
首先重復操作整除中的一個論斷：
如果gcd(a，b)=d，則存在m，n，使得d = ma + nb，稱呼這種關系為a、b組合整數d，m，n稱為組合系數。當d=1時，有 ma + nb = 1 ，此時可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
為了證明上面的結論，我們把上述計算中xi、yi看成ti的迭代初始值，考察一組數(t1，t2，t3)，用歸納法證明：當通過擴展歐幾里德演算法計算後，每一行都滿足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假設前k行都成立，考察第k+1行
對於k-1行和k行有
t1(k-1) t2(k-1) t3(k-1)
t1(k) t2(k) t3(k)
分別滿足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k) × a + t2(k) × b = t3(k)
根據擴展歐幾里德演算法，假設t3(k-1) = j t3(k) + r
則：
t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
則
t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +
t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得證
因此，當最終t3迭代計算到1時，有t1× a + t2 × b = 1，顯然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。

『肆』 求演算法設計：基本遞歸演算法一

遞歸演算法 就是函數或過程的自我調用，演算法精煉，但較為抽象。
由於是自我調用，但一定要保證逐步簡化，最終能結束退出，否則會造成堆棧溢出。

『伍』 演算法設計的基本方法裡面的「遞歸」是什麼意思

遞歸做為一種演算法在程序設計語言中廣泛應用.是指函數/過程/子程序在運行過程中直接或間接調用自身而產生的重入現象.遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫程序能使程序變得簡潔和清晰.。 遞歸是一種重要的編程技術。該方法用於讓一個函數從其內部調用其自身。一個示例就是計算階乘。0 的階乘被特別地定義為 1。 更大數的階乘是通過計算 1 * 2 * ...來求得的，每次增加 1，直至達到要計算其階乘的那個數。下面的段落是用文字定義的計算階乘的一個函數。「如果這個數小於零，則拒絕接收。如果不是一個整數，則將其向下舍入為相鄰的整數。如果這個數為 0，則其階乘為 1。如果這個數大於 0，則將其與相鄰較小的數的階乘相乘。」要計算任何大於 0 的數的階乘，至少需要計算一個其他數的階乘。用來實現這個功能的函數就是已經位於其中的函數；該函數在執行當前的這個數之前，必須調用它本身來計算相鄰的較小數的階乘。這就是一個遞歸示例。遞歸和迭代（循環）是密切相關的 — 能用遞歸處理的演算法也都可以採用迭代，反之亦然。確定的演算法通常可以用幾種方法實現，您只需選擇最自然貼切的方法，或者您覺得用起來最輕松的一種即可。顯然，這樣有可能會出現問題。可以很容易地創建一個遞歸函數，但該函數不能得到一個確定的結果，並且不能達到一個終點。這樣的遞歸將導致計算機執行一個「無限」循環。下面就是一個示例：在計算階乘的文字描述中遺漏了第一條規則（對負數的處理） ，並試圖計算任何負數的階乘。這將導致失敗，因為按順序計算 -24 的階乘時，首先不得不計算 -25 的階乘；然而這樣又不得不計算 -26 的階乘；如此繼續。很明顯，這樣永遠也不會到達一個終止點。因此在設計遞歸函數時應特別仔細。如果懷疑其中存在著無限遞歸的可能，則可以讓該函數記錄它調用自身的次數。如果該函數調用自身的次數太多，即使您已決定了它應調用多少次，就自動退出。下面仍然是階乘函數，這次是用 JScript 代碼編寫的。 // 計算階乘的函數。如果傳遞了// 無效的數值（例如小於零），// 將返回 -1，表明發生了錯誤。若數值有效，// 把數值轉換為最相近的整數，並// 返回階乘。function factorial(aNumber) {aNumber = Math.floor(aNumber); // 如果這個數不是一個整數，則向下舍入。if (aNumber < 0) { // 如果這個數小於 0，拒絕接收。 return -1; } if (aNumber == 0) { // 如果為 0，則其階乘為 1。 return 1; } else return (aNumber * factorial(aNumber - 1)); // 否則，遞歸直至完成。}

『陸』 遞歸演算法怎麼做

遞歸就是函數方法的自我調用。
不是什麼問題都可以用遞歸演算法的， 要看具體問題是否適合用遞歸方法解決。

『柒』 《演算法設計與分析》中遞歸的概念是什麼 謝謝大家。。

自己調用自己，調到底部再，層層返回，不推薦使用，比較耗時間。

『捌』 請教高人 遞歸演算法編寫思路技巧

一個子程序（過程或函數）的定義中又直接或間接地調用該子程序本身，稱為遞歸。遞歸是一種非常有用的程序設計方法。用遞歸演算法編寫的程序結構清晰，具有很好的可讀性。遞歸演算法的基本思想是：把規模大的、較難解決的問題變成規模較小的、易解決的同一問題。規模較小的問題又變成規模更小的問題，並且小到一定程度可以直接得出它的解，從而得到原來問題的解。
利用遞歸演算法解題，首先要對問題的以下三個方面進行分析：
一、決定問題規模的參數。需要用遞歸演算法解決的問題，其規模通常都是比較大的，在問題中決定規模大小（或問題復雜程度）的量有哪些？把它們找出來。
二、問題的邊界條件及邊界值。在什麼情況下可以直接得出問題的解？這就是問題的邊界條件及邊界值。
三、解決問題的通式。把規模大的、較難解決的問題變成規模較小、易解決的同一問題，需要通過哪些步驟或等式來實現？這是解決遞歸問題的難點。把這些步驟或等式確定下來。
把以上三個方面分析好之後，就可以在子程序中定義遞歸調用。其一般格式為：
if 邊界條件 1 成立 then
賦予邊界值 1
【 elseif 邊界條件 2 成立 then
賦予邊界值 2
┇ 】
else
調用解決問題的通式
endif
例 1 ： 計算勒讓德多項式的值

x 、 n 由鍵盤輸入。
分析： 當 n ＝ 0 或 n ＝ 1 時，多項式的值都可以直接求出來，只是當 n ＞ 1 時，才使問題變得復雜，決定問題復雜程度的參數是 n 。根據題目提供的已知條件，我們也很容易發現，問題的邊界條件及邊界值有兩個，分別是：當 n ＝ 0 時 P n (x) ＝ 1 和當 n ＝ 1 時 P n (x) ＝ x 。解決問題的通式是：
P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。
接下來按照上面介紹的一般格式定義遞歸子程序。
function Pnx(n as integer)
if n ＝ 0 then
Pnx ＝ 1
elseif n ＝ 1 then
Pnx ＝ x
else
Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n
endif
end function
例 2 ： Hanoi 塔問題：傳說印度教的主神梵天創造世界時，在印度北部佛教聖地貝拿勒斯聖廟里，安放了一塊黃銅板，板上插著三根寶石針，在其中一根寶石針上，自下而上地放著由大到小的 64 個金盤。這就是所謂的梵塔（ Hanoi ），如圖。梵天要求僧侶們堅持不渝地按下面的規則把 64 個盤子移到另一根針上：

(1) 一次只能移一個盤子；
(2) 盤子只許在三根針上存放；
(3) 永遠不許大盤壓小盤。
梵天宣稱，當把他創造世界之時所安放的 64 個盤子全部移到另一根針上時，世界將在一聲霹靂聲中毀滅。那時，他的虔誠的信徒都可以升天。
要求設計一個程序輸出盤子的移動過程。
分析： 為了使問題更具有普遍性，設共有 n 個金盤，並且將金盤由小到大依次編號為 1 ， 2 ，…， n 。要把放在 s(source) 針上的 n 個金盤移到目的針 o(objective) 上，當只有一個金盤，即 n ＝ 1 時，問題是比較簡單的，只要將編號為 1 的金盤從 s 針上直接移至 o 針上即可。可定義過程 move(s,1,o) 來實現。只是當 n>1 時，才使問題變得復雜。決定問題規模的參數是金盤的個數 n ；問題的邊界條件及邊界值是：當 n ＝ 1 時， move(s,1,o) 。
當金盤不止一個時，可以把最上面的 n － 1 個金盤看作一個整體。這樣 n 個金盤就分成了兩個部分：上面 n － 1 個金盤和最下面的編號為 n 的金盤。移動金盤的問題就可以分成下面三個子問題（三個步驟）：
(1) 藉助 o 針，將 n － 1 個金盤（依照上述法則）從 s 針移至 i(indirect) 針上；
(2) 將編號為 n 的金盤直接從 s 針移至 o 針上；
(3) 藉助 s 針，將 i 針上的 n － 1 個金盤（依照上述法則）移至 o 針上。如圖

其中第二步只移動一個金盤，很容易解決。第一、第三步雖然不能直接解決，但我們已經把移動 n 個金盤的問題變成了移動 n － 1 個金盤的問題，問題的規模變小了。如果再把第一、第三步分別分成類似的三個子問題，移動 n － 1 個金盤的問題還可以變成移動 n － 2 個金盤的問題，同樣可變成移動 n － 3 ，…， 1 個金盤的問題，從而將整個問題加以解決。
這三個步驟就是解決問題的通式，可以以過程的形式把它們定義下來：
hanoi(n － 1,s,o,i)
move(s,n,o)
hanoi(n － 1,i,s,o)
參考程序如下：
declare sub hanoi(n,s,i,o)
declare sub move(s,n,o)
input "How many disks?",n
s ＝ 1
i ＝ 2
o ＝ 3
call hanoi(n,s,i,o)
end
sub hanoi(n,s,i,o)
rem 遞歸子程序
if n ＝ 1 then
call move(s,1,o)
else
call hanoi(n － 1,s,o,i)
call move(s,n,o)
call hanoi(n － 1,i,s,o)
endif
end sub
sub move(s,n,o)
print "move disk";n;
print "from";s;"to";o
end sub

『玖』 遞歸演算法的實現

如何設計遞歸演算法
1.確定遞歸公式
2.確定邊界(終了)條件
遞歸的一般模式
procere aaa(k:integer);
begin
if k=1 then (邊界條件及必要操作)
else begin
aaa(k-1);
(重復的操作);
end;
end;
C#:例子
例：一列數的規則如下: 1、1、2、3、5、8、13、21、34...... 求第30位數是多少。
public class MainClass{public static void Main(){Console.WriteLine(Foo(30));}public static int Foo(int i){if (i <= 0)return 0;else if(i > 0 && i <= 2)return 1;else return Foo(i -1) + Foo(i - 2);}}
又如:
procere a;
begin
.
.
.
a;
.
.
.
end;
這種方式是直接調用.
又如:
procere c(形參);forward;
procere b;
局部說明
begin
. .
c(實參);
. .
end;
procere c;
局部說明；
begin
. .
b;
. .
end;
這種方式是間接調用.
例1計算n!可用遞歸公式如下:
fac:=n*fac(n-1) {當n>0時}
fac(n)={
fac:=1; { 當n=0時}
可編寫程序如下:
program facn;
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(n,'!=',fac(n):0:0);
end. JavaScript:例子//遞歸演算法//遞歸演算法functionrecursionAlgorithm(num){ if(num<=1)//判斷如果num小於等於1的情況下，返回本身 { return1; }else { returnnum*arguments.callee(num-1);//調用函數本身進行返回 }}

『拾』 關於遞歸演算法

你輸入了三次，所以遞歸有三層，最外面一層是 a = A,程序停止在if(a!= '#') printf();
中間的一層是 a = B,程序同樣停止在if(a!= '#') printf(); 最裡面的一層，也就是你輸入a = #,
程序在判斷完兩個if後返回到上一層，if(a! ='#') printf("%c\n",a); 輸出 B ，然後再返回上一層輸出 A