數學遞歸演算法

❶ 設計遞歸演算法生成n個元素的所有排列對象

#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;

template<class T>
void permutation(T list[], int k, int m)
{
if (k == m)
{
(list, list + m + 1, ostream_iterator<T>(cout, "")); //將當前list排序
cout << endl;
}
else{
for (int i = k; i <= m; i++)
{
swap(list[i], list[k]); //將下標為i的元素交換到k位置，類似從list[k:m]中剔除操作
permutation(list, k + 1, m);
swap(list[i], list[k]);
}
}
}

int main(int argc, char* argv[])
{
char arr[3] = { 'a', 'b', 'c' };
cout << "排序結果如下：" << endl;
permutation(arr, 0, 2);
return 0;

}

(1)數學遞歸演算法擴展閱讀

遞歸，在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。也就是說，遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。

通俗來說，遞歸演算法的實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法來表示問題的解。

遞歸的基本原理

第一：每一級的函數調用都有自己的變數。

第二：每一次函數調用都會有一次返回。

第三：遞歸函數中，位於遞歸調用前的語句和各級被調用函數具有相同的執行順序。

第四：遞歸函數中，位於遞歸調用後的語句的執行順序和各個被調用函數的順序相反。

第五：雖然每一級遞歸都有自己的變數，但是函數代碼並不會得到復制。

❷ 漢諾塔遞歸演算法是什麼

如下：

1、漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。

大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

2、抽象為數學問題：從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數。

演算法分析（遞歸演算法）：

實現這個演算法可以簡單分為三個步驟：把n-1個盤子由A 移到 B；把第n個盤子由 A移到 C；把n-1個盤子由B 移到 C。從這里入手，在加上上面數學問題解法的分析，我們不難發現，移到的步數必定為奇數步。

1、中間的一步是把最大的一個盤子由A移到C上去。

2、中間一步之上可以看成把A上n-1個盤子通過藉助輔助塔（C塔）移到了B上。

3、中間一步之下可以看成把B上n-1個盤子通過藉助輔助塔（A塔）移到了C上。

❸ 漢諾塔遞歸演算法是什麼

hanot (n-1,b,a,c);（解釋：在把B塔上的(n-1))個藉助A塔移動到C塔）

為了實現 n個盤從 藉助c 從a 移動到 b

思路如下：

首先考慮極限當只有一個盤的時候，盤直接從 a -> b即可。

當有2個盤的時候，把1號盤從a -> c 然後 把2號盤 a->b 再 把 2好盤從 c - > b。

當有n個盤的時候，把 n-1個 盤 藉助 b 移動到 c 然後將 n號盤從 a -> b。

這時候只要將 n-1想辦法從c移動到 b 藉助 a 那麼就可以先把 n-2個盤藉助b移動到a。

遞歸，就是在運行的過程中調用自己。

構成遞歸需具備的條件：

1，子問題須與原始問題為同樣的事，且更為簡單；

2，不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。

在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況。

以上內容參考：網路-遞歸公式

❹ 遞歸的概念

​是指函數/過程/子程序在運行過程序中直接或間接調用自身而產生的重入現象。

在計算機編程里，遞歸指的是一個過程：函數不斷引用自身，直到引用的對象已知。

使用遞歸解決問題，思路清晰，代碼少。但是在主流高級語言中（如C語言、Pascal語言等）使用遞歸演算法要耗用更多的棧空間，所以在堆棧尺寸受限制時（如嵌入式系統或者內核態編程），應避免採用。所有的遞歸演算法都可以改寫成與之等價的非遞歸演算法。

漢諾塔問題，是常見可用遞歸解決的問題，不過也有非遞歸的解法。

菲波納契數列可用遞歸定義。

以下為求漢諾塔問題的Pascal程序：

procere Hanoi(n:integer;x,y,z:char);

遞歸
begin

if n<>1 then begin

Hanoi(n-1,x,z,y);

writeln(x,n,z);

Hanoi(n-1,y,x,z);

else writeln(x,n,z);

end;

end;

上述程序用接近自然語言的偽代碼可表述如下：

Hanoi 過程 (整型參數n; 字元型參數 x,y,z);

//註：n 代表本步中要處理的盤子數，x,y,z 分別表示 n 號盤子原來所在柱子、經由柱子、目標柱子

開始

如果 n 不為 1 ，那麼：開始

調用 Hanoi 過程 (參數為 n-1,x,z,y);

