1的数目.pdf
《1的数目.pdf》由会员分享,可在线阅读,更多相关《1的数目.pdf(13页珍藏版)》请在文库网上搜索。
1、写书评, 赢取 编程之美-微软技术面试心得 1 的数目 给定一个十进制正整数 N,写下从 1 开始,到 N 的所有整数, 然后数一下其中出现的所有“1”的个数。 例如: N= 2,写下 1,2。这样只出现了 1 个“1”。 N= 12,我们会写下 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12。这样,1 的个数是 5。 问题是: 1. 写一个函数f (N) , 返回1到N之间出现的“1”的个数,比如f (12) =5。 2. 在32位整数范围内, 满足条件“f (N) = N”的最大的N是多少? 写书评, 赢取 编程之美-微软技术面试心得 分析与解法 【 问题
2、1 的解法一】 这个问题看上去并不是一个困难的问题,因为不需要太多的 思考,我想大家都能找到一个最简单的方法来计算 f(N),那就 是从 1 开始遍历到 N,将其中每一个数中含有“1”的个数加起来, 自然就得到了从 1 到 N 所有“1”的个数的和。写成程序如下: 代码清单 2-9 ULONGLONG Count1InAInteger(ULONGLONG n) ULONGLONG iNum = 0; while(n != 0) iNum += (n % 10 = 1) ? 1 : 0; n /= 10; return iNum; ULONGLONG f(ULONGLONG n) ULONGLO
3、NG iCount = 0; for (ULONGLONG i = 1; i =1,那么 f(N)都等于 1,如果 N=0,则 f(N) 为 0。 再看 2 位数的情况。 如果 N=13,那么从 1 到 13 的所有数字:1、2、3、4、5、6、 7、8、9、10、11、12、13,个位和十位的数字上都可能有 1,我 们可以将它们分开来考虑,个位出现 1 的次数有两次:1 和 11, 十位出现 1 的次数有 4 次: 10、 11、 12 和 13,所 以 f (N) =2+4=6。 要注意的是 11 这个数字在十位和个位都出现了 1, 但是 11 恰好在 个位为 1 和十位为 1 中被计算了
4、两次,所以不用特殊处理,是对 的。再考虑 N=23 的情况,它和 N=13 有点不同,十位出现 1 的次 数为 10 次,从 10 到 19,个位出现 1 的次数为 1、11 和 21,所以 f(N)=3+10=13。通过对两位数进行分析,我们发现,个位数出 现 1 的次数不仅和个位数字有关,还和十位数有关:如果 N 的个 位数大于等于 1,则个位出现 1 的次数为十位数的数字加 1;如果 N 的个位数为 0, 则个位出现 1 的次数等于十位数的数字。 而十位 数上出现 1 的次数不仅和十位数有关,还和个位数有关:如果十 位数字等于 1,则十位数上出现 1 的次数为个位数的数字加 1;如 果十
5、位数大于 1,则十位数上出现 1 的次数为 10。 f(13) = 个位出现1 的个数 + 十位出现1 的个数 = 2 + 4 = 6 ; f(23) = 个位出现1的个数 + 十位出现1 的个数 = 3 + 10 = 13 ; f(33) = 个位出现1的个数 + 十位出现1 的个数 = 4 + 10 = 14 ; f(93) = 个位出现1 的个数 + 十位出现1 的个数 = 10 + 10 = 20 ; 接着分析 3 位数。 写书评, 赢取 编程之美-微软技术面试心得 如果 N = 123: 个位出现 1 的个数为 13:1, 11, 21, , 91, 101, 111, 121 十
6、位出现 1 的个数为 20:1019, 110119 百位出现 1 的个数为 24:100123 f(23)= 个位出现 1 的个数 + 十位出现 1 的个数 + 百位出 现 1 的次数 = 13 + 20 + 24 = 57; 同理我们可以再分析 4 位数、 5 位数。 读者朋友们可以写一写, 总结一下各种情况有什么不同。 根据上面的一些尝试,下面我们推导出一般情况下,从 N 得 到 f(N)的计算方法: 假设 N=abcde,这里 a、b、c、d、e 分别是十进制数 N 的各 个数位上的数字。如果要计算百位上出现 1 的次数,它将会受到 三个因素的影响:百位上的数字,百位以下(低位)的数字
7、,百 位(更高位)以上的数字。 如果百位上的数字为 0,则可以知道,百位上可能出现 1 的次 数由更高位决定,比如 12 013,则可以知道百位出现 1 的情况可能 是 100199,1 1001 199,2 1002 199,11 10011 199, 一共有 1 200 个。也就是由更高位数字(12)决定,并且等于更高 位数字(12)当前位数(100)。 写书评, 赢取 编程之美-微软技术面试心得 如果百位上的数字为 1,则可以知道,百位上可能出现 1 的次 数不仅受更高位影响,还受低位影响,也就是由更高位和低位共同 决定。 例如对于 12 113, 受更高位影响, 百位出现 1 的情况
8、是 100 199,1 1001 199,2 1002 199,11 10011 199,一共 1 200 个, 和上面第一种情况一样, 等于更高位数字 (12) 当前位数 (100) 。 但是它还受低位影响,百位出现 1 的情况是 12 10012 113,一共 114 个,等于低位数字(123)+1。 如果百位上数字大于 1(即为 29),则百位上可能出现 1 的次数也仅由更高位决定,比如 12 213,则百位出现 1 的可能性 为: 100199, 1 1001 199, 2 1002 199, 11 10011 199, 12 10012 199, 一共有 1 300 个, 并且等于更
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数目