本文主要是介绍第三十题（从1到n的正数中出现1的次数 ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出两种方法
第一种是时间效率较低的常规方法，遍历1~n,求出每个数中1的个数，将求出的所有结果求和即可。
第二种方法基于这个规律：1~10^n-1的所有整数中1的出现的次数总和为n*10^(n-1)。
对于一个整数，按照最高位是否为1分两种情况讨论：
若最高位为1，例如数字12345，可以分为
1~9999,10000~12345两部分，1~9999中1出现的次数总和可以用上述规律求得为4*10^3
10000~12345所有数的最高位1的总数为2345+1（10000最高位的1）
而10001~12345所有数后四位中1的个数总和0~2345中1的个数总和相同，相当于求1~2345中1的个数总和，这是原问题的子问题，可以通过递归求解。
若最高位大于1，例如数字3456，可以这样划分：
第一，1~9999,10000~19999的后四位 利用上面给出的规律，为2*4*10^3
第二，10000~19999的最高位1的个数总和，为(2-1)*10^4
第三，20001~23456中后四位中1的个数总和，相当于1~3456中1的个数总和，同理采用递归求解。
代码如下：
#include "stdafx.h"
#include<iostream>
using namespace std;
namespace MS100P_30
{int count1OfNumber_method1(int number){int count=0;int temp;for (int i = 1; i <= number; i++){temp = i;while (temp != 0){if (temp % 10 == 1) count++;temp /= 10;}}return count;}int count1OfNumber_method2(int number){if (number >= 1 && number <= 9) return 1;if (number == 0) return 0;int digits = 0,sum=0;int temp = number;while (temp != 0) //求位数{temp /= 10;digits++;}int highDigit = number / (int)pow(10, digits-1); //最高位数字int remaider = number % ((int)pow(10, digits - 1));if (highDigit == 1){sum += (remaider + 1);sum += (digits-1)*pow(10, digits - 2); sum += count1OfNumber_method2(remaider);}else{sum = highDigit*(digits-1)*pow(10, digits - 2) + pow(10, digits - 1) + count1OfNumber_method2(remaider);}return sum;}void test(){cout << count1OfNumber_method1(24567) << endl;cout << count1OfNumber_method2(24567) << endl;cout << count1OfNumber_method1(12345) << endl;cout << count1OfNumber_method2(12345) << endl;}
}int _tmain(int argc, _TCHAR* argv[])
{MS100P_30::test();return 0;
}
这篇关于第三十题（从1到n的正数中出现1的次数 ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
