簡介

又有一個大老曾經說過 :

Programming = Data structures + Algorithms

Data structure 在這邊先不提

會先說明 Algorithms 演算法的淺薄概念

Algorithms: collections of steps for completing a task

簡單說，就是要設計一系列的動作，最後達成我們想要的目標，這就是演算法。

最簡單的來說，可以把一個大問題 problem

切成很多的 subproblem

這時候會用到 recursion 用來解決 subproblems

對於同一個問題，可能可以有很多個 algorithms 可以解決她

但是我們最想要的是一個 有效率、最優化 的演算法 (Time complexity)

但如果有非常多人同時再用一個程式，會考慮到這個程式會不會再那麼有效率等等，這時候就會用到資料結構(Data structure)來做配合，讓我們做的事情最優化。

演算法試做

Ex:

listing all prime numbers(質數)

• Given an integer n, let's list all the prime numbers no greater than n.

• Consider the following (imprecise) algorithms:

  • For each number i no greater than n, check whether it is a prime number.

  (nice but hard to execute)

  how to determine a prime number?

  • Idea1: If any number j < i can divide i, i is not a prime number.

    For each number j < i, check whether j divides i. If so report NO; otherwise report YES.

    就是先找一個數字 i， 再讓它去除以每一個比他小的正整數，如果有人可以整除他就代表他不是 prime，沒有人的話就是 prime。

    (這個動作稱作為 writing pseudocodes 簡單說就是用程式的方式先用中文或是英文寫出來，再用程式碼寫出來) 就是先不考慮語法。

    試試看 Pseudocode

    Given an integer n:
    for i from 2 to n
    	assume that i is a prime number
    	for i from 2 to i - 1
    		if j divides i
    			set i to be a composite number
    	if i is still considred as prime 
    		print i
    

    然後把他轉成程式:

    for (int i = 2; i <= n; i++){
    	bool isPrime = true;
    	for(int j = 2; j < i; j++){
    		if (i % j == 0){
    			isPrime = false;
    			break;
    		}
    	}
    	if (isPrime == true)
    		cout << i << " ";
    }
    

  因此，如果我們先把 algorithms 先寫出來，程式也不遠了

  那我們再來 modularize 這個問題吧!

  // Algorithm1
  #include<iostream>
  using namespace std;
  bool isPrime(int x);
  int main()
  {
  	int n = 0;
  	cin >> n;
  	for (int i = 2; i <= n; i++)
  	{
  		if (isPrime(i) == true)
  			cout << i << " ";
  	}
  	return 0;
  }
  
  // Function
  bool isPrime(int x)
  {
  	for (int i = 2; i < x; i++)
  	{
  		if (x % i ==0)
  			return false;
  	}
  	return true;
  }
  
  

  改進演算法

  那我們可不可以讓他跑得更快?????

  答案是可可的!

  // Algorithm2
  #include<iostream>
  using namespace std;
  bool isPrime(int x);
  int main()
  {
  	int n = 0;
  	cin >> n;
  	for (int i = 2; i <= n; i++)
  	{
  		if (isPrime(i) == true)
  			cout << i << " ";
  	}
  	return 0;
  }
  
  // Function
  bool isPrime(int x)
  {
  	for (int i = 2; ***i * i <= x***; i++)
  	{
  		if (x % i ==0)
  			return false;
  	}
  	return true;
  }
  

  這段程式跟上面，只有畫上底線的地方不一樣，

  原本我們的判斷 prime的想法是，我們挑一個數字，然後用比他小的數字去整除。

  但是仔細想想，例如我們拿

  38

  37 36 35 34 33.. 這些數字其實都不會整除 38

  所以，可以從 1 除到 x 的開根號就可以了

  那為什麼不寫 i ≤ sqrt(x) ?

  答案就是因為 sqrt 出來會有浮點數的問題

  所以直接用 i * i (兩個整數相乘會更好)

  流程

  我們在想一個題目的時候，流程是這樣的:

  1. 想法
  2. Pseudocode
  3. code
  4. improve the algorithm (NOT implementation)
  5. improve more?

  Improve more

  如果我們今天要讓整個程式運作得更快，可能就要從最初的想法開始下手改變。

  Idea2: 每當我們找到一個 prime 的時候，就把他的倍數刪掉。

  例如:

  看到 2 就把 4 6 8 10 ... 刪掉

  看到 3 就把 6 9 12 15.... 刪掉

  簡單說就是從 2 開始，把每個數字都認為是 prime

  慢慢加上去並同時刪掉他們的倍數

  Pseudocode:

  Given a Boolean array A of length n
  Initialize all elements in A to be true // assume Prime 
  
  for i from 2 to n
  	if A[i] == true
  		print i
  		for j from 1 to (n/i)// eliminating composite numbers
  			Set A[i x j] to false 
  

  所以就可以寫出 code:

  // Algorithm3
  #include<iostream>
  using namespace std;
  
  const int MAX_LEN = 10000;
  
  void ruleOutPrime(int x, bool isPrime[], int n);
  int main()
  {
  	int n = 0;
  	cin >> n;
  	bool isPrime[MAX_LEN] = {0};
  	for (int i = 2; i <= n; i++)
  	{
  		isPrime[i] = ture;
  	}
  
  	for (int i = 2; i <= n; i++)
  	{
  		if (isPrime[i] == true)
  		{
  			cout << i << " ";
  			ruleOutPrime(i, isPrime, n);
  		}
  	}
  	return 0;
  }
  
  // Function
  void isPrime(int x, bool isPrime[], int n)
  {
  	for (int i = 0; x * i < n; i++ )
  		isPrime[x * i] = false; 
  }
  

