每日一题(10)——统计连续数字中1的个数

最新推荐文章于 2022-10-27 17:31:32 发布

Aiphis7

最新推荐文章于 2022-10-27 17:31:32 发布

阅读量763

点赞数

分类专栏：笔试题/面试题

笔试题/面试题专栏收录该内容

49 篇文章

订阅专栏

问题：

输入十进制数字N，统计从1到N的连续数字中，所有的1出现的次数。

例如：

•N = 3, f(3) = 1 (只有一位数字的情况)

•(两位数字的情况)

•N = 13, f(13) = 6 2+4

•N = 23 ,f(23) = 13 3+10

•N = 33, f(33) = 14 10+4

•……

•N = 99, f(99) = 20 10+10

•N = 123

•个位出现1个数：13

•十位数出现1个数：20

•百位出现1个数：24

•同理，我们可以分析4位数、5位数。。。

总结规律：

计算方法：可以通过分别计算每一位上出现1的次数，最后加和统计一共出现的次数

引出问题：

怎样计算某一特定位上1出现的次数？

假设N=abcde，要计算其百位上1出现的次数，

它受到三个因素的影响：百位以上的数字，百位以下的数字，百位上的数字。

当百位数字c=0时，百位上出现1的次数只受百位以上的数字影响

12045：百位上1出现的次数为12*100=1200 次

当百位数字c=1时，百位上出现1的次数只受百位以上的数字，百位以下的数字共同影响

12145：百位上1出现的次数为12*100+45+1 次

当百位数字c>1时，百位上出现1的次数只受百位以上的数字影响

12345：百位上1出现的次数（12+1）*100=1300次

其他各位也是依然这样计算。

[cpp]view plaincopyprint? 
       
 #include <iostream>  
   
 using namespace std;  
   
 void fun(int N)  
 {  
     int factor=1;  
     int count=0;  
     int low,cur,high;  
     while (N/factor)  
     {  
         low = N - (N/factor)*factor;  
         cur = (N/factor)%10;  
         high = N/(factor*10);  
           
         switch(cur)  
         {  
         case 0:  
             count += high*factor;  
             break;  
         case 1:  
             count += high*factor+low+1;  
             break;  
         default:  
             count += (high+1)*factor;  
             break;  
         }  
   
         factor *=10;  
     }  
     cout<<count<<endl;  
 }  
   
 int main()  
 {  
     int n;  
     while(cin>>n)  
     {  
         if(n==-1) break;  
         fun(n);  
     }  
 }  