//註：這一步表示用本過程方法將剩餘 n-1 個盤子從柱子 x 經由柱子 z 移動到柱子 y

輸出 x,n,z; //註：表示將 n 號盤子從 x 移動到 z

調用 Hanoi 過程 (參數為 n-1,y,x,z);

//註：這一步表示用本過程方法將剩餘 n-1 個盤子從柱子 y 經由柱子 x 移動到柱子 z

結束; //以上程序段就完成了把 n 個盤子從柱子 x 經由柱子 y 移動到柱子 z

否則 輸出 x,n,z; //註：若 n 為1 的話本句直接輸出表示將 n 號盤子從 x 移動到 z
遞歸，就是在運行的過程中調用自己。

構成遞歸需具備的條件：

函數嵌套調用過程示例

1. 子問題須與原始問題為同樣的事，且更為簡單；

2. 不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。

在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況。

❺ 請問遞歸演算法的時間復雜度如何計算呢

遞歸演算法的時間復雜度在演算法中，當一個演算法中包含遞歸調用時，其時間復雜度的分析會轉化為一個遞歸方程求解，常用以下四種方法：

1.代入法(Substitution Method)

代入法的基本步驟是先推測遞歸方程的顯式解，然後用數學歸納法來驗證該解是否合理。

2.遞歸程序設計是程序設計中常用的一種方法，它可以解決所有有遞歸屬性的問題，並且是行之有效的.

3.但對於遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調用，則其運行時間可大為節省.

❻ 漢諾塔遞歸演算法是什麼

漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

注意：

我們在利用計算機求漢諾塔問題時，必不可少的一步是對整個實現求解進行演算法分析。到目前為止，求解漢諾塔問題最簡單的演算法還是同過遞歸來求。

這里還必須有一個結束點，或者具體的說是在調用到某一次後函數能返回一個確定的值，接著倒數第二個就能返回一個確定的值，一直到第一次調用的這個函數能返回一個確定的值。

現這個演算法可以簡單分為三個步驟：

（1） 把n-1個盤子由A 移到 B。

（2）把第n個盤子由 A移到 C。

（3） 把n-1個盤子由B 移到 C。

從這里入手，在加上上面數學問題解法的分析，我們不難發現，移到的步數必定為奇數步：

（1）中間的一步是把最大的一個盤子由A移到C上去。

（2）中間一步之上可以看成把A上n-1個盤子通過藉助輔助塔（C塔）移到了B上。

（3）中間一步之下可以看成把B上n-1個盤子通過藉助輔助塔（A塔）移到了C上。

❼ 什麼是遞歸遞歸有什麼用

1、程序調用自身的編程技巧稱為遞歸。遞歸做為一種演算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

2、遞歸一般的作用用於解決三類問題：
(1)數據的定義是按遞歸定義的。（Fibonacci函數）
(2)問題解法按遞歸演算法實現。
這類問題雖則本身沒有明顯的遞歸結構，但用遞歸求解比迭代求解更簡單，如Hanoi問題。
(3)數據的結構形式是按遞歸定義的。

❽ 什麼是遞歸遞歸有什麼用