Complexity

雖然上面三個演算法，跑出來的 效力 相同

但是三者的 效率 卻不太一樣

但是效率這個詞，好像有點不太明確，所以前輩們就用了 Complexity 來決定他們的效率好不好

Time complexity : 當你程式做完的時候，花了多少的時間 。

Space complexity : 當成是做完的時候，用了多少空間。

但是要看效率好不好，也就是說要看程式跑的時間快不快，所以當 time complexity 越少，這個程式的效率就越好。

但是如果要真的比較的話，通常會用 Basic operation 的數量來比較。

(真的要數的話 會在離散數學、資料結構、演算法等等的課題中計算)

就拿Algorithm1 跟 algorithm2 來比較，可以知道，

1 運算的行數，比 2 來的要多 (因為 2 只減到 sqrt{x} 而已)

所以，2 的time complexity 會比 1 來的小，因此也比較有效率。

Recursion (Recursive functions) 遞迴

• A function is recursive if it invokes itself (directly or indirectly)(呼叫他自己)
• The process of using recursive functions is called Recursion

Ex1: Finding the Maximum

例如今天我們要從 array A[1...n] 中找到一個最大的數字 (A的長度是 n)

要怎麼找?

可以把它切成，我們先找到1 - (n-1)裡面的最大值，再去跟 n 比較

• Strategy :
• Subtask 1 : Find the Maximum of A[1 ... (n - 1)]
• Subtask 2 : Compare that with A[n]

所以當 subtask 2 很簡單、 subtask 1 也跟原本的 task 很像

因此是可以使用同一個 strategy 來解決的。

我們必須先寫一個 header:

double max(double array[], int len);

所以如果我們要解決 subtask 1 就可以這樣寫:

double subMax = max(array, len - 1);

如果按照上面的想法，我們可以寫出:

double max (double array[], int len)
{
	double subMax = max (array, len - 1);
	if (array[len - 1] > subMax)
		return array[len - 1];
	else
		return subMax; 
}
int main()
{
	double a[5] = {5, 7, 2, 4, 3};
	cout << max(a, 5);
	return 0;
}

但實際跑出來的結果會發現，這個程式好像不會結束。

原因是因為 當 len = 1 的時候，他還是會一直跑一直跑，因此

我們需要設置一個停止的方法 (Stopping condition)

而每一個 Recursion 都需要一個 stopping condition

改良後:

double max (double array[], int len){
	double subMax = max (array, len - 1);
	if (array[len - 1] > subMax)
		return array[len - 1];
	else
		return subMax; 
}
int main()
{
	double a[5] = {5, 7, 2, 4, 3};
	cout << max(a, 5);
	return 0;
}

Ex2 :Computing Factorials(階層)

Given n, how to write a function that compute the factorial of n?

• A subproblem: computing the factorial of (n-1)
• A strategy: First calculate the factorial of (n-1), then multiply it with n.

這樣就可以寫出

int factorial(int n)
{
	if (n == 1) // stopping condition
		return 1;
	else	
		// recursive call
		return factorial(n - 1) * n;	
}

當 n = 1的時候，就會 return 1
當 n = 2的時候，就會 return f(1) * 2，也就是 1 * 2
那如果今天 n = 4 的時候: 就會長成這樣:

f(4) = f(3) * 4 = f(2) * 3 * 4 = f(1) * 2 * 3 * 4 = 1 * 2 * 3 * 4 = 24

非常的EZ !

Ex3: the Fibonacci sequence

Write a recursive function to find the nth Fibonacci number!

• The F- sequence is 1, 1, 2, 3, 5, 13, 21, ...... Each number is the sum of the two proceeding numbers.
• Strategy: The nth value can be found once we know the (n-1)th and (n-2)th values

所以寫起來會長這樣:

int fib(int n)
{
	if (n == 1) // stopping condition
		return 1;
	else if (n == 2) // stopping condition
		return 1;
	else
		// recursive call
		return (fib(n - 1) + fib (n -2));
}

使用時請詳閱公開說明書

根據上面的三個例子，我們可以了解到 Recursion 在使用的時候需要注意幾項東西:

1. 每一個 recursion 都需要 stopping condition // 否則程式不會停。
2. 很多情況， recursive strategy 也可以用 loop 來解決，但有時候需要用 function 的方式來解決會比較方便。
3. 如果在相同效力的程式(equivalent Iterative function)相較， recursive function 會比較方便(簡單且好懂)。
4. 可是recursive function 會用到更多的記憶體空間，所以會比較花時間。

心得

我以前在學 python 的時候也有學過 要怎麼處理

比大小問題

但是那時候就是兩個兩個比較，像是用

tempMax 先儲存最大

再跟 realMax 比較

最後在 print realMax 就會得到最大

或是 Fibonacci sequence

可能就是直接前兩項加一加

但是學到了recursive function 之後整個變得很直觀很好懂了!

真的好酷!