一、问题
给定一个十进制正整数N,统计从1开始,到N(含N)的所有整数中出现的所有“1”(包含各个位)的个数。
二、解法
版本一:最简单的思路,就是从1到N进行遍历,统计逐个数上“1”的个数并相加,最后的结果就是所求的值。
9 #include <stdlib.h> 10 #include <stdio.h> 11 12 typedef int TYPE; 13 TYPE N = 9999; 14 15 TYPE count_number_1(TYPE n) 16 { 17 TYPE sum = 0; 18 while(n) { 19 sum += n % 10 == 1 ? 1 : 0; 20 n /= 10; 21 } 22 return sum; 23 } 24 25 int main(void) 26 { 27 TYPE i; 28 TYPE sum = 0; 29 for(i = 1; i <= N; i++) { 30 sum += count_number_1(i); 31 } 32 printf("sum of number 1 in %d is %d.\n", N, sum); 33 return EXIT_SUCCESS; 34 }
特点:逐个数遍历,并利用求余算法统计各个位上“1”的总数。
时间复杂度计算:O(nlogn) (对数函数实际上以10为底)
(关于对数时间计算参考维基百科:时间复杂度 對數時間:若演算法的T(n) = O(log n),則稱其具有對數時間。由於計算機使用二進制的記數系統,對數常常以2為底(即log2 n,有時寫作lg n)。然而,由對數的換底公式,loga
n和logb n只有一個常數因子不同,這個因子在大O記法中被丟棄。因此記作O(log n),而不論對數的底是多少,是對數時間演算法的標準記法。)
gprof 时间性能监视测试:
sum of number 1 in 10000000 is 7000001. 时间:0.60(main + count_number_1 )
sum of number 1 in 100000000 is 80000001. 时间:6.43(main + count_number_1 )
sum of number 1 in 1000000000 is 900000001. 时间:71.62(main + count_number_1 )
版本二:分析数学规律,思考“小数N在每一位上可能出现1的次数”之和来得到结果。
9 #include <stdlib.h> 10 #include <stdio.h> 11 12 typedef int TYPE; 13 TYPE N = 1000000000; 14 15 TYPE main(void) 16 { 17 TYPE i; 18 TYPE sum = 0; 19 TYPE bits = 1; 20 TYPE high_bit_value = 0; 21 TYPE current_bit_value = 0; 22 TYPE low_bit_value = 0; 23 while(bits <= N) { 24 high_bit_value = N / (10 * bits); 25 // current_bit_value = (N % (10 * bits)) / bits; 26 // 下面赋值参考编程之美例程优化 27 current_bit_value = (N / bits) % 10; 28 // low_bit_value = (N % (10 * bits)) % bits; 29 // 下面赋值参考编程之美例程优化 30 low_bit_value = N - (N / bits) * bits; 31 if (0 == current_bit_value) 32 sum += bits * high_bit_value; 33 else if(1 == current_bit_value) 34 sum += bits * high_bit_value + low_bit_value + 1;
35 else 36 sum += bits * (high_bit_value + 1); 37 bits *= 10; 38 } 39 printf("sum of number 1 in %d is %d.\n", N, sum); 40 return EXIT_SUCCESS; 41 }
特点:考虑了1-N各个数字之间的关系,对于不同的位数bits的数,可以通过统计每个位上的“1”的次数来求解,这需要找到他们的数学规律,可以采用归纳法来求解。这道题是先把问题转化为数学问题思考,再转回编程实现。下面为思考过程(对于不同位数通过找例子测试得到规律):
对于一位数a(a >= 0):
个位数上的1统计值:
a < 1: A = 0
a >= 1: A = 1
“1”的个数:A
对于二位数ba(b >= 1):
个位数上的1统计值:
a < 1: A = b
a >= 1: A = b + 1
十位数上的1统计值:
b = 1: B = a + 1
b > 1: B = 10
“1”的个数:A + B
对于三位数cba(c >= 1):
个位数上的1统计值:
a < 1: A = cb
a >= 1: A = cb + 1
十位数上的1统计值:
b = 0: B = 10 * c
b = 1: B = 10 * c + a + 1
b > 1: B = 10 * (c + 1)
百位数上的1统计值:
c = 1: ba + 1
c > 1: 100
“1”的个数:A + B + C
对于四位数dcba(d >= 1):
个位数上的1统计值:
a < 1: A = dcb
a >= 1: A = dcb + 1
十位数上的1统计值:
b = 0: B = 10 * dc
b = 1: B = 10 * dc + a + 1
b > 1: B = 10 * (dc + 1)
百位数上的1统计值:
c = 0: C = 100 * d
c = 1: C = 100 * d + ba + 1
c > 1: C = 100 * (d + 1)
千位数上的1统计值:
d = 1: D = cba + 1
d > 1: D = 1000
“1”的个数:A + B + C + D
对于五位数edcba(e >= 1):
个位数上的1统计值:
a = 0: A = 1 * edcb
a = 1: A = 1 * edcb + k + 1 (k = 0)
a > 1: A = 1 * (edcb + 1)
十位数上的1统计值:
b = 0: B = 10 * edc
b = 1: B = 10 * edc + a + 1
b > 1: B = 10 * (edc + 1)
百位数上的1统计值:
c = 0: C = 100 * ed
c = 1: C = 100 * ed + ba + 1
c > 1: C = 100 * (ed + 1)
千位数上的1统计值:
d = 0: C = 1000 * e
d = 1: C = 1000 * e + cba + 1
d > 1: C = 1000 * (e + 1)
万位数上的1统计值:
e = 0: X (不存在)
e = 1: D = 1000 * f + dcba + 1 (f = 0)
e > 1: D = 10000 * (f + 1) (f = 0)
“1”的个数:A + B + C + D + E
时间复杂度计算:O(logn)(对数函数实际上以10为底)
gprof 时间性能监视测试:基本上不耗费时间:0.00
版本三:逐步缩小数据规模,把大的数分解为更小的数的组合,利用递归的思想求解。
(此想法参考自一篇文章:http://www.cnblogs.com/jy02414216/archive/2011/03/09/1977724.html)
9 #include <stdlib.h> 10 #include <stdio.h> 11 12 typedef long long TYPE; 13 TYPE N = 1000000000; 14 15 TYPE count_number_1(TYPE n) 16 { 17 TYPE sum = 0; 18 TYPE bits = 0; 19 TYPE pow_bits = 1; 20 TYPE n_cpy = n; 21 while(n_cpy) { 22 bits++; 23 pow_bits *= 10; 24 n_cpy /= 10; 25 } 26 pow_bits /= 10; 27 if(bits > 1) { 28 TYPE top_bit_value = n / pow_bits; 29 TYPE low_bit_value = n % pow_bits; 30 // recursive
31 if(top_bit_value == 1) { 32 sum = count_number_1(low_bit_value) + 33 count_number_1(pow_bits - 1) + 34 low_bit_value + 1; 35 } else { 36 sum = count_number_1(low_bit_value) + 37 top_bit_value * count_number_1(pow_bits - 1) + 38 pow_bits; 39 } 40 } else { 41 // lowest bits 42 if (n < 1) 43 sum = 0; 44 else 45 sum = 1; 46 } 47 return sum; 48 } 49 50 int main(void) 51 { 52 TYPE i; 53 TYPE sum = 0; 54 sum += count_number_1(N); 55 printf("sum of number 1 in %lld is %lld.\n", N, sum); 56 return EXIT_SUCCESS; 57 }
时间复杂度计算:O(2^logn)(对数函数实际上以10为底)
gprof 时间性能监视测试:基本上不耗费时间:0.00
特点:考虑的数据规模的递减,通过递归思路不断缩小数据规模,最后只剩下个位数“1”含有个数的求解。但是数据过大时递归可能会导致堆栈溢出。下面为思考过程(对于不同位数通过找例子测试得到规律):
个位数a:f(a)
a < 1 : A = 0
a >= 1 : A = 1
十位数ba:
b = 1 : BA = f(a) + f(9) + a + 1
b > 1 : BA = f(a) + b * f(9) + 10
百位数cba:
c = 1 : CBA = f(ba) + f(99) + ba + 1
c > 1 : CBA = f(ba) + c * f(99) + 100
千位数dcba:
d = 1 : CBA = f(cba) + f(999) + cba + 1
d > 1 : CBA = f(cba) + d * f(999) + 1000
三、总结与思考
这道题目的第一种解法是最先想到的解法,符合编程的思维习惯,但是第二种解法确使运算效率提升到一个新的档次,第二种解法,从数学的思考角度去考虑,通过寻找规律来寻找求解。所以,有的复杂的算法,先转变为数学问题,通过数学规律或相互关系寻找新的数学上的解法,再编程实现,效率说不定能够快速提升。当然,第一种解法直观易懂,大家很容易推出问题,第二种解法不容易推出问题,但是效率确实更优的。当程序运算效率跟不上时,不防通过考虑下数学问题推导这种思维进行优化。
第三种解法参考别的文章的提示思路,采用的时递归缩小数据规模的想法,运用了分治的思想,这个方法实际测试效率时发现也效率和是相当高的,但时间复杂度这个值参考别人的计算结果,并未自己验证,因此无法准确的进行评估。
备注:
1.转载请注明出处:http://blog.csdn.net/chensilly8888/
2.全文源码均开源(在UBUNTU + GCC4.8.2下编译并测试通过),可下载或查看:https://github.com/chenxilinsidney/funnycprogram/tree/master/beauty_of_programming/count_number_1
3.有写错或写漏之处请指正,谢谢!