搜尋此網誌

2011年7月11日 星期一

軼代和遞迴Iterative and Recursive

遞迴的整體概念是把同樣類似重複的工作,分拆到最小的單位來做,然後慢慢把小單位的結果集合成大單位的結果,然後成為答案.
遞迴要有兩個要素:1.基本元素,也可說是終止條件 2.遞迴判斷條件,
例如:2^0 =1; 2^1=2*2^0; 2^2=2*2^1, 2^3=2*2^2,到最後我們可以歸納為
x^0=1,這個就是基本條件, 又若n>0的話, x^n=x*x^n-1;這個就是遞迴條件.
以下是以n的幾次方分別用用遞迴和軼代的方式來實作的程式碼:


#include <iostream>
using namespace std;

int recursive(int, int);

int main() {
cout << recursive(2,3);
return 0;

}

int recursive(int x, int n){
if(n==0){
return 1;
}else{
return x*recursive(x, n-1);
}
}






所有的遞迴和Iterative都可以互換,跑出同樣的結果,把上列程式用Iterative來寫變成:


#include <iostream>
using namespace std;

int recursive(int, int);

int main() {
cout << recursive(2, 3);
return 0;

}

int recursive(int x, int n) {
int answer=1;
if (n==0) {
return answer;
} else {
for (int i=0; i<n; i++) {
answer *=x;
}
}
return answer;
}




但遞迴較佔記憶體空間.

divide and conquer with recursive


遞迴常被使用在分割-處理的使用上,很多二分(Binary)相關的演算法都是用recursive實作

c++ Typedef的用法


typedef可以用來為常用的變數型態設定方便自己識別的名稱.



#include <iostream>
using namespace std;

typedef int Integer;

int main() {
Integer a=1;
Integer * number= &a;
Integer * number2= number;
(*number2)=3;
cout << *(number) << "\n";
return 0;
}


C++指標(Pointer)介紹


1. 指標可以用來指定一個記憶體位址儲存變數資料,用"&"符號可以取出變數的記憶體位址,"*"符號則是取出實際所儲存的值



#include <iostream>
using namespace std;

int main() {
int a=1;
int * number= &a;
cout << *(number) << "\n";
return 0;
}





2. 指標也可以互相指定到同一個記憶體位址,但要很小心,萬一任何一個指標更動到實際所儲存值,那麼另一個也會受影響到



#include <iostream>
using namespace std;

int main() {
int a=1;
int * number= &a;
int * number2= number;
(*number2)=3;
cout << *(number) << "\n";
return 0;
}