分享到plurk 分享到twitter 分享到facebook

版本 e687e0fa4dfcbdc5d534b11ba05e378c50244d49

acm/course/Math

Changes from e687e0fa4dfcbdc5d534b11ba05e378c50244d49 to 722082d466d9a8862bb7ef861806a72c0623ea07

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)
精準度(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(double a, double b)
{
        double eps = 1e-8;
        if( fabs(a-b) < eps)
                printf("Yes\n");
        else printf("No\n");
}
```
###判斷不相等
```c++
void NEqual(double a, double b)
{
        double eps = 1e-8;
        if( fabs(a-b) > eps)
                printf("Yes\n");
        else printf("No\n");
}
```
###判斷小於
```c++
void Less(double a, double b)
{
        double eps = 1e-8;
        if( a-b < -eps)
                printf("Yes\n");
        else printf("No\n");
}
```
###判斷大於
```c++
void Greater(double a, double b)
{
        double 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 )比較小的位置,這樣的儲存方式有利於進位時的運算。

###加法運算:
###加法運算
```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;
                }
            }
        } 
}
```