遞歸演算法流程圖

A. 已知A[n]為整數數組，試寫出實現下列運算的遞歸演算法： (1) 求數組A中的最大整數。 (2) 求n個整數的和。

//遞歸求數組A[n]中的最大整數；
int maxintA(int n)
{
if(0 == n) return 0;//數組為空
if(1 == n) return a[n-1];//數組中只有一個元素

return (a[n-1] > manxintA(n-1)?a[n-1]:maxintA(n-1));//遞歸

}

//遞歸求素組A[n]中n個整數的和
int sumofA(int n)
{
if(0==n) return 0;// 數組為空
if(1==n) return a[n-1];// 數組中只有一個元素

return (a[n-1]+sumofA(n-1));//遞歸
}

B. java中遞歸演算法是什麼怎麼算的

一、遞歸演算法基本思路：

Java遞歸演算法是基於Java語言實現的遞歸演算法。遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。遞歸演算法實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法表示問題的解。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形式，從而使我們的編碼大大簡化，然而遞歸的思維確實跟我們的常規思維相逆的，通常都是從上而下的思維問題，而遞歸趨勢從下往上的進行思維。

二、遞歸演算法解決問題的特點：

【1】遞歸就是方法里調用自身。

【2】在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

【3】遞歸演算法代碼顯得很簡潔，但遞歸演算法解題的運行效率較低。所以不提倡用遞歸設計程序。

【4】在遞歸調用的過程中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸演算法設計程序。

【5】在做遞歸演算法的時候，一定把握出口，也就是做遞歸演算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口就是一個條件，當滿足了這個條件的時候我們就不再遞歸了。

三、代碼示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代碼執行流程圖如下：

此程序中n=5就是程序的出口。

C. 二叉樹先序遍歷演算法流程圖怎麼畫，學的是數據結構c語言。

在計算機軟體專業中，數據結構、以及 C 語言這兩門課程是非常重要的兩門課程。最為重要的是：如果將來想做計算機軟體開發工作的話，那麼對 C 語言中的指針編程、以及遞歸的概念是必須要熟練精通掌握的，因為它和數據結構課程中的鏈表、二叉樹等內容的關系實在是太緊密了。但是這個編程技能必須要依靠自己多上機實踐才能夠真正徹底掌握的。
首先要搞明白二叉樹的幾種遍歷方法：（1）、先序遍歷法：根左右；（2）、中序遍歷法：左根右；（3）、後序遍歷法：左右根。其中根：表示根節點；左：表示左子樹；右：表示右子樹。
至於談到如何畫先序遍歷的流程圖，可以這樣考慮：按照遞歸的演算法進行遍歷一棵二叉樹。

程序首先訪問根節點，如果根節點的值為空（NULL），則停止訪問；如果根節點的值非空，則遞歸訪問二叉樹的左子樹（left），然後是依然判斷二叉樹下面的左子樹下面的根節點是否為空（NULL），如果根節點的值為空（NULL），則返回上一層，再訪問二叉樹的右子樹（right）。依此類推。

D. c語言課程設計：選出一位幸運人士，一定要用遞歸演算法！要源代碼，流程圖，和演算法描述！

這道題做ACM題目的時候做過，當時使用數組做的，最後因為效率太低通過不了。

G Josephus Problem
Time Limit:1000MS Memory Limit:65535K

題型: 編程題 語言: 無限制

描述
Josephus Problem is an ancient problem named for Flavius Josephus. There are people standing in a circle waiting to be executed. The counting out begins at the
first point in the circle and proceeds around the circle in a fixed direction. In each step, one person is skipped and the next person is executed. The elimination
proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

For example, if there are 10 people in the circle, the executed order is 2, 4, 6, 8, 10, 3, 7, 1, 9. So the 5th person survives.

Now we define a function J(n) to be the survivor』s number when there are n person in the circle, and J^2(n)=J(J(n)), for instance J^2(10)=J(J(10))=J(5)=3,
and J^3(n)=J(J(J(n))), and so on. Could you calculate J^m(n)?

輸入格式
The input consists of a number of cases.
Each case contains integers n and m. 0<n, m<=10^9
The input is terminated by a case with m=n=0

輸出格式
For each case, print the number J^m(n)

輸入樣例
10 2
10 1
20 1
0 0

輸出樣例
3
5
9

Provider
admin
#include<stdio.h>
#include<malloc.h>
#include<math.h>

int J(int number,int * circle)

{
int i,length=number;

for(i=0;i<number;i++)
{
circle[i]=i+1;

}

while(length>1)
{
if(length%2==0)
{
for(i=0;i<length;i++)
{

circle[i]=circle[i*2];

}
length=length/2;
continue;

}
if(length%2==1)
{
circle[0]=circle[length-1];
for(i=1;i<length;i++)
{

circle[i]=circle[(i-1)*2];

}
length=length/2+1;
continue;

}

}

return circle[0];
}

int main()
{

int n,m,i,*circle;

circle=(int*)malloc(n*sizeof(int));
while(1){
{
scanf("%d%d",&n,&m);
}while(n<0||m<0||m>10);
if(n==0&&m==0)
break;
for(i=0;i<m;i++)
{
n=J(n,circle);

}
printf("%d\n",n);

}

return 0;
}

