一.题目及要求
1.题目
给定一个十进制的正整数，写下从1开始，到N的所有整数，然后数一下其中出现“1”的个数。
2.要求
要求：
1）写一个函数 f(N) ，返回1 到 N 之间出现的 “1”的个数。例如 f(12) = 5。
2）在32位整数范围内，满足条件的“f(N) =N”的最大的N是多少。
二.设计思路
此题显然可以使用穷举的方式计算，若是如此，便失去了练习的意义所在。在这里我们可以利用数学的方法找规律。
在此，假设，用户输入的整数是num,分析如下：
当num是一位数时：f(num)=1(若num=0，则函数值是0)
当num是两位数时：可以将其写成f(num)=个位数是1的个数+十位数是1的个数；
f(12)=2+4=6;
f(22)=3+10=13;
f(32)=4+10=14;
………………
当num是三位数时：同理，写成f(num)=个位数是1的个数+十位数是1的个数+百位数是1的个数;
f(132)=14+20+33=67
………………
当num是四位数五位数时同样如此分析;
若num=abcde,计算百位上出现1的个数，该值受三部分影响,(1)c上的值（2）de的值（3）ab的值
1)若c=0,则受ab的值得影响，那么百位1的个数=ab*当前的位数(100);(若num=12045,则该值是12*100=1200)
2)若c=1,则受ab和de的影响，那么百位1的个数=ab*当前为数(100)+de+1;(若num=12145，则该值=12*100+45+1=1246)
3)若c∈[2,9],则受ab的影响，那么百位1的个数=(ab+1)*当前位数(100);(若num=12345，则该值=(12+1)*100);
三.源代码
// search_1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include<iostream.h> /*函数-寻找1的个数*/ int search_1(int num) { int count=0; int H_num,C_num,L_num; //当前位C_num和高位H_num，以及低位L_num) int flag=1; while(num/flag!=0) { H_num=num/(flag*10); //高位 C_num=(num/flag)%10; //当前位 L_num=num%flag; //低位 switch(C_num) { case 0: //当前位是0的时候 count=count+H_num*flag; break; case 1: count=count+H_num*flag+L_num+1; //当前位是1的时候 break; default: count=count+(H_num+1)*flag; //当前位在2~9之间时 break; } flag=flag*10; } return count; } int main() { int num; //用户输入的数据 cout<<"请输入数据："; cin>>num; cout<<"1出现的个数为："<<search_1(num)<<endl; return 0; }
四.结果及截图
五.心得体会
1)刚开始看见这个题目的时候，便想到了最简单的方法也是最笨的方法—枚举，但是这样便失去了练习的意义。然后才开始找规律。
2)这个程序再一次的向人们展示了数学思想在编程中的应用，此程序的核心就是找规律，在找枚举的过程中，看你对数字的敏感程度，总结规律。