算法题一道

---

    算法题一道，计算连续自然数序列中‘1’出现的次数。
    作者：tyc611.cublog.cn，2008-10-05

---

【问题描述】
（1）对于一个整数n，写一个函数f(n)，使得它返回1到n之间的所有自然数（十进制数表示）中出现的‘1’的次数。例如，对于n=13，自然数1，2，3，4，5，6，7，8，9，10，11，12，13中‘1’出现的次数为6，所以f(13) = 6。
（2）找出满足f(n)=n的最大n值。

【问题分析】
这个问题在《编程之美》中有所讨论，虽然最终给出了正确答案，但解答过程并不严谨。另外，对于第二个问题的求解效率也太低了。

这个问题曾经在CU的C/C++版讨论过，网友给出了很好的解答。其中，最有效的解法是网友yzc2002给出的算法，并给出了严谨的证明过程。下面图中内容即为他给出的分析证明过程：

上面的讨论中，f(10^k-1)=k*10^(k-1)是一个很重要的结论。
对于上面分析的最后一步（f(n)
实现代码如下（修改自yzc2002的代码）：
#include

long long f(long long n)
{
    int k;
    long long e, r, m;
   
    if (n <= 1)
        return n;
   
    for (k = 0, e = 1, m = n; m >= 10; ++k, e *= 10)
        m /= 10;
    r = n - m * e;
   
    return m == 1 ? (e / 10 * k + r + 1 + f(r)) : (e / 10 * k * m + e + f(r));
}

int digit_num(long long n)
{
    int k;
    for (k = 0; n > 0; ++k)
        n /= 10;
    return k;
}

int main()
{
    int count = 0;
    long long n;
   
    for (n = 1; n < 10000000000LL;)
    {
        long long v = f(n);
        if (v == n) {
            printf("%lld\n", n);
            ++n;
            ++count;
        }
        else if(v > n)
            n = v;
        else {
            int k = digit_num(n + n - v);
            n += (n - v) / k + 1;
        }
    }
   
    printf("Total: %d\n", count);
   
    return 0;
}

运行结果如下：
-bash-3.00$ time ./a.out
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998
35000000
35000001
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199988
35199989
35199990
35200000
35200001
117463825
500000000
500000001
500199981
500199982
500199983
500199984
500199985
500199986
500199987
500199988
500199989
500199990
500200000
500200001
501599981
501599982
501599983
501599984
501599985
501599986
501599987
501599988
501599989
501599990
502600000
502600001
513199998
535000000
535000001
535199981
535199982
535199983
535199984
535199985
535199986
535199987
535199988
535199989
535199990
535200000
535200001
1111111110
Total: 83

real    0m0.026s
user    0m0.016s
sys     0m0.010s

对于f函数的实现，由于是一个尾递归，很容易改成一个非递归版本：
long long f2(long long n)
{
    int k;
    long long e, r, m;
    long long result = 0;
   
    while (n > 0) {
        for (k = 0, e = 1, m = n; m >= 10; ++k, e *= 10)
            m /= 10;
        r = n - m * e;
        result += e / 10 * k * m + (m == 1 ? r + 1 : e);
        n = r;
    }
   
    return result;
}

---