E. 請教遍歷所有文件名（FileName）的流程圖（請使用遞歸演算法)

1、寫出 查找子節點的方法 findchild（this node），參數是當前節點，開始是」filesystem「
2、查看當前節點的子節點 subnode = findchild （this node）
如果子節點不是 file，調用方法tempnode = findchild（sub node），直到找到子節點file
3、層層返回
filesystem --》 driver --》 dir --》 file
dir《 --
--》 file
--》 file
driver《--
filesystem 《--

F. 想要流程圖

圖的遍歷

從圖中某一頂點出發訪遍圖中其餘頂點，且使每一頂點僅被訪問一次。這一過程叫做圖的遍歷。
遍歷圖的基本方法有兩種：深度優先搜索和廣度優先搜索。這兩種方法都適用於有向圖和無向圖。
和樹的遍歷類似，圖的遍歷也是從某個頂點出發，沿著，某條邊搜索路徑對圖中所有頂點各作一次訪問。若給定的圖是連通圖，則從圖中任意頂點出發順著邊可以訪問到該圖中所有的頂點，然而，圖的遍歷比樹的遍歷復雜得多，這是因為圖中的任一點都可能和其餘頂點相鄰接，故在訪問了某個頂點之後，可能順著某條迴路又到了該頂點。為了避免重復訪問同一個頂點，必須記住每個頂點是否被訪問過。為此，可設置一個布爾向量visited[1..n],它的初值為false，一旦訪問了頂點vi，便將visited[i]置為ture。

一、連通圖的深度優先搜索
連通圖深度優先搜索的基本思想如下：假定圖中某個頂點v1為出發點，首先訪問出發點v1，然後任選一個v1的訪問過的鄰接點v2，以v2為新的出發點繼續進行深度優先搜索，直至圖中所有頂點被訪問過。
顯然，圖的深度優先搜索是一個遞歸過程，類似於樹的前序遍歷，它的特點是盡可能先對縱深方向進行搜索，故稱之深度優先搜索。
現以圖5-10中G為例說明深度優搜索過程。假定v1是出發點，首先訪問v1。因v1有兩個鄰接點v2、v3均未被訪問，選擇v2作為新的出發點。訪問v2之後，再找v2的未訪問過的鄰接點。同v2鄰接的有v1、v4、v5，其中v1以被訪問過，而v4、v5未被訪問。選擇v4作為新的出發點。重復上述搜索過程繼續依次訪問v8、v5。訪問v5之後，由於與v5相鄰的頂點均以被訪問，搜索退回到v8。由於v8、v4、v2都沒有未被訪問的鄰接點，所以搜索過程連續地從v8退回到v4，再退回到v2最後退回到v1這時選擇v1的未被訪問過的鄰接點v3，繼續往下搜索，依次訪問v3、v6、v7，從而遍歷了圖中全部頂點。在這個過程中得到的頂點的訪問序列：

(a)無向圖G

(b)G的深度優先搜索過程
圖5-10a 深度優先搜索過程示例

v1→v2→v4→v8→v5→v3→v6→v7
這樣的序列就稱之為圖的深度優先搜索遍歷序列。
連通圖的深度優先搜索的非形式演算法如下:
procere dfs (g:graph;v1:integer);
//從v1出發深度優先遍歷圖g//
begin write(v1);
visited[v1]:=ture;
找出g中v1的第一鄰接點w;
while w存在do
[ if w 未被訪問 then dfs(g,w);
w:=g中v1的下一鄰接點]
end;
上述非行式演算法未涉及圖的存儲結構.圖的遍歷過程必然地包含對圖中每個頂點查找其鄰接點這一操作;而在圖的不同存儲結構上查找鄰接點的方法是不同的.
若以鄰接表為存儲結構,查找鄰接點操作實際上是順序查找鏈表.鄰接表上的深度優先演算法如下:
procere dfs(g:adj_list;v1:integer);
//從v1出發深度優先遍歷圖g.g以鄰接表為存儲結構//
begin write(v1);
visited[v1]:=ture;//標志v1已訪問//
p=g[v1].link;//找v1的第一個鄰接點//
while p<>nil do
[ if not (visited[p↑.adjvex]);//書錯寫成vertex//
then dfs(g,p↑.adjvex);
p:=p↑.next]//回溯----找v1的下一個鄰接點//
end;

二、連通圖的廣度優先搜索
連通圖廣度優先搜索的基本思想是：從圖中某個頂點v1出發，訪問了v1之後依次訪問v1的所有鄰接點；然後分別從這些鄰接點出發按深度優先搜索遍歷圖的其它頂點，直至所有頂點都被訪問到。它類似於樹的按層次遍歷，其特點是盡可能優先對橫向搜索，故稱之為廣度優先搜索。
下面以圖5-10中G為例說明廣度優先搜索的過程。首先從起點v1出發，訪問v1。v1有兩個未曾訪問的鄰接點v2和v3。先訪問v2，再訪問v3。然後再先後訪問v2的未曾訪問過的鄰接點v4、v5及v3的未曾訪問過的鄰接點v6、v7。最後訪問v4的未曾訪問過的鄰接點v8。至此圖中所有頂點均以被訪問到。得到的頂點訪問序列為：

