Day 15 - 演算大法好ㄟ

简介

又有一个大老曾经说过 :

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));
}