原题目：
给定一个十进制数n，写下从1开始，到n的所有整数，然后数一下其中出现的所有"1"的个数。
例如：
n=2，写下1，2。这样只出现了1个"1"
n=12,写下 1,2,3,4,5,6,7,8,9,10,11,12。这样"1"的个数是5
请写出一个函数，返回1到n之间出现"1"的个数，比如 f(12)=5
1
package org.blogjava.arithmetic;
2
3
/** *//**
4
* @author jack.wang
5 * @see http://jack2007.blogjava.net/
6
*/
7public class countnumber 
{
8
9
private int count1num(int num) {
10 int sum = 0;
11 while (num != 0) {
12 sum = (num % 10 == 1) ? 1 : 0;
13 num /= 10;
14
}
15 return sum;
16 }
17
18 private int countnum(int n) {
19 int sum = 0;
20 for (int i = 1; i <= n; i) {
21 sum = count1num(i);
22 }
23 return sum;
24 }
25
26 private int countnumnew(int n) {
27 int count = 0;
28 int factor = 1;
29 int lower;
30 int current;
31 int higher;
32 while (n / factor != 0) {
33 lower = n - (n / factor) * factor;
34 current = (n / factor) % 10;
35 higher = n / (factor * 10);
36 switch (current) {
37 case 0:
38 count = higher * factor;
39 break;
40 case 1:
41 count = higher * factor lower 1;
42 break;
43 default:
44 count = (higher 1) * factor;
45 }
46 factor *= 10;
47 }
48 return count;
49 }
50
51 /** *//**
52 * @param args
53 */
54 public static void main(string[] args) {
55 system.out.println("两个算法的结果相等");
56 /** *//**
57 * 方法一： 这个问题看上出并不是一个难问题，因为不需要太多的思考，只要稍懂点程序的人都会想到，简单的设计如下。
58 * 这个方法很简单但是这个算法的致命问题是效率，它的时间复杂度是 o(n)*count(int num)函数的复杂度=
59 * o(n)*logn。可见如果n很大时复杂度成线性增长。是否还有更好的方法，我说的是从算法复杂的角度考虑最优的方法？
请看方法二。
60 */
61 long start = system.currenttimemillis();
62 countnumber cn1 = new countnumber();
63 system.out.println("第一个算法的结果"cn1.countnum(100000000));
64 long end = system.currenttimemillis();
65 long time1 = end - start;
66 /** *//**
67 * 方法二： 这种方法分别分析n的每一位上1出现的可能性，读者可以自己按照归纳的思想分析一下，最终你会得出
68 * 一个结论，就是通过分析n而不是遍历1到n的每一个数就可以得出答案，如果n的长度为len的话这种 算法的复杂度为o
(len)。 发现规律为
69 * 1. 如果位数上为0，1的数目由该位以上的数决定，并乘以该位的分位 比如百位上是0，高位上是14则百位上出现1的数目
为 14*100。
70 * 2. 如果位数上为1，1的数目由高位和低位共同决定。 比如高位是14低位是112，则百位出现1的数目为 14×100 （112
1）
71 * 3. 如果位数上大于1，则百位出现1的数目为 （14 1）×100
72 */
73 start = system.currenttimemillis();
74 countnumber cn2 = new countnumber();
75 system.out.println("第二个算法的结果"cn2.countnumnew(100000000));
76 end = system.currenttimemillis();
77 long time2 = end - start;
78 system.out.println("第一个算法的时延比第二个算法的多" (time1 - time2) / 1000 "秒");
79 }
80
81 /** *//**
82 console out:
83 两个算法的结果相等
84 80000001
85 80000001
86 第一个算法的时延比第二个算法的多27秒
87 */
88}
89
本博客为学习交流用，凡未注明引用的均为本人作品，转载请注明出处，如有凯发k8网页登录的版权问题请及时通知。由于博客时间仓促，错误之处敬请谅解，有任何意见可给我留言，愿共同学习进步。