首页 > 代码库 > 编程之美----1的数目

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

2024-08-01 09:57:42   225人阅读

问题：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增加10k 时，f(n)至少增加k*10k-1 

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


联系
我们