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 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 eps; 判斷小於 (ab):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; } } } } ```