標籤: 暫無標籤

遞歸演算法是把問題轉化為規模縮小了的同類問題的子問題。然後遞歸調用函數(或過程)來表示問題的解。

遞歸演算法的特點
遞歸演算法是一種直接或者間接地調用自身演算法的過程。在計算機編寫程序中,遞歸演算法對解決一大類問題是十分有效的,它往往使演算法的描述簡潔而且易於理解。
遞歸演算法解決問題的特點:
(1) 遞歸就是在過程或函數里調用自身。
(2) 在使用遞歸策略時,必須有一個明確的遞歸結束條件,稱為遞歸出口。
(3) 遞歸演算法解題通常顯得很簡潔,但遞歸演算法解題的運行效率較低。所以一般不提倡用遞歸演算法設計程序。
(4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開闢了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸演算法設計程序。
舉例
描述:把一個整數按n(2<=n<=20)進位表示出來,並保存在給定字元串中。比如121用二進位表示得到結果為:「1111001」。
參數說明:s: 保存轉換后得到的結果。
n: 待轉換的整數。
b: n進位(2<=n<=20)
void
numbconv(char *s, int n, int b)
{
int len;
if(n == 0) {
strcpy(s, "");
return;
}
"
numbconv(s, n/b, b);
"
len = strlen(s);
s[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];
s[len+1] = '\0';
}
void
main(void)
{
char s[20];
int i, base;
FILE *fin, *fout;
fin = fopen("palsquare . in", "r");
fout = fopen("palsquare.out", "w");
assert(fin != NULL && fout != NULL);
fscanf(fin, "%d", &base);
"
for(i=START; i <= END; i++) {
numbconv(s, i*i, base);
fprintf(fout, "%s\n", s);
}
exit(0);
}
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);
  }
  }

1遞歸演算法簡析

遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫
遞歸能使程序變得簡潔和清晰.
如何設計遞歸演算法
1.確定遞歸公式
2.確定邊界(終了)條件

典型例題

例3漢諾塔問題
如圖:已知有三根針分別用1,2,3表示,在一號針中從小放n個盤子,現要求把所有的盤子
從1針全部移到3針,移動規則是:使用2針作為過度針,每次只移動一塊盤子,且每根針上
不能出現大盤壓小盤.找出移動次數最小的方案.
程序如下:
program hanoi;
var
n:integer;
procedure 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;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b ;
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end;
while (b<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b;b:=t1; end
until i=j;
b:=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);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do
write(a:6);
writeln;
end.
例5求最大公約數
最大公約數演算法:給兩個數,如果兩個數相等,最大公約數是其本身;如果不等,取兩個數相減的絕對值和兩個數中最小的數比較,相等則為最大公約,不等則繼續上面的演算法,直到相等。
程序如下:
public class YueShuTest{
public static void yueshu(int num1,int num2){
if(num1==num2){
System.out.println(num1);
}
else{
//遞歸調用本身
yueshu(Math.abs(num1-num2),Math.min(num1,num2));
}
}
}

2{遞歸的一般模式}

procedure aaa(k:integer);
begin
if k=1 then (邊界條件及必要操作)
else begin
aaa(k-1);
(重複的操作);
end;
end;

相關評論

同義詞:暫無同義詞