(a)無向圖G

(b)G的廣度優先搜索過程
圖5-10b 廣度優先搜索過程示例

v1→v2→v3→v4→v5→v6→v7→v8
相應的，這樣的序列就稱之為圖的廣度優先搜索遍歷序列。
在廣度優先搜索中，若對x的訪問先於y，則對x鄰接點的訪問也先於隊y的鄰接點的訪問。因此，可採用隊列來暫存那些剛訪問過，但可能還有為訪問過的鄰接點的頂點。
連通圖的廣度優先搜索演算法如下：
procere bfs(g:adj_list;v1:integer);//書錯寫成adjlist//
//以鄰接表為存儲結構的廣度優先搜索。Q為隊列，假定visited的各分量已只置 為false//
begin init_linkedque(Q);//設計一個空隊Q//
visited[v1]:=ture;write(v1);
in_limkedque(Q,v1); //v1入隊//
while not empty(Q) do
[ v:=out_linkedque(Q);
p:=adj_list[v].link;//書錯寫成adjlist//
while p<>nil do
[ if visited[p↑.adjvex]:=false;//書錯寫成vertex//
then
[visited[p↑.adjvex]:=ture;
with(p↑.adjvex);
in_linkedque(Q,p↑.adjvex);]
p:=p↑.next]]
end;

三、圖的連通分量計算
如果要遍歷一個非連通圖，則需要多次調用dfs或bfs，每一次都要得到一個連通分量；調用dfs或bfs的次數就是連通分量的個數。因此很容易寫出非連通圖的遍歷演算法和計算一個圖的連通分量得演算法。下面給出的是以鄰接表為存儲結構，通過調用深度優先搜索演算法實現的計算連通分量的演算法。
procee conn_component (var g:graph;
var visited:array[1..vnum);
begin for v:=1 to vnum do
visited[v]:flase;
count:=0;
for v:=1 to vnum do
if not(visited[v])then
[count:=count+1;
write('component',count,':');
dfs(g,v);writeln;]
end;
對於圖5-5中非連通圖G3，用上述演算法可求出3個連通分量，各連通分量所含頂點如下：
component1: 1 2 3
component2: 4 5 6 7
component3: 8 9
注意，若從上述演算法中刪去有關連通分量計數器的操作，就得到一個非連通圖德遍歷演算法。

詳細資料和圖片請參看參考資料，那裡的比較詳細

G. 遞歸演算法流程圖如何畫請以菲波那切數列遞歸演算法為例

遞歸（recursion）：程序調用自身的編程技巧。
遞歸滿足2個條件：
1）有反復執行的過程（調用自身）
2）有跳出反復執行過程的條件（遞歸出口）

遞歸例子：
（1）階乘
n! = n * (n-1) * (n-2) * ...* 1(n>0)
//階乘
int recursive(int i)
{
int sum = 0;
if (0 == i)
return (1);
else
sum = i * recursive(i-1);
return sum;
}

（2）河內塔問題

//河內塔
void hanoi(int n,int p1,int p2,int p3)
{
if(1==n)
cout<<"盤子從"<<p1<<"移到"<<p3<<endl;
else
{
hanoi(n-1,p1,p3,p2);
cout<<"盤子從"<<p1<<"移到"<<p3<<endl;
hanoi(n-1,p2,p1,p3);
}
}

（3）全排列
從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當m=n時所有的排列情況叫全排列。
如1,2,3三個元素的全排列為：
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
//全排列
inline void Swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void Perm(int list[],int k,int m)
{
if (k == m-1)
{
for(int i=0;i<m;i++)
{
printf("%d",list[i]);
}
printf("n");
}
else
{
for(int i=k;i<m;i++)
{
Swap(list[k],list[i]);
Perm(list,k+1,m);
Swap(list[k],list[i]);
}
}
}

H. 給定以下XML文件，完成演算法流程圖

void FindFile( Directory d ) { FileOrFolders = d.GetFileOrFolders(); foreach( FileOrFolder fof in FileOrFolders ) { if( fof is File ) You Found a file; else if ( fof is Directory ) FindFile( fof ); } }

I. 漢諾塔問題的遞歸演算法流程圖

關鍵是第一步移法，奇數層的說，3層在第一柱，後兩根柱數數：123。所以，第一塊應放在第二根柱，4層，第一塊放第三柱。...........奇數層第一塊放第二柱，偶數層第一塊放第三柱。

J. 按要求設計遞歸演算法。只需寫出偽代碼或畫流程圖，不需語言實現，但演算法必須完整清晰。

arrs[100000][100000];
a[100000];
f(i,){
if(i==4){
arrs[]=a;
return;
}
a[i]=;
f(i+1,+3);
f(i+1,+4);
}
f(0,0)
arrs就是結果，並且是排了序的。