欢迎来到三一文库! | 帮助中心 三一文库31doc.com 一个上传文档投稿赚钱的网站
三一文库
全部分类
  • 研究报告>
  • 工作总结>
  • 合同范本>
  • 心得体会>
  • 工作报告>
  • 党团相关>
  • 幼儿/小学教育>
  • 高等教育>
  • 经济/贸易/财会>
  • 建筑/环境>
  • 金融/证券>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 三一文库 > 资源分类 > PPT文档下载
     

    主题数学题.ppt

    • 资源ID:2714641       资源大小:253.01KB        全文页数:43页
    • 资源格式: PPT        下载积分:6
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录   微博登录  
    二维码
    微信扫一扫登录
    下载资源需要6
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    主题数学题.ppt

    1,主題: 數學題,解題技巧 高斯消去法 其它數學問題 例題講解 歷年題目,2,聯立方程式求解,數學上很常用到 解有三種可能 唯一解 無限多組解 無解,3x + 2y + z = 10,2x 3y + 3z = 5,x + y 2z = -3,x = 1,y = 2,z = 3,3,聯立方程式求解,無解 如果等式的左邊變數係數皆為 0,而右邊常數項係數不為 0 的話,此聯立方程式無解 無限多組解 如果等式的個數比變數個數多,而且不是無解的話,此聯立方程式有無限多組解,2x + 3y = 10,4x + 6y = 25,2x + 3y = 10,0x + 0y = 5,4,高斯消去法,每次挑選一個變數的係數,由它來把其它相同變數的係數消為 0,3x + 2y + z = 10,2x 3y + 3z = 5,x + y 2z = -3,× (-2),× (-3),0x y + 7z = 19,0x 5y + 7z = 11,x + y 2z = -3,5,高斯消去法: 表示法,常用的表示法 實數表示法 整數表示法 分數表示法,6,實數表示法,在做高斯消去法的過程中,所有的係數皆以實數來儲存 開一個二維的實數陣列,把所有變數的係數和常數項都存在陣列中 優點 方便,好寫 缺點 精準度會有問題,容易有誤差,7,整數表示法,實數表示法的缺點是容易有誤差發生,誤差主要是因為除法 用整數表示法時,所有除法的動作都會被換成乘法,3x + 2y = 10,2x 3y = 5,3x + 2y = 10,2x 3y = 5,8,整數表示法,優點 沒有誤差的問題,也不難寫 缺點 因為都是乘法,乘到後來數字有可能太大 等式的係數能約分時就要約分,儘量避免數字太大,9,分數表示法,每一個係數都用分子和分母來表示 開兩個二維陣列,分別存每個係數的分子和分母 在運算過程中,都模仿分數的運算過程,等到最後答案算出來時,再依照題目的要求將分數做轉換 分子分母能約分的一樣可以先做約分,10,分數表示法,3x + 2y = 10,2x 3y = 5,× (-2/3),11,例題講解: H.90.4,給一個化學的反應式,每項化合物的係數並沒有給你,題目要求你幫他算出每項化合物的係數並且要達到反應式平衡 反應式中的化合物種類為元素種類加 1,且均有唯一解 輸出的係數必需皆為整數 輸出係數的最大公因數須為 1,12,Sample input/output,Input: C12H22O11 + O2 = CO2 + H2O Output: C12H22O11 + 12O2 = 12CO2 + 11H2O 能約分的要約到最簡 係數為 1 的不用寫出來 元素名字均為一個大寫字母,13,解法,題目中規定反應式中的化合物種類為元素種類加 1 化合物種類 = 變數個數 元素種類 = 等式個數 例: 四個化合物就可以設四個變數 xC12H22O11 + yO2 = zCO2 + wH2O 三個元素就可以有三個等式 C: 12x = z H: 22x = 2w O: 11x + 2y = 2z + w,14,解法,列出等式之後,就代入高斯消去法求解 12x + 0y z = 0w 22x + 0y + 0z = 2w 11x + 2y 2z = w 因為變數個數為等式個數加 1,所以可以把 x y z 都以 w 的某個倍數表示,15,解法,以分數表示法為例,解出來的結果為 x = (1/11) w y = (12/11) w z = (12/11) w w = (1/1) w 只要做個通分,把分數都化成整數就是答案了 x: y: z: w = 1: 12: 12: 11 (別忘記約去最大公因數),16,其它數學問題,常見的類型 模擬 注意 loop 找公式 數學公式 recursive call 其它,17,解題技巧,數學類的問題光看題目有些會很難看出有什麼規則,遇到這類問題的時後建議用手自己跑幾個小 case,會比較容易看出有沒有規則或是可以簡化的部分,18,奇怪的數字,給一個四位數,把這個數字的 4 個 digit 數字由大到小排成另一個四位數 A,由小到大也排成另一個四位數 B,將 A 減 B 得到另一個四位數 C,請問在做 n 次這種運算之後會得到什麼數字,19,解法,照著題目的意思模擬 因為四位數只有 10000 種可能,所以在 10000 步內一定會出現 loop 除了 0000、1111、9999 之外,所有的數字都會變成 6174,20,例題講解: A. 202 http:/acm.uva.es/p/v2/202.html,給一個分數,要把這個分數化成循環小數的型式 Example 1/6 = 0.1(6) 括號內代表循環的部分 5/7 = 0.(714285) 300/31 = 9.(677419354838709) 1/250 = 0.004(0),21,解法,照著題目模擬 利用整數除法和 mod 來將分數化為循環小數 分母是 n 的話, mod n 只會出現 0 到 n-1 的數,所以循環小數的位數最多只會有 n 位 再算下去一定會出現之前已經出現過的餘數,產生 loop,也就可以知道從上次出現過的餘數的位置到目前的位置會產生循環,22,Example,1/7 = 0 . 1 10/7 = 1 . 3 30/7 = 4 . 2 20/7 = 2 . 6 60/7 = 8 . 4 40/7 = 5 . 5 50/7 = 7 . 1,23,例題講解: A. 10612 http:/acm.uva.es/p/v106/10612.html,給一個整數 n (1 = n = 2*10100),令 S=11 + 22 + 33 + + nn,試求 S 的最後一個位數為多少 Example n = 3, S = 1 + 22 + 33 = 32,last digit = 2,24,解法,因為 n 很大,沒辦法直接模擬,要找規則化簡題目 因為只需要最後一個 digit,所以沒必要的地方可以省略 2323 的最後一個 digit 和 323 的最後一個 digit一樣 2323 = (20 + 3)23 化簡後只有 323 這項沒有乘 20 只需要留下個位數就夠了,25,解法,123456789123456789 = 9123456789 次方數還是太大,需要再化簡 91 = 9,92 = 81,93 = 729,94 = 6561 最後一個 digit 只會是 9 或 1 最後一個 digit 很快就會重覆出現,有 loop 存在 求出最後一個 digit 的週期,次方數就可以去 mod 這個週期而把數字減小 123456789 mod 2 = 1,9123456789 的最後一個 digit = 9,26,解法,每個數單獨的 last digit 已經可以很快算出來,可是 S 是很多數的和,直接算還是很慢,要再化簡 只要留下最後兩個 digit 就夠了 123456789 只需要求 1 89 的和就夠了 Hint 每 100 個數的和 last digit 一定為 0,27,每 100 個數和的last digit 一定為 0,尾數之 last digit,28,例題講解: A. 10212 http:/acm.uva.es/p/v102/10212.html,給兩個數,要求 P(n, m) 的最後一個不是 0 的 digit 為多少 0 = n = 20000000 m = n Hint 會產生 0 的就是 2 和 5 的乘積 把 2 和 5 配對之後消去,剩下的再去求最後一個 digit 就好,29,k = 0; Z = 1; for i = n to n - m + 1 do z = i; while (z mod 2) = 0) k+; z = z mod 2; while (z mod 5) = 0) k-; z = z mod 5; Z=(Z*z) mod 10 Answer: (Z*2|k|) mod 10 如果 2 的個數比 5 多 (Z*5|k|) mod 10 如果 5 的個數比 2 多,30,數字排列的大小,給一個由 1 9 所排列出來的數字,請問這是在所有排列中第幾大的數字 123456789 最小的 123495678 第 97 小的,31,解法,由左到右看,假設由自己開始到最右邊還剩下 n 個數字,而自己在這些數中比 m 個數還大,則自己所算出來的數字為 m * (n 1)!) 把所有的數加起來就是自己還比幾個數字還要大,32,Example,578123694 5 比 4 個數大 = 4 * 8! 所有以 1 2 3 4 開頭的都會比我小 每個以 1 2 3 4 開頭後面都還有 8! 種排列方法 7 比 5 個數大 = 5 * 7! 1 6 中 5 已經被用掉了 8 比 5 個數大 = 5 * 6! 1 7 中 5 6 已經被用掉了,33,例題講解: A. 679 http:/acm.uva.es/p/v6/679.html,Dropping ball 一個高度為 h 的 binary tree, 每一個 node 上有一個開關,會決定球往左邊或是右邊掉,當這次往左邊掉之後,下次就會往右邊掉 所有的 node 一開始都設為往左邊掉 問丟第 n 顆球下去的時後會掉在哪一個 node 上 高度最多到 20,34,35,解法,照著題目模擬 速度慢 找看看有沒有規則 binary tree 一左一右,36,解法,以 node 1 來看,給一個數字 n,其實只要看 n mod 2 是餘 0 還是 1 就可以知道會掉在 node 1 的左邊還是右邊 餘 1 掉左邊,0 掉右邊 假設第 n 顆球掉到左邊的話,只要看看有幾顆球掉到左邊 (n div 2 或 n div 2 +1),再根據判斷 node 1 的方法就可以知道在 node 2 的時後最後會往哪一邊掉了 把數字以 binary number 來表示會明顯很多,37,例題講解: A. 580 http:/acm.uva.es/p/v5/580.html,有兩種東西 L 和 U,請問在長度為 n 的所有由 L 和 U 所組成的組合中有三個 U 連在一起的個數為多少 Example n = 4 LUUU UUUL UUUU 共三種,38,解法一,用排列組合的方法解 要求有三個 U 連在一起的個數就相當於把所有的可能扣掉沒有三個 U 連在一起的個數,39,Example,假設現在有 5 個 L 和 4 個 U,U,U,U,U,U,U,U,U,40,解法一,要考慮的 case 很多,程式也不容易寫 長度若為 5,就要考慮 0 5 個 U 的情況 每一種情況還要去算 U 要怎麼分堆,41,解法二,DP 解 ( recursive call) 一樣是求沒有三個 U 連在一起的解 Recurrence L + 長度為 n 1 的解 UL + 長度為 n 2 的解 UUL + 長度為 n 3 的解,42,解法二,令 Ai 為長度為 i 的解 A0 = 1, A1 = 2, A2 = 4 Ai = Ai 1 + Ai 2 + Ai 3,43,歷年題目,練習題 A. 202 Repeating Decimals http:/acm.uva.es/p/v2/202.html A. 10612 Last digit http:/acm.uva.es/p/v106/10612.html A. 10212 The last non-zero digit http:/acm.uva.es/p/v102/10212.html A. 679 Dropping ball http:/acm.uva.es/p/v6/679.html A. 580 Critical mass http:/acm.uva.es/p/v5/580.html 挑戰題 A. 254 Towers of Hanoi http:/acm.uva.es/p/v2/254.html A. 10232 Bit-wise Sequence http:/acm.uva.es/p/v102/10232.html A. 10049 Selfdescribing Sequence http:/acm.uva.es/p/v100/10049.html A. 10479 Hendrie Sequence http:/acm.uva.es/p/v104/10479.html 其它歷年題目 H.90.4,

    注意事项

    本文(主题数学题.ppt)为本站会员(本田雅阁)主动上传,三一文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一文库(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    经营许可证编号:宁ICP备18001539号-1

    三一文库
    收起
    展开