从1到n整数中1出现的次数

从1到n整数中1出现的次数

创新互联公司专业为企业提供崖州网站建设、崖州做网站、崖州网站设计、崖州网站制作等企业网站建设、网页设计与制作、崖州企业网站模板建站服务,10余年崖州做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。

要计算X出现的次数(从1到n整数中1出现的次数),需统计X在每一位出现的次数。

1到10出现1次X;1到100出现10次X;1到1000出现100次X。

综上可以得出:从 1 至 10i,在它们的左数第二位(右数第 i 位)中,任意的 X 都出现了 10i1 次。

Eg:以n=21345,X=1

依次分析X在各位中出现的次数:

个位:因为21340中有2134个10,所以从1到21340,1出现了2134次;再看从21341到21345,因为1<5(这里X为1,肯定满足,当X为任意数时,应判断X<5是否成立),所以1在个位中出现的次数为2135次。

十位:因为21300中有213个100,所以从1到21300,1出现在十位的次数为213*10次,再看从21301到21345,因为4>1,所以十位出现的次数为(213+1)*10^(2-1)=2140.

同理,百位出现的次数为(21+1)*10^(3-1)=2200.

千位:因为20000中共有2个10000,所以从1到20000,1出现在千位的次数为2*1000次,再看从20001到21345,因为1==1,所以千位中肯定含有1,但不会是1000次,而是345+1=346次(因为有21000,所以要加1),所以1出现在千位的总次数为2*10^(4-1)+(345+1)=2346次。

万位:方法同上,出现的次数为(0+1)*10^(5-1)=10000.

所以:21345中1出现的次数为2135+2140+2200+2346+10000=18821次

X在第i位出现的次数的计算方法:

1、取第i位左边(高位)的数字,乘以10^(i-1),得到基本的sum

2、取第i位数字:

1)如果大于X,则结果sum+=10^(i-1).

2)如果等于X,则结果为

sum+=(第i位右边的(低位)的数字)+1

3)如果小于X,则结果就为sum

代码如下:

size_t NumberOf1Between1AndN_Solution(size_t n)
{
	char str[12] = { 0 };
	int length = strlen(_itoa(n, str, 10));//计算n的位数
	size_t countSum = 0;
	//为取第i位数字简便,所以以下采取str运算
	for (int i = length - 1; i >= 0; --i)
	{
		//取第i位左面的数字
		int tmpLeft = 0;
		for (int j = 0; j < i; ++j)
		{
			tmpLeft = tmpLeft * 10 + str[j] - '0';
		}

		countSum += tmpLeft * pow(10, length - i - 1);
		int iVal = str[i] - '0'; //第i位的数字
		//如果大于X,则结果countSum+=pow(10, i).
		if (iVal > 1)
		{
			countSum += pow(10, length - i - 1);
		}
		//如果等于X,则结果为countSum+=(第i位右边的(低位)的数字)+1
		else if (iVal == 1)
		{
			int tmpRight = 0;//计算低位数字
			for (int j = i + 1; j < length; j++)
			{
				tmpRight = tmpRight * 10 + str[j] - '0';
			}
			countSum += tmpRight + 1;
		}
		//如果小于X,则结果就为countSum
	}
	return countSum;
}

文章题目:从1到n整数中1出现的次数
网页URL:http://myzitong.com/article/ijoscg.html