《编程之美》中有一个求1出现次数的问题，给定一个十进制正整数N，写下从1到N的所有正整数，然后数一下其中1出现的次数；如果将这个问题稍微改变一下，要求数一下其中含有1的数字的个数；比如N=12，f(N)=4,(1, 10, 11, 12)
看起来问题基本一样，但实际上两者还是有很大的不同的，改变后的问题应该说是一个排列组合问题；
这里给出一种解法：
首先现将问题转化为：求不含1的数的个数
设N=high ow
从最高位high开始，设当前共有bit+1位
1. 求出0~high999..之间不含1的数的个数，由组合问题可知，一共有：high*9^bit..,个
2. 由1求出的数，由于多计算了N+1~high999这些数字，需要将这些数字减去
2.1 如果high=1，那么这些数字都含1，直接忽略;
2.2 否则：
考虑到这些数字的最高为都是high，且不为1，可以略去，因此就变为了计算F(999..)-F(low);
F(999..)容易计算，值为9^bit；
算法复杂度是O(bit)，可视为常数；
现在求出了0～N之间不含1的数字个数；0～N一共有N+1个数字
那么f(N) = N+1 - F(N)
根据思路写出程序如下：
扫一扫
2573
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
