2018q1 Homework3 (list) =========================== contributed by < `BroLeaf`> ###### tags `BroLeaf` ## 生日悖論 - [ ] 自我檢查事項 ### 如何透過近似的運算式,估算上述機率計算呢?附上有效的 LaTeX 算式 有 n 個人生日不重複的機率 $P'(X) = \frac{365}{365}\times\frac{364}{365}\times\frac{363}{365}\times\frac{362}{365}\times\cdots\times\frac{366-n}{365}$ $= 1\times(1-\frac{1}{365})\times(1-\frac{2}{365})\times(1-\frac{3}{365})\times\cdots\times(1-\frac{n-1}{365})$ 引入Talor series $e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots$ $當\ X<<1時,{\displaystyle e^{x}\approx 1+x}$ 原式變為$1\times e^{-\frac{1}{365}}\times e^{-\frac{2}{365}}\times e^{-\frac{3}{365}}\times \cdots \times e^{-\frac{n-1}{365}}$ $=e^{-\frac{n(n-1/2)}{365}}=e^{-\frac{n(n-1)}{730}}$ 則有 n 個人生日會重複的機率為$1-P'(n) = 1-e^{-\frac{n(n-1)}{730}}$ ## Linux 風格的 linked list - [ ] 自我檢查事項: * 為何 Linux 採用 macro 來實作 linked list?一般的 function call 有何成本? * 參考[What is the difference between a macro and a function in C?](https://stackoverflow.com/questions/4990362/what-is-the-difference-between-a-macro-and-a-function-in-c) * Advantages * Time efficiency. * Not need to pass arguments like function. * It's preprocessed. * Easier to Read. * Disadvantages * Very hard to debug in large code. * Take more memory in stack compare to function. Suppose in the program that there a Macro which used 50 times that means it will consume memory 50 times but in function if a function is called 50 times it will take single memory every time because every time it deallocate that memory * C 語言對於 macro 的處理是在 preprocessed 這個解段,基本上可以當做是在 compile time 完成的,所以比起在 run time 才處理 function 的 push、pop 自然會更有時間上的效率,而這些勢必要多犧牲一些在 memory 的空間來達到這樣的效果