演算法 (Algorithm)

定義

一個有限大小的指令集。

• 輸入： 外界提供輸入，或不需要輸入．
• 輸出： 至少產生一個輸出．
• 明確性： 指令清楚不含糊
• 有限性： 逐行有限數目的步驟之後停止
• 有效性： 指令需基本到可實行．

Algorithm exercise

SelectSort

void SelectSort(int *a, const int n){
	for(int i=0; i<n; i++){
		int j=i;
		for(int k=i+1; k<n; k++>){
			if(a[k] < a[j]){
				j=k;
			}
		}
		swqp(a[i],a[j])
	}
}

BinarySearch

// 疊代
void BinarySearch(int *a, const int x, const int n){
	int left=0, right=n-1;
	while(left <= right){
		int middle = (left+right)/2
		if(x < a[middle]){
			right = middle-1;
		}
		else if(x > a[middle]){
			left = middle+1;
		}
		else return middle;
	}
	return - 1 ;
}

// 遞迴 BinarySearch(a, x, 0, n-1)
void BinarySearch(int *a, const int x, const int left, const int right){
	if(left <= right){
		int middle = (left+right)/2
		if(x < a[middle]){
			return BinarySearch(a, x, left, middle-1)
		}
		else if(x > a[middle]){
			return BinarySearch(a, x, right, middle+1)
		}
		return middle;
	}
	return - 1 ;
}

Fibonacci

費氏數列定義為:F(0) = 0, F(1) = 1, F(i) = F(i-1) + F(i-2) (i ≥ 2)，請分別用C++寫出疊代與遞迴函式來計算F(i)的值。

// 疊代
#include <iostream>

int fibonacci(int n) {

	if (n <= 1)
        return n;

	int a=0, b=1, result;
	for(int i = 2; i <= n; i++){
		result = a + b;
		a = b;
		b = result;
	}
	return result;
}

int main() {
    int n;
    std::cout << "Enter the number of terms: ";
    std::cin >> n;
    
    std::cout << fibonacci(n) << " ";
    
    return 0;
}

// 遞迴
#include <iostream>

int fibonacci(int n) {
    if (n <= 1)
        return n;
    else
        return (fibonacci(n-1) + fibonacci(n-2));
}

int main() {
    int n;
    std::cout << "Enter the number of terms: ";
    std::cin >> n;
    
    std::cout << fibonacci(n) << " ";
    
    return 0;
}

未完待續 …

---