课堂练习——得出“1”的个数
2015-05-03 20:30 by 奔波儿灞, 5 阅读, 0 评论, 收藏, 编辑
题目：给定一个十进制的正整数，写下从1开始，到N的所有整数，然后数一下其中出现“1”的个数。
要求：写一个函数 f(N) ，返回1 到 N 之间出现的 “1”的个数。例如 f(12) = 5。在32位整数范围内，满足条件的“f(N) =N”的最大的N是多少。
一、设计思路
首先，此题可以用从1到N遍历一遍的方法来解决。即输入一个数除以10取余数，如果余数等于1则计数加1，否则计数加0，然后此数除以10，直到此数除以10结果等于0。然而，此种方法多做了很多无用功。我们做练习的目的并不是实现程序，而是学会各种算法来优化程序。所以，此题第二种解法则是统计各种情况下，“1”个数的变化规律。
规律变化：
f(3)=1;
f(13)=2+1;f(23)=3+10;f(33)=4+10;f(43)=5+10;f(53)=6+10;f(63)=7+10;……;f(93)=10+10;
f(103)=11+10+4;f(113)=12+12+14;f(123)=13+20+24;……
……
通过对数字进行有规律的总结，发现从1到N，中出现的所有的1的总数。可以从N这个数总结出来的。
f(N)=个位上出现1的次数+十位上出现1的次数+百位上出现1的次数+……
所以对于一个数abcde，取百位上的c来计算，
假若c是"1",那么百位上1的个数是由他的高位和低位来决定的。等于ab*100+cde+1;
假若c是"0",那么百位上1的个数是ab*100；
假如c是大于1，那么 百位上1的个数是（ab+1）*100;
二、源代码
1 #include <iostream.h>
2 int f(int n)
3 {
4 int Count=0;
5 int Factor=1;
6 int LowerNum=0;
7 int CurrNum=0;
8 int HigherNum=0;
9 while(n/Factor!=0)
10 {
11 LowerNum=n-(n/Factor)*Factor;
12 CurrNum=(n/Factor)%10;
13 HigherNum=n/(Factor*10);
14 switch(CurrNum)
15 {
16 case 0:
17 Count+=HigherNum*Factor;
18 break;
19 case 1:
20 Count+=HigherNum*Factor+LowerNum+1;
21 break;
22 default:
23 Count+=(HigherNum+1)*Factor;
24 break;
25 }
26 Factor*=10;
27 }
28 return Count;
29 }
30 int main()
31 {
32 int num;
33 cout<<"请输入十进制整数："<<endl;
34 cin>>num;
35 cout<<f(num)<<endl;
36 return 0;
37 }
三.结果截图
