网上看到一道题:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数‘
这里修改下题目:求从0到n这n+1个整数的十进制表示中出现m的次数, 其中(9>=m>=0)
例如n为12、m为1:从0到12这些整数中包含1的数字有1、10、11和12,一共有5个1
代码如下:
#include <cstdio> /****************************************************************** * 获知[0, iBound]中所有数字的十进制表达式中包含的0的总数 ******************************************************************/ int GetZeroCount(int iBound) { if (0 > iBound) { return(0); } if (0 == iBound) { return(1); } /* * 下面以GetZeroCount(300456)为例分析问题 */ /* * [0, 300456]可拆分为: * [0, 99999], [100000, 199999], [200000, 299999], [300000, 300456] */ /* * iBase记录与iBound的位数相同的最小的正整数 * iBits记录iBase中0的个数 * 这里iBound = 300456, 则有: iBase = 100000, iBits = 5 */ int iBase = 1; int iBits = 0; int iTemp = iBound / 10; while (iTemp > 0) { iBase *= 10; iBits += 1; iTemp /= 10; } int iHighest = iBound / iBase; int iLeft = iBound % iBase; /* * 计算[0, 99999]中0的总数 */ int iStartCount = GetZeroCount(iBase - 1); /* * 计算[100000, 199999]中0的总数 * 其中: 0在第2位的情形为: * 第1位始终为1不变, 第2位始终为0不变, 其他4位都可取[0, 9]这10种值, * 故0在第2位的情形有: 1 * 1 * 10 * 10 * 10 * 10 = 10000种 * 具体为: [100000, 109999], 这10000种 * 同理可知: 0在第3, 4, 5, 6位也都有10000种情形 * 故而, [100000, 199999]中0的总数为50000个 */ /* * [200000, 299999]中0的总数与[100000, 199999]中的相同 */ /* * 计算[100000, 199999], [200000, 299999]中0的总数 */ int iMiddleCount = (iBase / 10) * iBits * (iHighest - 1); /* * iHighZeroCount记录与最高位相邻的0的个数 */ int iHighZeroCount = 0; if (0 == iLeft) { iHighZeroCount = iBits; } else { int iCheck = iLeft * 10; while (iCheck < iBase) { iHighZeroCount += 1; iCheck *= 10; } } /* * iLeftBits记录iLeft的位数 */ int iLeftBits = iBits - iHighZeroCount; /* * 计算[300000, 300456]中0的总数 * 最高位后面两个0共计出现(456 + 1)次 * 后面三位出现0的情形等价于[000, 456]中0的总数 * [000, 456]比[0, 456]多的0在数字开头 * 其中: * 两个0开头的情形有10个: [000, 009] * 一个0开头的情形有90个: [010, 099] * 继而可知[300000, 300456]中0的总数为: * (456 + 1) * 2 + GetZeroCount(456) + 10 * 2 + 90 * 1 * 10拆为9 + 1, 可得: * (456 + 1) * 2 + GetZeroCount(456) + 2 + 9 * 2 + 90 * 1 */ int iLastCount = (iLeft + 1) * iHighZeroCount + GetZeroCount(iLeft); iLastCount += (iLeftBits - 1); int iRedundantZeroCount = 9; while (iLeftBits > 1) { iLeftBits -= 1; iLastCount += iLeftBits * iRedundantZeroCount; iRedundantZeroCount *= 10; } return(iStartCount + iMiddleCount + iLastCount); } /****************************************************************** * 获知[0, iBound]中所有数字的十进制表达式中包含的iNumber的总数 ******************************************************************/ int GetNumberCount(int iNumber, int iBound) { if (0 > iNumber || 9 < iNumber) { return(-1); } /* * 因为0不可能排在最高位 * 所以, [100, 199]在不计<最高位>的iNumber时不等于[0, 99]的iNumber数 * 继而, 0的总数计算方法需要特殊处理 */ if (0 == iNumber) { return(GetZeroCount(iBound)); } if (0 >= iBound) { return(0); } /* * iBase记录与iBound的位数相同的最小的正整数 * 如: iBound = 345时, iBase = 100 */ int iBase = 1; int iTemp = iBound / 10; while (iTemp > 0) { iBase *= 10; iTemp /= 10; } int iHighest = iBound / iBase; int iLeft = iBound % iBase; /* * 计算最高位上包含的iNumber的个数 */ int iHighCount = 0; if (iHighest > iNumber) { /* * 如iHighest = 3, iNumber = 1 * 此时[0, 345]中, iNumber在最高位的数字包括[100, 199] * 共计100个, 即iBase */ iHighCount = iBase; } else if (iHighest < iNumber) { /* * 如iHighest = 3, iNumber = 4 * 此时[0, 345]中, iNumber在最高位的数字个数为0 */ iHighCount = 0; } else { /* * 如iHighest = 3, iNumber = 3 * 此时[0, 345]中, iNumber在最高位的数字包括[300, 345] * 共计46个, 即iLeft + 1 */ iHighCount = iLeft + 1; } /* * 下面都<不能再计算最高位>的iNumber的个数 */ /* * 计算[0, iHighest * iBase - 1]中所有<不计最高位的>iNumber的个数 * 如上即为: [0, 299]中不计最高位的iNumber的个数 * [0, 299] 可拆分为: [0, 99], [100, 199], [200, 299] * [100, 199]与[200, 299]在<不计最高位>的iNumber(1~9)的个数时与[0, 99]是等价的 * 即有: 3 * GetNumeralCount(iNumber, 99) */ int iFullCount = iHighest * GetNumberCount(iNumber, iBase - 1); /* * 计算[iHighest * iBase, iBound]中所有<不计最高位>的iNumber的个数 * 如上即为: [300, 345]中<不计最高位>的iNumber的个数 * [300, 345]在<不计最高位>的iNumber的个数与[0, 45]是等价的 * 即有: GetNumberCount(iNumber, 45) */ int iLeftCount = GetNumberCount(iNumber, iLeft); return(iHighCount + iFullCount + iLeftCount); } /****************************************************************** * 获知iCheck的十进制表达式中包含的iNumber的总数 ******************************************************************/ int GetNumberCountOf(int iNumber, int iCheck) { if (0 > iNumber || 9 < iNumber) { return(-1); } if (0 > iCheck) { return(-1); } int iCount = 0; do { if (iCheck % 10 == iNumber) { iCount += 1; } iCheck /= 10; } while (iCheck > 0); return(iCount); } /****************************************************************** * 利用枚举法, 获知[0, iBound]中所有数字的十进制表达式中包含的iNumber的总数 ******************************************************************/ int EnumerateNumberCount(int iNumber, int iBound) { if (0 > iNumber || 9 < iNumber) { return(-1); } if (0 > iBound) { return(-1); } int iCount = 0; for (int iIndex = 0; iIndex <= iBound; ++iIndex) { iCount += GetNumberCountOf(iNumber, iIndex); } return(iCount); } void test_way_1(int iBound) { for (int iNumber = 0; iNumber < 10; ++iNumber) { int iCount = GetNumberCount(iNumber, iBound); printf("%5d ----- %5d\n", iNumber, iCount); } } void test_way_2(int iBound) { for (int iNumber = 0; iNumber < 10; ++iNumber) { int iCount = EnumerateNumberCount(iNumber, iBound); printf("%5d ----- %5d\n", iNumber, iCount); } } int main(int argc, char * argv[]) { int iBound = 300456; printf(" Get Number Count Of [0, %d]\n", iBound); printf("---------- test_way_1 ----------\n"); test_way_1(iBound); printf("---------- test_way_2 ----------\n"); test_way_2(iBound); printf("------------ finish ------------\n"); return(0); }