编程之美：1的数目

编程之美：1的数目2015-02-11一、问题描述

给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下之中所有“1”的个数。

例如：

N=12,（1,2,3,4,5,6,7,8,9,10,11,12）共有5个1

二、解题思想

假设N=abcde为一个整数，a,b,c,d,e分别对应十进制数，如果要计算（1到N）百位出现1的个数,他将受三个因素的影响：百位以上的数，百位数和百位一下的数，具体依赖如下：

分别设整数N百位以上，百位和百位一下的数字分别为：preNum,curNum,proNum，如N=abcde的三个值分别为：

preNum=ab

curNum=c

proNum=de

分三种情况讨论百位上的数字出现1的计数（用oneCount表示）

情况1：百位数字为0（curNum=0），oneCount=preNum*100;

情况2：百位数字为1（curNum=1），oneCount=preNum*100+proNum+1;

情况3：百位数字大于1（curNum>1），oneCount=（preNum+1）*100;

其他位计算1出现的个数类似

三、代码实现

#include<iostream>using namespace std;int compOneNum（int n）{int preNum;int curNum;int proNum;int oneCount=0;//当前位的幂指数10^aint t=1;while（n/t）{preNum=n%t;curNum=（n/t）%10;proNum=（n/t）/10;switch （curNum）{case 0:oneCount+=proNum*t;break;case 1:oneCount+=proNum*t+preNum+1;break;default:oneCount+=（proNum+1）*t;break;}t=t*10;}return oneCount;}int main（）{cout<<"请输入整数n："<<endl;int n;cin>>n;int oneCount=compOneNum（n）;cout<<oneCount<<endl;system（"pause"）;return 0;}