本文主要是介绍从1到n正数中1出现的次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题:输入一个整数n，求从1到n这n个整数的十进制中1出现的次数。
详细实现代码如下:
// ====================方法一:穷举====================
int NumberOf1(unsigned int n);int NumberOf1Between1AndN_Solution1(unsigned int n)
{int number = 0;for(unsigned int i = 1; i <= n; ++ i)number += NumberOf1(i);return number;
}int NumberOf1(unsigned int n)
{int number = 0;while(n){if(n % 10 == 1)number ++;n = n / 10;}return number;
}// ====================方法二:找规律====================
int NumberOf1(const char* strN);
int PowerBase10(unsigned int n);int NumberOf1Between1AndN_Solution2(int n)
{if(n <= 0)return 0;char strN[50];sprintf(strN, "%d", n);return NumberOf1(strN);
}int NumberOf1(const char* strN)
{if(!strN || *strN < '0' || *strN > '9' || *strN == '\0')return 0;int first = *strN - '0';unsigned int length = static_cast<unsigned int>(strlen(strN));if(length == 1 && first == 0)return 0;if(length == 1 && first > 0)return 1;// 假设strN是"21345"// numFirstDigit是数字10000-19999的第一个位中1的数目int numFirstDigit = 0;if(first > 1)numFirstDigit = PowerBase10(length - 1);else if(first == 1)numFirstDigit = atoi(strN + 1) + 1;// numOtherDigits是01346-21345除了第一位之外的数位中1的数目int numOtherDigits = first * (length - 1) * PowerBase10(length - 2);// numRecursive是1-1345中1的数目int numRecursive = NumberOf1(strN + 1);return numFirstDigit + numOtherDigits + numRecursive;
}int PowerBase10(unsigned int n)
{int result = 1;for(unsigned int i = 0; i < n; ++ i)result *= 10;return result;
}// ====================测试代码====================
void Test(char* testName, int n, int expected)
{if(testName != NULL)printf("%s begins: \n", testName);if(NumberOf1Between1AndN_Solution1(n) == expected)printf("Solution1 passed.\n");elseprintf("Solution1 failed.\n"); if(NumberOf1Between1AndN_Solution2(n) == expected)printf("Solution2 passed.\n");elseprintf("Solution2 failed.\n"); printf("\n");
}void Test()
{Test("Test1", 1, 1);Test("Test2", 5, 1);Test("Test3", 10, 2);Test("Test4", 55, 16);Test("Test5", 99, 20);Test("Test6", 10000, 4001);Test("Test7", 21345, 18821);Test("Test8", 0, 0);
}int _tmain(int argc, _TCHAR* argv[])
{Test();return 0;
}
这篇关于从1到n正数中1出现的次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
