一张纸上写着1到9999所有的数。一只老鼠（名叫Jenny ）把所有的数字0都吃掉了。例如6012变成了两个数6和12。吃完之后Jenny很快就算出剩下所有数的和。Jenny是怎么算的？和是多少？
下面是我的解答。Jenny一定有更好的办法，可惜她不告诉我们。
设F(n)是1到n个9的数，0被吃掉后的和（我们求的是F(4)），G(n)是所有不含0的n位数的和。F(n)由下面几部分组成：不含0的n位数，最后一位是0的数，最后一位不是0，倒数第2位是0的数，最后两位不是0，倒数第3位是0的数，等等。有下列递归关系：
F(n) = G(n) + F(n-1) + (9*F(n-2) + 10^(n-2)*G(1)) + ... + (9^(n-2)*F(1) + 10*G(n-2)) + G(n-1)
化简后得
F(n) = G(n) + a_1*G(n-1) + a_2*G(n-2) + ... + a_(n-1)*G(1),
其中 a_k = (10^k-1)*2/9 - k + 1，及 G(n) = 5*(10^n - 1)*9^(n-1)，这样可以算出任意F(n)。对我们的题，有
F(4) = G(4) + 2G(3) + 21G(2) + 220G(1)
G(1) = 45
G(2) = 4455
G(3) = 404595
G(4) = 36446355
所以 F(4) = 37359000。
Jenny 太笨了[:%][:%][:((][:((] 本贴由[Jenny]最后编辑于：2005-11-23 14:24:50 |
只是想让更多人看看有没有更好的解。 你的题目对我来说本来就偏难，偶而看到相对容易的，化力气做了你也常看不上眼，俺自信心受挫，以后更不敢做了。 |
你再冤枉我六月要下雪了！ 这样的意见, 我也不会说了 . |
查了一下出题的地方，答案是10^n * ((9^n - 8n - 1)*729/1280 + 9n/2)。 说是用差分方程解的。 Jenny会差分方程，我们不会。 |
| 欢迎光临 珍珠湾ART (http://66.160.158.134/) | Powered by Discuz! X3 |