※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1710504406.A.DD1.html ※ 编辑: cuteSquirrel (114.37.206.247 台湾), 03/15/2024 20:45:12