google面试题——0~n之间1的个数

problem

Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?
 
算法思想：
 
循环求出每个数中1的个数，累计之，若满足f(n)=n，则退出，否则继续。

代码如下：

#include
#include
#include

class CalculationTimes
{
public:
    CalculationTimes(){}
    ~CalculationTimes(){}
 
    int GetTimes(int n);
};

//计算正整数n中1的个数
int CalculationTimes::GetTimes(int n)
{
    int count=0;   
    while(n)
  {
        if(n%10==1)
            count++;
        n/=10;
    }
    return count;
}

//显示菜单
void show_menu()
{
    printf("--------------------------------------------- ");
    printf("input command to test the program \n ");
    printf("   i or I : input n to test \n");
    printf("   g or G : get n to enable f(n)=n \n");
    printf("   q or Q : quit \n");
    printf("--------------------------------------------- ");
    printf("$ input command >");
}

void main()
{
    char sinput[10];
    int n;
 
    show_menu();
 
    scanf("%s",sinput);
    while(stricmp(sinput,"q")!=0)
  {
        int t=0,count=0;
        if(stricmp(sinput,"i")==0)
   {
            printf("  please input an integer:");
            scanf("%d",&n);
   
            count=0;
            CalculationTimes obj;
            t=GetTickCount();
            for(int i=1;i<=n;i++)
                count+=obj.GetTimes(i);
            t=GetTickCount()-t;
            printf("   count=%d    time=%d ",count,t);
        }
        else if(stricmp(sinput,"g")==0)
   {
            CalculationTimes obj;
            n=2;
            count=1;
            t=GetTickCount();
            while(1)
    {
                count+=obj.GetTimes(n);
                if(count==n)
                    break;
                n++;
            }
            t=GetTickCount()-t;
            printf("   f(n)=n=%d    time=%d ",n,t);
        }
  
  
        //输入命令
        printf("$ input command >");
        scanf("%s",sinput);
    }
}

运行结果如下：