一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。 一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。 注意： (1) 遞歸就是在過程或函數里調用自身; (2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。 遞歸演算法一般用於解決三類問題： (1)數據的定義是按遞歸定義的。(Fibonacci函數) (2)問題解法按遞歸演算法實現。(回溯) (3)數據的結構形式是按遞歸定義的。(樹的遍歷，圖的搜索) 遞歸的缺點： 遞歸演算法解題的運行效率較低。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。遞歸通俗的講就是一個函數在其代碼中反復調用自身。你應該知道菲波納契數列，這個數列的定義是f(x)=1?(x=1)f(x)=2?(x=2)f(x)=f(x-1)+f(x-2) (x>2)也就是說從第三項開始的每一項的值都等於是前兩項之和。這在數學中叫遞推數列--高中數學內容。

❾ (1-2+3-4+5-6+7-8+9)用遞歸方法怎麼寫

首先要理解遞歸本身其實是一項非常重要的演算法技巧。
遞歸滿足兩個條件：
1，不斷調用函數本身，也就是遞歸函數。
2，調用是有限的，也就是遞歸出口。
為了理解方便，下面是用一個最簡單的例子：求n的階乘。
n!(階乘)定義：
n!數學意思為n!
=
n*(n-1)!
&
1!=1;
其實根據上面遞歸定義結合分析下就可以n階乘的遞歸演算法：
1,構造一個遞歸函數,不斷乘以自身和使用自身減一後調用同樣函數．
2,定義出口，當函數參數等於1時結束;
如果用iso
c++語言描述如下：
int
factorial(int
n){
if(
n
>
1){
return
n*factorial(n-1);//遞歸函數調用
}
else
if(n
==
1){
return
1;
//遞歸出口
}
else{
return
error;//報告輸入錯誤
}
}
這里討論主要的不是上面這個簡單的例子，而是下面的一些改良．
因為遞歸設計大量的堆棧操作，所以一般都會考慮將遞歸轉為非遞歸來執行．
這里用上面這個程序作一個分析例子來分析．
假設這里執行factorial(4)，那麼程序會按照下面方式來執行：
(1)執行factorial(4)判斷n
>
1執行factorial(3),並且將factorial(4)函數相關信息存入一個堆棧．
(2)執行factorial(3)判斷n
>
1執行factorial(2),並且將factorial(3)函數相關信息存入一個堆棧．
(3)執行factorial(2)判斷n
>
1執行factorial(1),並且將factorial(2)函數相關信息存入一個堆棧．
(4)執行factorial(1)判斷n
==
1執行返回1;
(5)將factorial(2)函數從堆棧中彈出，執行2*1，並且返回2．
(6)將factorial(3)函數從堆棧中彈出，執行2*3，並且返回6．
(7)將factorial(4)函數從堆棧中彈出，執行6*4，並且返回24．
如下圖所示：
factorial(4)
-->factorial(3);
-->factorial(2);
-->factorail(1);
<--factorail(1);
<--factorial(2);
<--factorial(3);
<--結果
可以看到中間涉及的堆棧操作是很大的開銷，每次需要保存當前函數的所有信息．
為了避免這樣情況，可以使用下面這幾種方法來實現遞歸到非遞歸的轉換．
(1)
循環方法
循環方法是所有遞歸到非遞歸的轉換中最理想的方法，可以將開銷減少到最小．
不過也是分析起來最復雜的，對於簡單的遞歸可以用這樣的方法來處理．
例如：factorial計算
這里回到n!(階乘)定義上面來分析，這里將n!數學意思為n!
=
n*(n-1)!
&
1!=1;做一個擴展可以到到n!另外一個表示方法n!
=
n*(n-1)*(n-2)*....*1;
這樣就可以很容易得到另外一個定義：
n!表示執行n次循環計算一個增量k，初始k=1和結果t=1;每次t乘以k++的值.
iso
c++實現代碼如下：
factorial(int
n){
int
k
=
1
;//增量
int
t
=
1
;//臨時結果
while(k!=n){
t*=k;
k++;
}
return
t;
}
這樣可以避免遞歸帶來的大量堆棧操作．
(2)
自定義堆棧
對於復雜邏輯的堆棧操作，需要藉助外部堆棧來實現．
因為對於所有的遞歸操作最後分析出來都是形成的一顆樹形結構．
下面是一個遞歸實現factorial的一個方法，雖然在這個程序中對比循環來相對復雜，不過對於一些不能分析出來循環的遞歸操作來說自定義堆棧的方法可以達到空間開銷可控．
factorial(int
n){
stack
s;
int
t
=
1;//臨時變數
s.push(n);
while(s.top()!=1)[
t
*=
s.top();
s.push(s.top()-1);
s.pop();
}
return
t;
}
除了上面這兩種方法外，還可以使用一種迭代的方法實現遞歸到非遞歸的處理．

❿ 漢諾塔遞歸演算法是什麼

漢諾塔遞歸演算法是：f（n）=2^n-1。

漢諾塔，又稱河內塔，是一個源於印度古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。

大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。

不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。

不管這個傳說的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，並且始終保持上小下大的順序。

這需要多少次移動呢？這里需要遞歸的方法。假設有n片，移動次數是f（n）顯然f（1）等於1，f（2）等於3，f（3）=7，且f（k+1）=2*f（k）+1。此後不難證明f（n）=2^n-1。n=64時。

假如每秒鍾一次，共需多長時間呢：一個平年365天有31536000 秒，閏年366天有31622400秒，平均每年31556952秒，計算一下：18446744073709551615秒。

這表明移完這些金片需要5845.54億年以上，而地球存在至今不過45億年，太陽系的預期壽命據說也就是數百億年。真的過了5845.54億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。