求一个随意正整数N，从1到N含有1的个数

RT:

  例如     N=5， 含有1的数字为：1，总共有1个1；

             N=11， 含有1的数字为：1，10，11，总共有4个1；

算法如下：（并测试两种算法的效率）

import java.util.Calendar;
import java.util.Scanner;

public class AnalyseNum {

    public static void main(String[] args) {
      
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        long beginS = Calendar.getInstance().getTimeInMillis();
        System.out.println("f("+ N +") = " + AnalyseNum(N));
        System.out.println("for--efficency:" + (Calendar.getInstance().getTimeInMillis() - beginS));
       
        beginS = Calendar.getInstance().getTimeInMillis();
        System.out.println("f("+ N +") = " + AnalyseNumEfficiency(N));
        System.out.println("algorithm--efficency:" + (Calendar.getInstance().getTimeInMillis() - beginS));
       
    }

    public static int AnalyseNum(int num)
    {
        int count = 0;
       
        for(int i=1; i<=num; i++)
        {
            /*int numdiv = i/10;
            if(i%10 ==1)
                count++;
            while(numdiv != 0)
            {
                int nummod = numdiv%10;
                if(nummod == 1)
                    count++;
                numdiv = numdiv/10;
            }*/
            int isNum = 0;
            int curNum = i;
            while(curNum != 0)
            {
                isNum += (curNum % 10 == 1)? 1 : 0;
                curNum /= 10;
            }
           
            count += isNum;
        }
       
        return count;
    }
   
    public static int AnalyseNumEfficiency(int num)
    {
        int count = 0;
        int factor = 1;
        int lowerNum = 0;
        int curNum = 0;
        int higherNum = 0;
       
        while(num / factor != 0)
        {
            lowerNum =num - (num/factor)*factor;
            curNum = (num/factor)%10;
            higherNum = num/(factor*10);
           
            switch (curNum) {
            case 0:
                count += higherNum*factor;
                break;
            case 1:
                count += higherNum*factor + lowerNum + 1;
                break;
            default:
                count += (higherNum + 1)*factor;
                break;
            }
           
            factor *= 10;
        }
       
        return count;
    }
}

测试后，发现后面一种算法的高于前者N倍~~~~~