编程之美笔记 2.4 1的个数(计算从1到N的数列里1的个数)

Q:

给定一个十进制整数N，写下从1到N的所有整数，然后数一下其中出现的所有的“1”的个数，如10: 1、2、3、4、5、6、7、8、9、10，其中“1”的个数为2。

（1）      写一个函数，返回1到N之间出现的 “1”的个数，如f(10) = 2；

（2）      满足条件”f(N) = N”的最大的N是多少？

A：

（1）       解法1：

从1到N遍历，计算每个数中出现的”1”的个数，算法复杂度为O(N)*计算一个数中1的个数的复杂度=O(N*lgN).

unsigned long count1InAnInteger(unsigned long N)

{

         unsigned long num = 0;

         while(N)

         {

                   num += (N%10==1) ? 1 : 0;

                   N /= 10;

         }

         return num;

}

 

unsigned long count1InSerial(unsigned long n)

{

         unsigned long iCount = 0;

         for(unsigned long i=1; i<=n; i++)

         {

                   iCount += count1InAnInteger(i);

         }

         return iCount;

}

解法2：

归纳法寻找N的各位中包含1的规律：

如果当前位上的数字为0，则在该位上出现1的次数由更高位决定，等于更高位乘以当前位数（十位为10，百位为100）；

如果当前位上的数字为等于1，则该位上出现1的次数由高位和低位共同决定：等于高位乘以当前位数加上低位数字加1；

如果当前位上的数字大于1，则该位上出现1的次数由高位决定：等于高位数字加1然后乘以当前的位数。

typedef unsigned long TYPE;

TYPE sum1s(TYPE n)

{

         TYPE iCount = 0;

         TYPE iFactor = 1;

         TYPE iLowerNum = 0;

         TYPE iCurrNum = 0;

         TYPE iHigherNum = 0;

         while(n/iFactor != 0)

         {

                   iLowerNum = n - (n/iFactor) * iFactor;

                   iCurrNum = n/iFactor % 10;

                   iHigherNum = n/(iFactor*10);

                   switch(iCurrNum)

                   {

                   case 0:

                            iCount += iHigherNum*iFactor;

                            break;

                   case 1:

                            iCount += iHigherNum*iFactor + iLowerNum+1;

                            break;

                   default:

                            iCount += (iHigherNum+1)*iFactor;

                            break;

                   }

                   iFactor *= 10;

         }

         return iCount;

}

（2）

解：略。