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

忘是亡心i 2022-09-17 13:15 98阅读 0赞

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

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

问题描述：给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有"1"的个数。例如：  
N ＝ 2，写下1，2。这样只出现了1个"1"。  
N ＝ 12，写下1，2，……，12，这样有5个"1"。  
写一个函数f(N)，返回1到N之间出现的"1"的个数，比如f(12) = 5。

假设N ＝ abcde，这里a,b,c,d,e分别是十进制数N的各个数位上的数字。如果要计算百位上出现1

的次数，将受3方面因素影响：百位上的数字，百位以下(低位)的数字，百位(更高位)以上的数字。

如果百位上的数字为0，则可以知道百位上可能出现1的次数由更高位决定，比如12 013，则可以知

道百位出现1的情况可能是100－199，1 100－1 199，……，11 100－11 199，一共有1 200个。也就是

由更高位数字(12) 决定，并且等于更高位数字(12)×当前位数(100)。

如果百位上的数字为1，则可以知道，百位上可能出现1的次数不仅受更高位影响，还受低位影响，

也就是由更高位和低位共同决定。例如12 113， 受更高位影响，百位出现1的情况是100－199，1 100

－1 199，……，11 100－11 199，一共有1 200个，和上面第一种情况一样，等于更高位数字(12)×当

前位数(100)。但它还受低位影响，百位出现1的情况是12 100－12 113，一共114个，等于低位数字

(113)+1。

如果百位上数字大于1(即为2－9)，则百位上可能出现1的次数也仅由更高位决定，比如12 213，则

百位出现1的情况是：100－199，1 100－1 199，……，11 100－11 199，12 100－12 199，共1300个

，并且等于更高位数字+1(12+1)×当前位数(100)。

代码：

#include <cstdio>
    
    long long Sum1s( long long n )
    {
    	long long iCount = 0,iFactor = 1,iLowerNum = 0,iCurrNum = 0,iHigherNum = 0;
    	while( n / iFactor != 0 )
    	{
    		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;
    }
    
    int main()
    {
        long long n;
        while(~scanf("%lld",&n)){
            printf("%lld\n",Sum1s(n));
        }
    	return 0;
    }

还有别人好理解的代码：

#include "stdio.h"
    #include "math.h"
    int ans(int n)//求1到n之间包含1的个数；
    {
    	
    	int sum=0,d=0,k,t,i,j;
    	k=n;
    	if(k<1)
    		return 0;
    	if(k>0 && k<10)//计算数据n在1到9之间时1的个数；
    		return 1;
        do//计算数据n大于10时1的个数；
    	{
                j=k%10;
    		    k=k/10;
    		    if(k>0)
    			{
    		    	t=(int)pow(10,d);
    				i=n%t;
    				if(j==1)//处理411等之类的特殊数据；
    			       sum = sum + k*t+i+1;
    				else if(j==0)//处理10的整数次方之类的特特殊数据；
    				   sum = sum + k*t;
    				else//处理497，396等之类的一般数据；
    					sum = sum + (k+1)*t;
    			    d++;
    			}
    	}while(k!=0);
    	t=(int)pow(10,d);
    	if(j==1)//处理最高位是1的特殊数据；
    		sum=sum+n%t+1;
    	else
    	    sum += t;
    	return sum;
    }
    int main()
    {
    	int m,n;
    	while(scanf("%d%d",&m,&n)!=EOF)
    	{
    		if(m==0 && n==0)
    			break;
    		if(m>n)
    			printf("%d\n",ans(m)-ans(n-1));
    		else
    		    printf("%d\n",ans(n)-ans(m-1));
    	}
    	return 0;
    }