【题目】输入一个整数n,求从1到n这n个正数中,x出现的次数。x是1,2,...,9中任意一个。
例如:输入12,x=1,出现一的数字有1,10,11,12共有5个1,则输出5。
输入12,x=2,出现一的数字有2,12共有2个2,则输出2。
输入12,x=3,出现一的数字有3共有1个3,则输出1。
【分析】
网络上流传很广的一道题和它很像:输入一个整数n,求从1到n这n个正数中,1出现的次数。例如:输入12,出现一的数字有1,10,11,12共有5个1,则输出5。
此题是笔者研究了网络上的那道以后自己搞的扩展。
简单方法不再赘述,这里只讨论扩展算法。思路和网络上那道一样,分别计算各位、十位、百位、千位、...上每一位中可能出现的x的个数,然后相加即可。
对于x=1的情况,推荐http://www.cnblogs.com/python27/archive/2011/12/14/2288205.html给出了规律分析,一下转引了该文章的分析部分:
=================================================================================
首先,我们有如下比较容易得到的结论,0-9中1的个数是1个,0-99中十位(10-19)上1的个数是10,0-999中百位上(100-199)上1的个数是100,以此类推。为什么需要这些数字,我们经过简单罗列,很容易发现:个位上1的个数,实际上和这个数字包含多少个10有关,因为对于个位来说,总是从0-9循环,十位上1的个数,实际上和这个数字包含多少个100有关,因为每包含1个100,就有0-99的循环,而0-99中十位上的1是10个;那么关系究竟是什么呢?我们看下面的例子来理解:
对于数字123:
123/10=12,包含12个10,每个10包含1个1(个位1)所以个位共包含12*1=12个1;余数的情况后面单独讨论;
123/100(或者12/10)=1,包含1个100,每个100包含10个1(十位1),所以十位共包含1*10=10个1;余数的情况后面单独讨论;
123/1000(或者1/10)=0,包含0个1000,每个1000包含100个1(百位1),所以百位共包含0*100=0个1;余数的情况后面单独讨论;
现在考虑余数的两种情况:
(1)余数大于1的情况:
数个位时,余数3大于1;所以个位上1的个数要+1;
数十位时,余数2大于1;因为增加了100-120之间(10-19)的数字即110-119,所以十位上1的个数要+10;
(2)余数等于1的情况:
数百位时,余数等于1;我们应该增加100-123这24个数字中百位上的1,共计24个;
在上面的计算中我们发现123/1000=0包含0个1000,所以百位包含0*100个1,这是常规的情况,实际上由于百位为1,从100到n(123)中还应增加:123-100+1个1.
总结上面的情况:就是对于每一位(个位,十位,百位),我们计算他们“通常”情况下(即该数字包含多少个10,100,1000乘以对应的1的个数)包含的1的个数+该位上余数大于1(等于1)的情况下包含的1的个数 = 该位上1的总个数,所有的位遍历,求和,就好了。
=================================================================================
笔者自己再次总结一下:每一位上1的个数都是由它的高位和自己决定的。123太简单,如果拿3456来看:
第0位(个位):3456/10 + (6>1) ? 1 : 0 = 345 + 1 = 346
第1位(十位):(3456/100) * 10 + (5 > 1 ? 10 : (5 == 1 ? 6 + 1 : 0)) = 340 + 10 = 350
第2位(百位):(3456/1000) * 100 + (4 > 1 ? 100 : (4 == 1 ? 56 + 1 : 0)) = 300 + 100 = 400
第3位(千位):(3456/10000) * 1000 + (3 > 1 ? 1000 : (3 == 1 ? 456 + 1 : 0)) = 1000
346 + 350 + 400 + 1000 = 2096
通过以上例子可以总结出通向公式:
对于给定的正整数value,v[i]代表第i位上的数字,a[i]代表第i位上x出现的次数,c[i]代表第i位后面的数字组成的整数。i的范围:0到最高位-1,假如给定的value为2345,则i的取值范围:0-3,当i=0时,c[i]=0。那么有:
a[i] = (value / (10 ^ (i+1))) * (10 ^ i) + (v[i] > x ? (10 ^ i) : (v[i] == x ? c[i] + 1 : 0))
将这个公式套用到3456上就可以明白为什么上面用复杂的公式计算各位上1的个数了。
/** return n^p; */ int myPower(int n, int p) { int ret = 1; while (p>0) { ret = ret * n; p--; } return ret; } /** * c[i] = value % (10^i) * a[i] stands for the number of n occurs in ith (i>=0) * a[i] = (value / (10 ^ (i+1))) * (10 ^ i) + (v[i] > n ? (10 ^ i) : (v[i] == n ? c[i] + 1 : 0)) */ int countIthN(int value, int i, int n) { if (value < 0) { return -1; } if (i == 0) { return value / 10 + ((value % 10) >= n ? 1 : 0); } int pi = myPower(10, i); int pi_1 = myPower(10, i+1); int ci = value % pi; int vi = (value / pi) % 10; return value / pi_1 * pi + (vi > n ? pi : (vi == n ? (ci + 1) : 0)); } int countN(int value, int n) { int ret = 0; for (int i = 0; value / myPower(10, i); i++) { ret += countIthN(value, i, n); } return ret; }