1的数目

前言问题描述解法一解法二总结

前言

今天记录一下昨天折磨了我一下午的一个算法小题：1的数目。

问题描述

解法一

okok，虽然我觉得一定不会那样简单，但首先想到的还是最直接、最简单的方法。一个一个数字的数。

int NumOf1(int num) { int n = 0; while(num>0){ int v = num%10; //余数 num = num / 10; //商 if(v == 1) ++n; } return n; } int TestFn(int N) { fn[0] = 0; for(int i = 1;i<MAXSIZE;++i) { fn[i] = fn[i-1] + NumOf12(i); } }

分析：一句话评价，简单粗暴不高效。

解法二

其实，有些时候，当我们拿到问题的时候没有思路，不妨写出前面几个简单的例子试一试，想一想，没准思路就慢慢出来了。 比如说这题：1的数目 1 10 11 12 13 14 15 16 …19 21 31 41 51 …91 100 101 102 … …

eeeee… 没有什么太大规律啊.如何求F（N）呢，比如说求F(215) = ？

乍一看，是没有什么规律的，但如果我们转变思路，纵向来看，把小于等于N的数进行分类，个位数中含有的1放在一类，十位数中含有1的放在一类，百位数中含有1的放在一类…规律就出来了

比如说，N=215，小于等于它的数中 (1)、个位数中含有1的有 1 11 21 31 …91 101 111 … 191 201 211

(2)、十位数中含有1的有： 10 11 12 … 19 110 111 112 … 119

(3)、百位中含有1的有： 100 101 102 …199

注意上面的类似11的数，个位十位都进行了统计，但是11原本也是需要被统计两次的，所以没影响。

你会发现这样的规律： （1）、在个位数的统计中，数字每增加10，就来1个个位数为1的，如1 11 21 … （2）、在十位数的统计中，数字每增加100，就来10个十位数为1的，如(10 11 12…19) 到（110, 111 112 … 119 ）… (3)、在百位数的统计中，数字没增加1000，就会出现100个百位数字为1的，如（100 101 102 … 199）到 (1100 1101 … 1199) …

然后按照这个规律就可以推出公式进行编码了（当然要注意边界条件）

//计算小于等于num的书中，第p位中含有1的数目（0代表个位，1代表十位...） int NumOfOneByDig(int num,int p) { int pow1 = pow(10,p); int pow2 = pow(10,p+1); int A = (num ) / pow2 * pow1; int B = (num%pow2)-pow1; int C = 0; if(B < 0){ C = 0; }else if(B >=0 && B<= (pow1-1)){ C = B+1; }else C = pow1; return A+C; } //统计1的个数 int NumOfOne(int num) { int tmp = num; int p = 0; int sum = 0; while(tmp>0) { tmp = tmp / 10; sum+=NumOfOneByDig(num,p); ++p; } return sum; }

分析：(1)、上面NumOfOneByDig()应用到的公式为 可能和你推的形式不一样，但只要最后结果正确应该就没问题了。 （2）、上面求幂的时候，用的是库函数，其实还可以放在NumOf函数进行优化，不是重点，这里就不赘述了。

总结

花的大部分时间都是在推导那个公式上，虽然最终的形式不是很复杂。但是推倒的时候确实花费了我不少精力，哎，我爱数学千百遍，数学虐我如常见。￣□￣｜｜