1、给定一个十进制的正整数，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数？

解法一：从1到N遍历，将每个数中含有“1”的个数加起来。。时间复杂度：O(n)*每个整数中“1”的个数复杂度=O(N*lgN)。。随着N增大，时间超越线性增长。。

#include
     
      using namespace std;int getNum(int n){    if(n==0) return 0;    int num=0;    while(n!=0)    {        num+=(n%10==1)?1:0;        n/=10;    }    return num;}int main(){    int n;    while(cin>>n)    {        int count=0;        for(int i=1;i<=n;++i)        {            count+=getNum(i);        }        cout<
      
       <
      
     

解法二：我们推导出一般情况下，从N得到f（N）的计算方法：假设 N=abcde，这里a、b、c、d、e 分别是十进制数N的各个数位上的数字。如果要计算百位上出现1的次数，它将会受到三个因素的影响：百位上的数字，百位以下（低位）的数字，百位（更高位）以上的数字。

1）如果百位上的数字为0，则可以知道，百位上可能出现1的次数由更高位决定，比如12013，则可以知道百位出现1的情况可能是100～199，1100～1199，2100～2199，…，11100~11199，一共有1200个。也就是由更高位数字（12）决定，并且等于更高位数字（12）×当前位数（100）。

 2）如果百位上的数字为1，则可以知道，百位上可能出现1的次数不仅受更高位影响，还受低位影响，也就是由更高位和低位共同决定。例如对于12113，受更高位影响，百位出现1的情况是100～199，1100～1199，2100～2199，…，11100~11199，一共1200个，和上面第一种情况一样，等于更高位数字（12）×当前位数（100）。但是它还受低位影响，百位出现1 的情况是12100～12113，一共114个，等于低位数字（123）+1。

3）如果百位上数字大于1（即为2~9），则百位上可能出现1的次数也仅由更高位决定，比如12213，则百位出现1的可能性为：100～199，1100～1199，2100～2199，…，11 100～11199，12100～12199，一共有1300 个，并且等于更高位数字+1（12+1）×当前位数（100）。

归纳总结，得出高效算法，len为输入长度，时间复杂度为O(len)=O(ln(N)/ln(10)+1) ，代码为：

#include
     
      using namespace std;int getNum(int n){    int iCount=0;    int iFactor=1;    int iLow=0;    int iCur=0;    int iHigh=0;    while(n/iFactor!=0)    {        iLow=n-(n/iFactor)*iFactor;        iCur=(n/iFactor)%10;        iHigh=n/(iFactor*10);        switch(iCur)        {            case 0:               iCount+=iHigh*iFactor;               break;           case 1:               iCount+=iHigh*iFactor+iLow+1;               break;           default:               iCount+=(iHigh+1)*iFactor;        }        iFactor*=10;    }    return iCount;}int main(){    int n;    while(cin>>n)    {        cout<
      
       <
      
     

2、紧接第一题满足条件“f(N)=N”的最大N是多少？

解法：最大的N，显然需要证明这个等式有个上界。可以经过简单的推算出来一个公式即：f(10ⁿ-1)=n*10^n-1，一开始f(N)<N，那么我们只需找到数开始，使f(Y)>Y，那么我们只需要计算比Y小的，最大的满足条件的值即可。令N=10^9-1=99 999 999 999，让n从N向0递减，依次检查是否有f(n)=n，第一个满足就是我们要找的整数。得出n=1 111 111 110。。