问题明确而简单.for循环肯定是不好的.
用递推方法:
定义h(n)=从1到9999.....9999 ( n 个 9)之间含有1的数字的个数.定义f(n)为n位数中含有1的数字的个数.
由定义可知:h(n)=f(1)+f(2)+f(3)+....+f(n);
则f(1)=h(1)=1;
f(2)=10^1+8*h(1).
f(3)=10^2+8*h(2).
f(4)=10^3+8*h(3).
......
意义如下:f(4)是一个四位数,假如最高位(千位)为1,那么后面是啥都行,这个数字必然有1了,所以是10^3.
假如最高位不是1,最高位不能是0(不然就成3位数了),所以最高位有8种选择2,3,4,5,6,7,8,9.这样一来,低三位中必须含有1,要不然就没有一了.所以乘上h(3).
下面举一个例子,求1到2345之间含有1数字的个数.
2345=h(1)+h(2)+h(3)+h(4)的一部分.
关键是h(4)的一部分应该怎么求.定义p(4,2)表示是四位数并且虽高位小于2的数中含有1的个数.p(4,2)=10^3+p(3,3);看到这里就应该明白了.p(3,3)表示三位数中最高位小于3的含1数字的个数.