题目
1 给定一个十进制的正整数，写下从1开始，到N的所有整数，然后数一下其中出现“1”的个数。
2 要求：
(1) 写一个函数 f(N) ，返回1 到 N 之间出现的“1”的个数。例如 f(12) = 5。
(2)在32位整数范围内，满足条件的“f(N) =N”的最大的N是多少。
设计思想
(1)一位数时
f(0)=0;f(1)=1;f(2-9)=1;
(2)二位数时
f(10)=1+(0+1)=2;
f(11)=(1+1)+(1+1)=4;
f(12)=(1+1)+(2+1)=5;
f(13)=(1+1)+(3+1)=6;
f(23)=(2+1)+10=13;
f(33)=(3+1)+10=14;
f(93)=(9+1)+10=20;
(3)三位数时
f(123)=个位出现的1数+十位出现的1数+百位出现的1数
(4)N = abcde时
以c位为例
if(c==0) num=ab*100;
if(c==1) num=ab*100+de+1;
if(c>=2) num=(ab+1)*100
源代码
#include<iostream>
#include<math.h>
using namespace std; int Count1Num(int Digit)
{
int figure=1;//标记计数1的位数（1为个位，10为十位）
int curOfDigit=0;//当前位数数字
int lowerOfDigit=0;//较低位数字大小（可为多位）
int higherOfDigit=0;//较高位数字大小
int count=0;
while(Digit/figure!=0)
{
//获取数字
curOfDigit=(Digit/figure)%10;
lowerOfDigit=Digit-(Digit/figure*figure);
higherOfDigit=Digit/(figure*10);
if(Digit<=0)
return 0;
if(0==curOfDigit)//当前数字为0时计数
{
count+=higherOfDigit*figure;
}
else if(1==curOfDigit)//当前数字为1时计数
{
count+=higherOfDigit*figure+lowerOfDigit+1;
}
else
{
count+=(higherOfDigit+1)*figure;
}
figure=figure*10;//数字左移一位
}
return count;
}
void main()
{
int Digit;
int max=0;
while((cout<<"请输入要测试的数值(输入-1结束测试):"<<endl)&&(cin>>Digit))
{
if(Digit==-1)
break;
cout<<"1到"<<Digit<<"包含的1个数:"<<Count1Num(Digit)<<endl;
}
}
程序截图
实验总结
本题的思想主要是逐位考虑，从低位向高位逐位进行1的计数，直到位数超出所求数字。