求解f(n)=n
davies 发表于 2005 年 11 月 11 日
有这样一个函数 f(n)，对于任意正整数n，它表示从 0 到 n 之间出现“1”的个数，比如 f(1) = 1, f(13) = 6, 那么下一个能实现 f(n) = n 的数字是什么?
最笨的办法就是用程序暴力求解，不断地计算 f(n)，并检验 f(n)=n是否成立，可以得到如下的结果：
- f[000000001] = 1
- f[000199981] = 199981
- f[000199982] = 199982
- f[000199983] = 199983
- f[000199984] = 199984
- f[000199985] = 199985
- f[000199986] = 199986
- f[000199987] = 199987
- f[000199988] = 199988
- f[000199989] = 199989
- f[000199990] = 199990
- f[000200000] = 200000
- f[000200001] = 200001
- f[001599981] = 1599981
- f[001599982] = 1599982
可以看出下一个n是199981，满足f(n) = n。
不用程序，手算也可以求解。f(n) = n 表示 y = f(n) 和 y = n 的交点，通过观察 y = f(n) 的变化可以估计交点的范围。f(n) 的一些关键点如下：
- f(9) = 1
- f(99) = 20
- f(999) = 300
- f(9999) = 4000
- f(99999) = 50000
- f(999999) = 600000
这是非常有规律的，同时另外一些观点如下：
- f(19) = 12 (f(9)*2 + 1*10 )
- f(199) = 140 (f(99)*2 + 1*100)
- f(1999) = 1600 (同上)
- f(19999) = 18000
- f(199999) = 200000
- f(1999999) = 2200000
它也是很有规律的，它们分别是 y = f(n) - n 的局部极小值点和极大值点。
由于 f(99999) = 50000 < 99999 而 f(199999) = 200000 > 199999, 则这区间内必有交点
199991中包含两个1，它之前的199981也包含两个1，则当 199981 <= n < 199991 时，都有 f(n) = n 成立。199981即为要求的下一个满足条件的数。