版本 67d357601302b2efc50f9a93e74bd438dbb073e8
Changes from 67d357601302b2efc50f9a93e74bd438dbb073e8 to current
Week 3: Math
===========
輾轉相除法(Euclid's algorithm)
-------------------------
說明：
可以用來尋找最大公因數
方法：
利用取餘數的方法，來進行遞迴，直到a等於0爲止。
###實做
```c++
int gcd(int a,inb b)
{
if(a==0) return b;
return gcd(b%a , a);
}
```
質數(Prime Number)
-------------------------
說明：又稱素數，指某自然數除了1和該數自身外，無法被其它自然數整除。
方法：
利用建立質數表有很多種方法，對於某自然數，利用每個小於它的自然數來對它做除法，看能不能整除。以下有兩種方法，方法一是把每個數的倍數給刪除掉，方法二則是利用質數的規律性建立。方法二需要確認該數是不是質數，所以建立時間上較慢。而方法一建立時間較快，但是記憶體用較多。
###方法一：
```c++
#define MAX 1000000
bool isprime[MAX];
void Sieve()
{
memset(isprime,true,sizeof(isprime));
isprime[0] = isprime[1] = false;
for(int i = 2; i <= sqrt(MAX); i++)
if(isprime[i])
for(int j = i+=; j<MAX; j+=i)
isprime[j] = false;
}
```
###方法二：
```c++
#define MAX 1000000
vector<int> prime;
bool isPrime(int n)
{
for(int i=0; prime[i] * prime[i] <= n; i++)
if(n%prime[i] == 0)
return false;
return true;
}
void MakePrime()
{
prime.push_back(2);
prime.push_back(3);
for(int i=5,gap=2 ; i<MAX ; i+=gap, gap=6-gap)
if(isPrime(i))
prime.push_back(i);
}
```
精準度(Epsilon)
-------------------------
說明：
電腦的float跟double精準讀位數有限，因此要對比兩個不同的浮點數，需要用到eps來判斷。
float的數值範圍：-3.4e-38 ~ 3.4e38
float的十進位精準度位數：6~7
double的數值範圍：-1.7e-308 ~ 1.7e308
double的十進位精準度位數：14~15
方法：
設 eps = 1e-8（0.00000001）;
判斷相等 (a==b)：|a - b| < eps ;
判斷不相等 (a!=b)：|a - b| > eps;
判斷小於 (a<b)：a - b < -eps;
判斷大於 (a>b)：a - b > eps;
###判斷相等
```c++
void Equal(float a, float b)
{
float eps = 1e-8;
if( (fabs(a-b)) < eps)
printf("Yes\n");
else printf("No\n");
}
```
###判斷不相等
```c++
void NEqual(float a, float b)
{
float eps = 1e-8;
if( (fabs(a-b)) > eps)
printf("Yes\n");
else printf("No\n");
}
```
###判斷小於
```c++
void Less(float a, float b)
{
float eps = 1e-8;
if( (a-b) < -eps)
printf("Yes\n");
else printf("No\n");
}
```
###判斷大於
```c++
void Greater(float a, float b)
{
float eps = 1e-8;
if( (a-b) > eps)
printf("Yes\n");
else printf("No\n");
}
```
大數(Big Number)
-------------------------
說明：
基於記憶體的有效運用，程式語言中規定了各種不同的資料型態，也因此變數所可以表達的最大整數受到限制，例如123456789123456789這樣的 整數就不可能儲存在long變數中（例如C/C++、Java等），我們稱這種數為大數運算。
方法：
要讓電腦儲存大數，最好的方法就是使用陣列。一個格子存一個數字，只要宣告 1000 格大小的 int 陣列，就可以存 1000 位數了！
我們習慣講低位數放在索引值（ index ）比較小的位置，這樣的儲存方式有利於進位時的運算。
###Hint
在 考慮正負數的情況下，最高位數用來標示正負數，正數的話最高位數會是0000，負數的話最高位數會是9999，負數採10000補數，例如99為0000 0000 0000 0099，而-99為9999 9999 9999 9901，也就是用9999減99表示法每個位數，最後低數位再加1。由 於使用陣列來儲存數值，關於數值在運算時的加減乘除等各種運算、位數的進位或借位就必須自行定義，加、減、乘都是由低位數開始運算，而除法則是由高位數開 始運算。a + b時若b為負數，求b的補數c並改進行a - c；a - b時若b為負數，求b的補數c並改進行a + c，乘法與除法一律先以正數表示運算，之後再判斷正負數決定是否轉為補數。
###加法運算
大數的運算有個有趣的地方，就是運算時不用立即進位，可以後來再去一口氣進位。
```c++
void add(int a[100], int b[100], int c[100])
{
int i = 0,carry = 0;
for(i = 0; i < 100; ++i){
c[i] = a[i] + b[i] + carry;
carry = c[i] / 10;
c[i] %= 10;
}
}
```
###減法運算
```c++
void sub(int a[100], int b[100], int c[100])
{
int i = 0,borrow = 0;
for(i = 0; i < 100; ++i){
c[i] = a[i] - b[i] - borrow;
if(c[i] < 0){
borrow = 1;
c[i] += 10;
}
else
borrow = 0;
}
}
```
###乘法運算
```c++
void mul(int a[100], int b[100], int c[100])
{
int i = 0, j = 0， carry = 0;
for(i = 0; i < 100; ++i ){
if(a[i]==0) continue;
for(j = 0; j < MAX; ++j)
c[i+j] += a[i] * b[i];
}
for(i = 0; i < MAX; ++i){
carry = c[i] / 10;
c[i] %= 10;
}
}
```
###除法運算
```c++
void div(int a[100], int b[100], int c[100])
{
int t[100];
for (i = 100-1; i >= 0; i--){
for (int k=9; k>0; k--) // 嘗試商數
{
mul(b+i, k, t);
if (largerthan(a+i, t))
{
sub(a+i, t, c+i);
break;
}
}
}
}
```
