1.
long int a, b, c;
a= 40000L;
b= 60000L;
c= a*b;
printf("c= %ld\n", c);
// 請問，c= ???, why?
這題要注意的是：
- long int 的大小是 4 bytes (32 bits)或 8 bytes (64 bits)，所以 signed long int能表現的最大值為 2^31-1 = 2147483647 (32 bits) 或 2^63-1 = 9223372036854775807L (64 bits)
- 所以如果是在64 bit 電腦上，c當然沒有疑問是2400000000L。可是在32 bit電腦上，這個數字已經超過該type可以表示的極限，所以就會造成溢位(overflow)。
- 可是overflow之後的表現屬於undefined behaviour，意思是說編譯器怎麼做都可以。
2.
long a, b, c;
a= 10;
b= a + 1;// b= 11, > a
while (b > a) {
a++;
b+= 1;
}
printf("a= %ld, b= (a+1)= %ld\n", a, b);
// 請問， a= ???, b= ???, why?
- 這個問題比較簡單，同上一題，會run到溢位為止。
- 至於溢位以後的動作一樣是undefined behaviour
(我的電腦跑出的結果是a= 9223372036854775807, b= (a+1)= -9223372036854775808 )
3.
double a, b, c;
a= 4.0*atan(1.0);// a= 3.1415926 ...
b= a + 1.0;// b= 4.1415926 ..., > a
while (b > a) {
a*= 1.001;
b= a + 1.0;
}
printf("a= %.3lf, b= (a + 1.0)= %.3lf\n", a, b);
// 請問：a= ???, b= ???, why?
- standard C 並沒有規定浮點數的儲存方式，這跟各家平台對於浮點數的儲存有關，也就是說跑出的結果是implementation defined。我的機器跑出的結果是
a= 9026451774346548.000, b= (a + 1.0)= 9026451774346548.000
- 若浮點數為 IEEE754 則答案會在剛超過 2^53 (9007199254740992) 時停止。
4.
1 不是質數，請問：從 1 to 1,000,000
一共有幾個質數？
使用 什麼方法最快？
你的計算時間是多少？精確度要 小於 0.1秒。
這題有幾個重點：
- 計算時間：C的time.h 只能提供精確度到秒級的時間處理。若需要毫秒級的時間處理可使用Linux提供的<sys/time.h>
http://jyhshin.pixnet.net/blog/post/26587986-linux-%E6%99%82%E9%96%93%E8%99%95%E7%90%86
- 找質數不外乎兩種方法：
循序搜尋法(Sequential Search)：一個一個跟找到的質數比較看能不能整除，不能就加入質數List...時間複雜度為O(N^2)
篩法(Sieve of Eratosthenes)：把已經找到的質數倍數先篩去，再從剩下的找質數再繼續篩(快多了)。時間複雜度為O(NloglogN)
以下為我用這兩種算法做的參考答案(使用C)：
https://gist.github.com/gnitnaw/9db341d4588ff5431c45
5.
100 的 階乘是多少？
要精確到 每一位？
這裡要用大數進行計算(int和long都不夠位數)。
我是直接創造一個可以擁有無限位數的class
https://gist.github.com/gnitnaw/79ccbac48a22e14b67c4
得到結果：
100!= 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
6.
強迫使用遞回呼叫的方式求 費氏數列。
第幾項： 0, 1, 2, 3, 4, 5
答案： 1, 1, 2, 3, 5, 8, 13, . . .
請問：第 100項的答案是 多少？
必須精確到 每一個 位數，
請問：你的程式 需要花多少時間完成？
精確度要 小於 0.1秒
這題不但要用大數計算還要推估大概計算時間
我是算到N=35以後用T(N)=T(N-1)+T(N-2)推算N=100的情況。
答案：
F(100) = 354224848179261915075，
所需時間推估為247170233002558582087us ~ 247170233002558582 ms
(靠！要7837716年)
7.
使用 辛普森的方法求 數值積分，
y= sin(x), x= 0 to pi 的積分值是多少？
pi= 4.0*atan(1.0)
小數點的要求是 %.22lf
0 to pi 的等分 區間數量是 n
n= 10 to 50 step 2
求出 每一個 n 所對應的 積分值？
這個不算難，一下子就寫出來了
https://gist.github.com/gnitnaw/56c6686fcbeb0c9eb3ed
N = 10, Surface = 2.0000067844418008000673
N = 12, Surface = 2.0000032688771600675182
N = 14, Surface = 2.0000017635025444384667
N = 16, Surface = 2.0000010333694131503535
N = 18, Surface = 2.0000006449719771595142
N = 20, Surface = 2.0000004230931827109430
N = 22, Surface = 2.0000002889414907336629
N = 24, Surface = 2.0000002039921938035150
N = 26, Surface = 2.0000001480922562357989
N = 28, Surface = 2.0000001100950042243198
N = 30, Surface = 2.0000000835398590304237
N = 32, Surface = 2.0000000645300017865225
N = 34, Surface = 2.0000000506327708649223
N = 36, Surface = 2.0000000402833366663913
N = 38, Surface = 2.0000000324482267721748
N = 40, Surface = 2.0000000264287591811296
N = 42, Surface = 2.0000000217426348037009
N = 44, Surface = 2.0000000180506227742683
N = 46, Surface = 2.0000000151100518763769
N = 48, Surface = 2.0000000127446351250171
N = 50, Surface = 2.0000000108245044039279
參考資料：
- http://www.csie.ntnu.edu.tw/~u91029/Prime.html
- PTT C_AND_CPP 精華區
沒有留言:
張貼留言