又有一個大老曾經說過 :
Programming = Data structures + Algorithms
Data structure 在這邊先不提
會先說明 Algorithms 演算法的淺薄概念
簡單說，就是要設計一系列的動作，最後達成我們想要的目標，這就是演算法。
最簡單的來說，可以把一個大問題 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:
(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 (兩個整數相乘會更好)
我們在想一個題目的時候，流程是這樣的:
如果我們今天要讓整個程式運作得更快，可能就要從最初的想法開始下手改變。
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 來決定他們的效率好不好
Time complexity : 當你程式做完的時候，花了多少的時間 。
Space complexity : 當成是做完的時候，用了多少空間。
但是要看效率好不好，也就是說要看程式跑的時間快不快，所以當 time complexity 越少，這個程式的效率就越好。
但是如果要真的比較的話，通常會用 Basic operation 的數量來比較。
(真的要數的話 會在離散數學、資料結構、演算法等等的課題中計算)
就拿Algorithm1 跟 algorithm2 來比較，可以知道，
1 運算的行數，比 2 來的要多 (因為 2 只減到 sqrt{x} 而已)
所以，2 的time complexity 會比 1 來的小，因此也比較有效率。
例如今天我們要從 array A[1...n] 中找到一個最大的數字 (A的長度是 n)
要怎麼找?
可以把它切成，我們先找到1 - (n-1)裡面的最大值，再去跟 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;
}
Given n, how to write a function that compute the factorial of 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 !
Write a recursive function to find the nth Fibonacci number!
所以寫起來會長這樣:
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 在使用的時候需要注意幾項東西:
我以前在學 python 的時候也有學過 要怎麼處理
比大小問題
但是那時候就是兩個兩個比較，像是用
tempMax 先儲存最大
再跟 realMax 比較
最後在 print realMax 就會得到最大
或是 Fibonacci sequence
可能就是直接前兩項加一加
但是學到了recursive function 之後整個變得很直觀很好懂了!
真的好酷!
iThome鐵人賽
看影片追技術