主题数学题课件

《主题数学题课件》由会员分享，可在线阅读，更多相关《主题数学题课件（44页珍藏版）》请在装配图网上搜索。

1、主題:數學題n高斯消去法n其它數學問題n例題講解n歷年題目1聯立方程式求解n數學上很常用到n解有三種可能n唯一解n無限多組解n無解3x+2y+z=102x 3y+3z=5 x+y 2z=-3x=1y=2z=32聯立方程式求解n無解n如果等式的左邊變數係數皆為 0，而右邊常數項係數不為 0 的話，此聯立方程式無解n無限多組解n如果等式的個數比變數個數多，而且不是無解的話，此聯立方程式有無限多組解 2x+3y=104x+6y=252x+3y=100 x+0y=53高斯消去法n每次挑選一個變數的係數，由它來把其它相同變數的係數消為 03x+2y+z=102x 3y+3z=5 x+y 2z=-3(-2

2、)(-3)0 x y+7z=190 x 5y+7z=11 x+y 2z=-34高斯消去法:表示法n常用的表示法n實數表示法n整數表示法n分數表示法5實數表示法n在做高斯消去法的過程中，所有的係數皆以實數來儲存n開一個二維的實數陣列，把所有變數的係數和常數項都存在陣列中n優點n方便，好寫n缺點n精準度會有問題，容易有誤差6整數表示法n實數表示法的缺點是容易有誤差發生，誤差主要是因為除法n用整數表示法時，所有除法的動作都會被換成乘法3x+2y=102x 3y=53x+2y=102x 3y=5(-2/3)2 3(-1)3x+2y=100 x 4.3333y=-1.666676x+4y=200 x 1

3、3y=-57整數表示法n優點n沒有誤差的問題，也不難寫n缺點n因為都是乘法，乘到後來數字有可能太大n等式的係數能約分時就要約分，儘量避免數字太大8分數表示法n每一個係數都用分子和分母來表示n開兩個二維陣列，分別存每個係數的分子和分母n在運算過程中，都模仿分數的運算過程，等到最後答案算出來時，再依照題目的要求將分數做轉換n分子分母能約分的一樣可以先做約分9分數表示法3x+2y=102x 3y=5(-2/3)10例題講解:H.90.4n給一個化學的反應式，每項化合物的係數並沒有給你，題目要求你幫他算出每項化合物的係數並且要達到反應式平衡n反應式中的化合物種類為元素種類加 1，且均有唯一解n輸出的係

4、數必需皆為整數n輸出係數的最大公因數須為 111Sample input/outputnInput:C12H22O11+O2=CO2+H2OnOutput:C12H22O11+12O2=12CO2+11H2On能約分的要約到最簡n係數為 1 的不用寫出來n元素名字均為一個大寫字母12解法n題目中規定反應式中的化合物種類為元素種類加 1n化合物種類=變數個數n元素種類=等式個數n例:n四個化合物就可以設四個變數nxC12H22O11+yO2=zCO2+wH2On三個元素就可以有三個等式nC:12x=znH:22x=2wnO:11x+2y=2z+w13解法n列出等式之後，就代入高斯消去法求解n12

5、x+0y z=0wn22x+0y+0z=2wn11x+2y 2z=wn因為變數個數為等式個數加 1，所以可以把 x y z 都以 w 的某個倍數表示14解法n以分數表示法為例，解出來的結果為nx=(1/11)wny=(12/11)wnz=(12/11)wnw=(1/1)wn只要做個通分，把分數都化成整數就是答案了nx:y:z:w=1:12:12:11(別忘記約去最大公因數)15其它數學問題n常見的類型n模擬n注意 loopn找公式n數學公式nrecursive calln其它16解題技巧n數學類的問題光看題目有些會很難看出有什麼規則，遇到這類問題的時後建議用手自己跑幾個小 case，會比較容易

6、看出有沒有規則或是可以簡化的部分17奇怪的數字n給一個四位數，把這個數字的 4 個 digit 數字由大到小排成另一個四位數 A，由小到大也排成另一個四位數 B，將 A 減 B 得到另一個四位數 C，請問在做 n 次這種運算之後會得到什麼數字18解法n照著題目的意思模擬n因為四位數只有 10000 種可能，所以在 10000 步內一定會出現 loopn除了 0000、1111、9999 之外，所有的數字都會變成 617419例題講解:A.202 n給一個分數，要把這個分數化成循環小數的型式nExamplen1/6=0.1(6)括號內代表循環的部分n5/7=0.(714285)n300/31=9

