求出1的个数.doc

原题目：给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有1的个数。例如：N=2，写下1，2。这样只出现了1个1N=12,写下 1,2,3,4,5,6,7,8,9,10,11,12。这样1的个数是5请写出一个函数，返回1到N之间出现1的个数，比如 f(12)=51packageorg.blogjava.arithmetic;23/*/*4*authorJack.Wang5*see/6*/7publicclassCountNumber89privateintcount1Num(intnum)10intsum=0;11while(num!=0)12sum+=(num%10=1)?1:0;13num/=10;1415returnsum;161718privateintcountNum(intn)19intsum=0;20for(inti=1;i=n;i+)21sum+=count1Num(i);2223returnsum;242526privateintcountNumNew(intn)27intcount=0;28intfactor=1;29intlower;30intcurrent;31inthigher;32while(n/factor!=0)33lower=n-(n/factor)*factor;34current=(n/factor)%10;35higher=n/(factor*10);36switch(current)37case0:38count+=higher*factor;39break;40case1:41count+=higher*factor+lower+1;42break;43default:44count+=(higher+1)*factor;4546factor*=10;4748returncount;495051/*/*52*paramargs53*/54publicstaticvoidmain(Stringargs)55System.out.println(两个算法的结果相等);56/*/*57*方法一：这个问题看上出并不是一个难问题，因为不需要太多的思考，只要稍懂点程序的人都会想到，简单的设计如下。58*这个方法很简单但是这个算法的致命问题是效率，它的时间复杂度是O(N)*count(intnum)函数的复杂度=59*O(N)*logN。可见如果N很大时复杂度成线性增长。是否还有更好的方法，我说的是从算法复杂的角度考虑最优的方法？ 请看方法二。60*/61longstart=System.currentTimeMillis();62CountNumbercn1=newCountNumber();63System.out.println(第一个算法的结果+cn1.countNum(100000000);64longend=System.currentTimeMillis();65longtime1=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的数目为14100+（112+ 1）71*3. 如果位数上大于1，则百位出现1的数目为（14+1）10072*/73start=System.currentTimeMillis();74CountNumbercn2=newCountNumber();75System.out.println(第二个算法的结果+cn2.countNumNew(100000000);76end=System.currentTimeMillis();77longtime2=end-start;78System.out.println(第一个算法的时延比第二个算法的多+(time1-t