编程之美----1的数目

问题：1，写一个函数f(N)，返回1到N之间出现的”1"的个数。2，满足条件“f(N)=N"的最大的N是多少？

解法：对于之间的每一个数字n，分情况讨论每一个数位出现1的个数，例如要计算百位上出现1的次数，它将会受到三个因素的影响：百位上的数字，百位以下（低位）的数字，百位（更高位）以上的数字。如果百位上的数字为0，可知，百位上可能出现1的次数由更高位决定，并且等于更高位数字*当前位数。如果百位上的数字为1，可知，百位上的数字可能出现1的次数不仅受更高位影响，还受低位影响。如果百位上数字大于1，则百位上可能出现1的次数仅由更高位决定，并且等于更高位数字加1，再乘以当前位数。

 1 LONGLONG Sumls(ULONGLONG n)
 2 {
 3     ULONGLONG iCount = 0;
 4     ULONGLONG iFactor = 1;
 5     ULONGLONG iLowerNum = 0;
 6     ULONGLONG iCurrNum = 0;
 7     ULONGLONG iHigherNum = 0;
 8     while(n / iFactor !=0)
 9     {
10         iLowerNum = n - (n / iFactor) * iFactor;
11         iCurrNum = (n / iFactor) %10;
12         iHigherNum = n / (iFactor * 10);
13         
14         switch(iCurrNum)
15         {
16         case 0:
17             iCount += iHigherNum * iFactor;
18             break;
19         case 1:
20             iCount += iHigherNum * iFactor + iLowerNum + 1;
21             break;
22         default:
23             iCount += (iHigherNum + 1) * iFactor;
24             break;
25         }
26         iFactor *= 10;
27     }
28     return iCount;
29 }

View Code

问题二用类似数学归纳法的思路当n增加10^k 时，f(n)至少增加k*10^k-1