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

题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。

编程之美上的原题

基本思路1:

每次判断各位是否为1,计数。然后依次/=10即可。

时间复杂度O(N*lgN)

#include <stdio.h>

int countone(int num)
{
	int cnt = 0;
	while(num)
	{
		if(num%10==1)
		{
			cnt++;
		}
		num/=10;
	}
	return cnt;
}

int countone_all(int n)
{
	int sum = 0;
	int i;
	for(i=1;i<=n;i++)
	{
		sum += countone(i);
	}
	return sum;
}

int main()
{
	int n = 12;
	printf("%d\n", countone_all(n));
	return 0;
}

思路2:

可以用归纳法搞出一个递推公式。

但是如书上所述,这个递推公式是有范围限制的,n最大为1111111110。

归纳如下

如果N为0~9 ,当N>=1时,f(N)=1,否则f(N)=0。

如果N为两位数,f(N)不仅和各位有关,还和十位有关:

(1)如果个位数大于等于1,则个位出现1的次数为十位数的数字加一(加个位的一个1)。如果N的个位数为0,个位出现1的次数就是0。

(2)如果十位数字等于1,则十位上出现1的次数为个位数字加1,如果十位数大于1,则十位数上出现1的次数为10。

可写出程序如下:

long long countone_plus(long long n)
{
	long long iCount = 0;
	long long iFactor = 1;
	long long iLowerNum = 0;
	long long iCurrNum = 0;
	long long iHigherNum = 0;

	while( n/iFactor )
	{
		iLowerNum = n - (n / iFactor) * iFactor;
		iCurrNum = (n/iFactor) % 10;
		iHigherNum = n / (iFactor * 10);

		switch(iCurrNum)
		{
			case 0:
				iCount += iHigherNum * iFactor;
				break;
			case 1:
				iCount += iHigherNum * iFactor + iLowerNum + 1;
				break;
			default:
				iCount += (iHigherNum + 1) * iFactor;
				break;
		}
		iFactor *= 10;
	}
	return iCount;
}


 

Leave a Reply

Your email address will not be published.