一、题目
给定一个十进制的正整数，写下从1开始，到N的所有整数，然后数一下其中出现“1”的个数。
二、要求
写一个函数 f(N) ，返回1 到 N 之间出现的 “1”的个数。例如 f(12) = 5。在32位整数范围内，满足条件的“f(N) =N”的最大的N是多少。
三、设计思路
1、首先遍历每个数的各个位数，然后将1的个数加起来。
2、首先找规律： f（1）=1；f（13）=7=2+5；f（23）=13=3+10......f(abcde)=?
以百位为例， 当c是1,那么百位上1的个数是由他的高位和低位来决定的。等于ab*100+cde+1;当c是"0",那么百位上1的个数是ab*100；当c是大于1，那么 百位上1的个数是（ab+1）*100;以此类推。
四、源代码
1.遍历各位1的个数：
#include<iostream> using namespace std; int main() {int icount=0,i,N,temp; cout<<"请输入最大的数N："; cin>>N; for(i=1;i<=N;i++) { temp=i; while(temp!=0) { icount+=(temp%10==1)?1:0; temp/=10; } } cout<<icount<<endl; return 0; }
2.通过规律的：
#include<iostream.h>
int Count(int n)
{
int count=0;
int now=1;
int l=0;
int nownum=0;
int h=0;
if(n<=0)
{
return 0;
}
while(n/now!=0)
{
l=n-(n/now)*now;
nownum=(n/now)%10;
h=n/(now*10);
if(nownum==0)
{
count+=h*now;
}
else if(nownum==1)
{
count+=h*now+l+1;
}
else
{
count+=(h+1)*now;
}
now*=10;
}
return count;
}
void main()
{
int number;
cout<<"请输入数字：";
cin>>number;
cout<<Count(number)<<endl;
}
五、实验截图
六、实验总结
这道题刚发下来，感觉不是很难，不就是遍历1的个数，但是老师需要我们将一个个数算出来，然后找规律，然后就发现问题了。原来问题不是非用很复杂的算法才能解决，简单的也可以算出来，以前的问题是把简单的算法优化，得到复杂的，今天是把复杂的，用简单的算法来实现，不知道有什么太大用处，我还是觉得那句话对，首先能把目的实现的程序就是好程序。
原文：http://www.cnblogs.com/bmbcbyc/p/4477187.html