这个题目的英文原题是:
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?
翻译过来大体是这样：
有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？
为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.
请大家写出自己的算法，并统计一些在你机器上计算出1111111110的时间。为了不影响大家的思路，我最后贴上我的程序。
语言不限，随便了。
CSDN论坛帖子链接：
---------------------------------------------
我在原题的基础上“增加了难度”，即求出小于MAX的所有f(n)=n的数。
程序运行结果：
dex_c:2485 dex_f:4960 time:30
递归调用2485次，计算某个数的1的个数4960次（包括84次打印时的验证dummy调用），耗时30ms
说明：
foo--某个数的1的个数，我本来写了一个，原理一样，但代码没有这么漂亮，比较长，所以干脆直接用帖子里的一个算法；
思路--从1到MAX步长逐渐增大的2分法。
---------------------------------------------
[code]#include <stdio.h>
#include<windows.h>
typedef unsigned long number_t;
int count=0;
int dex_c=0;
int dex_f=0;
number_t foo(number_t n)
{
dex_f++;
number_t num, k, r, d;
number_t x;
for(num = k = r = 0, d = 1; n; n /= 10) {
x = n % 10;
num += x * k + (x > 1 ? d : (x == 1 ? r + 1 : 0));
r += x * d;
k = k * 10 + d;
d *= 10;
}
return num;
}
inline void found(number_t x)
{
printf("%d: f(%d)=%d\n",count+1,x,foo(x));count++;
}
void scan(number_t a,number_t b)
{
// printf("scan %d %d\n",a,b);
if ((a>b)||(a<0)||(b<0)) return;
dex_c++;
number_t an=foo(a);
if (a==an) found(a);
if (a==b) return;
number_t bn=foo(b);
number_t k=a+(b-a)/2;
if ((a>bn) || (b<an)) return;
if (k>=(a+1)) scan(a+1,k);
if ((k+2)<=b) scan(k+1,b-1);
if (b==bn) found(b);
}
int main ()
{
int t=GetTickCount();
const number_t MAX=3000000000L;
number_t n=1;
number_t i;
number_t k=1,p=1;
found(0);
while(1)
{
n=n*10;
for (i=1;i<=9;i++)
{
p=k;
k=i*n;
if (k>=MAX)
{
scan(p,MAX);
t=GetTickCount()-t;
printf("dex_c:%d dex_f:%d time:%d\n", dex_c, dex_f, t);
getchar();
return 0;
}
scan(p,k-1);
}
}
}[/code]