7、.(677419354838709)n1/250=0.004(0)20解法n照著題目模擬n利用整數除法和 mod 來將分數化為循環小數n分母是 n 的話，mod n 只會出現 0 到 n-1 的數，所以循環小數的位數最多只會有 n 位n再算下去一定會出現之前已經出現過的餘數，產生 loop，也就可以知道從上次出現過的餘數的位置到目前的位置會產生循環21Example1/7=0.110/7=1.330/7=4.220/7=2.660/7=8.440/7=5.550/7=7.122例題講解:A.10612 n給一個整數 n(1=n=2*10100)，令 S=11+22+33+nn，試求 S 的最後

8、一個位數為多少nExamplenn=3,S=1+22+33=32，last digit=223解法n因為 n 很大，沒辦法直接模擬，要找規則化簡題目n因為只需要最後一個 digit，所以沒必要的地方可以省略n2323 的最後一個 digit 和 323 的最後一個 digit一樣n2323=(20+3)23 化簡後只有 323 這項沒有乘 20n只需要留下個位數就夠了 24解法n123456789123456789=9123456789 次方數還是太大，需要再化簡n91=9，92=81，93=729，94=6561n最後一個 digit 只會是 9 或 1n最後一個 digit 很快就會重覆出

9、現，有 loop 存在n求出最後一個 digit 的週期，次方數就可以去 mod 這個週期而把數字減小n123456789 mod 2=1，9123456789 的最後一個 digit=925解法n每個數單獨的 last digit 已經可以很快算出來，可是 S 是很多數的和，直接算還是很慢，要再化簡n只要留下最後兩個 digit 就夠了n123456789 只需要求 1 89 的和就夠了nHintn每 100 個數的和 last digit 一定為 026每 100 個數和的last digit 一定為 01122334455667788991010111112121313141415151

10、616171718181919202021212222232324242525262627272828292930303131323233333434353536363737383839394040414142424343444445454646474748484949505051552525353545455555656575758585959606061616262636364646565666667676868696970707171727273737474757576767777787879798080818182828383848485858686878788888989909091

11、91929293939494959596969797989899991001000000000000尾數之 last digit27例題講解:A.10212 n給兩個數，要求 P(n,m)的最後一個不是 0 的 digit 為多少 n0=n=20000000nm 4*8!n所有以 1 2 3 4 開頭的都會比我小n每個以 1 2 3 4 開頭後面都還有 8!種排列方法n7 比 5 個數大=5*7!n1 6 中 5 已經被用掉了n8 比 5 個數大=5*6!n1 7 中 5 6 已經被用掉了32例題講解:A.679 Dropping balln一個高度為 h 的 binary tree，每一個

12、node 上有一個開關，會決定球往左邊或是右邊掉，當這次往左邊掉之後，下次就會往右邊掉n所有的 node 一開始都設為往左邊掉n問丟第 n 顆球下去的時後會掉在哪一個 node 上n高度最多到 203334解法n照著題目模擬n速度慢n找看看有沒有規則nbinary treen一左一右35解法n以 node 1 來看，給一個數字 n，其實只要看 n mod 2 是餘 0 還是 1 就可以知道會掉在 node 1 的左邊還是右邊n餘 1 掉左邊，0 掉右邊n假設第 n 顆球掉到左邊的話，只要看看有幾顆球掉到左邊(n div 2 或 n div 2+1)，再根據判斷 node 1 的方法就可以知道在

13、 node 2 的時後最後會往哪一邊掉了n把數字以 binary number 來表示會明顯很多36例題講解:A.580n有兩種東西 L 和 U，請問在長度為 n 的所有由 L 和 U 所組成的組合中有三個 U 連在一起的個數為多少nExamplenn=4nLUUUnUUULnUUUUn共三種37解法一n用排列組合的方法解n要求有三個 U 連在一起的個數就相當於把所有的可能扣掉沒有三個 U 連在一起的個數38Example假設現在有 5 個 L 和 4 個 ULLLLLU U UUU U U UU U U UU U U U39解法一n要考慮的 case 很多，程式也不容易寫n長度若為 5，就要

14、考慮 0 5 個 U 的情況n每一種情況還要去算 U 要怎麼分堆40解法二nDP 解(recursive call)n一樣是求沒有三個 U 連在一起的解nRecurrencenL+長度為 n 1 的解nUL+長度為 n 2 的解nUUL+長度為 n 3 的解41解法二n令 Ai 為長度為 i 的解nA0=1,A1=2,A2=4nAi=Ai 1+Ai 2+Ai 342写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits43谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal