Re: [中學] 基礎計數

※ 引述《Swartz (I_Am_Swatz)》之銘言： : 從1寫到9999 : 自然數中，5一共寫了多少次? ======================================== 生成關係與遞迴解 令數列A_n = n位數字，書寫5的總次數。 初始條件: A_1 = 一位數字，書寫5的總次數。 顯然，一位數字的情況下，只有5滿足條件，書寫5的總次數為1 A_1 = 1 ----------------------------------------- 遞推的生成關係(由下而上推演): 當A_n-1 和 n-1位數字已知的時候， 我們可以在最左邊填上新的最高位，新的最高位表示符號為 "口"， 讓原本n-1位的數字成為n位數字 n位數字的表達式可以寫成: 口 串接 原本的n-1位數字 原本n-1位的數字 在 擴充完之後，原本5的書寫次數仍然存在， 而且原有的5的書寫次數恰好就是 A_n-1 。 擴充之後，相當於拷貝10份原有n-1位數字的5的書寫次數。 另一方面，當最高位 "口" 填上5的時候，又額外多書寫了5。 多了幾次5的書寫次數呢? 多了 10^(n-1)個5。 因為，最高位"口"填上5 固定之後，後面可以串接原本的n-1位數字 從 5 00...0 到 5 99...9 都是合法數字。 ^ ^ | | 最高位 最高位 從生成規則可以知道， n位數字 5的書寫次數 = A_n = 10*原本n-1位數字 5的書寫次數 + 擴充最高位之後所多出來的5的書寫次數 = 10*A_n-1 + 10^(n-1) = 5的書寫次數的遞迴關係數 其中，初始條件就是一開始提到的A_1 = 1 那麼，剩下的工作就回到離散數學，解出遞迴關係一般式的步驟 依序解出 齊次解 和 特解， 可得 通則: A_n = n * 10^(n-1), for every n >= 1. 初始條件: A_1 = 1 ======================================== 原本題目所求是 四位數字，所以n=4 代入 A_n的通則 可得 A_4 = 4 * 10^3 = 4000 四位數字，5的書寫次數為4000次。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.206.247 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1710504406.A.DD1.html