【意趣编程】“至少出现一次7”的数

【趣味编程】“至少出现一次7”的数

班级q群上老师给的题目，突然给出来的，感觉还是蛮喜欢这样的题目的。

前几天，一个朋友参加google总部的一个电话面试。有一道题目很有意思，题目不难，但是挺考程序员的思维的。
给定一个正整数n，写一个算法计算从1到n之间有多少“至少出现一次7”的数。例如n=20，那么有两个出现7的数：7，17。

看了下，应该是组合题没错，脑子里天马行空，凌乱…觉得能找到一个O(N)算法就已经够优了，同学又说有logN的，改天讨论一下。

讨论的时候我有个组合的思路：
比如100
高位不能为7
那么十位为7，那么10种；如果各位为7，那么10种；减去重复的1，故结果是10+10-1=19.可很明显这是有漏洞的，因为如果不全是10的N次方就有很多情况要考虑。

当时嘴大，把“杨辉三角”都给摔出口了。其实组合的题目里经常会用到杨辉三角的，在之前和一个学电子的朋友聊天的时候说到了这个话题，他提出“杨辉三角”的时候，我还纳闷：杨辉三角一直都知道，却没有用到。原来“杨辉三角”有如此美丽的性质。他给我好好上了一课。

陈yin老师立刻怀疑：“杨辉三角”和这个题目有五毛钱的关系吗？- -狠狠的被鄙视了。

晚上十二点多，看完两集《百家讲坛 易中天品三国》，回过头来想这个问题。脑子还是天马行空的，什么动态规划都来了，因为组合问题里也经常有用到动态规划的思维。结果是动态规划是可以解题，因为假如ABCDE五位数，我们可以先算前N位数中有7的个数，然后来推算N+1位数的时候7的个数，但是我不行——绝望了，主要是某位大于7，等于7，小于7的情况没有搞定。

片刻之后有个发现，还是从n=100开始讲起，
从1到100中有7的总数无非：C(2,1)*9^1 + C(2,2)*9^0 = 18+1 = 19。中，相信你也会想到了吧。

推广一下，比如n201，

• 我们可以先算出0到100有sum个7的数，
• 因为我们只考虑了0到100，所以还要考虑100到200，其实跟前者是一样的，所以sum*2；
• 最后还要考虑200到201，其实就是考考0到1，因为前面的2可以省略了。所以总数很明显是sum*2+0 = 38。

  这个思路已经初具雏形了，所以不够严谨的思路是这样的，假如ABCDE，

  • 先算出0到10000的总数（这个很容易算），乘于A，这样就把 00000到A0000的7的总数算出来了。
  • 接着考虑A0000到ABCDE，我们把A甩掉，所以只需考虑0000到BCDE就行了。
  • 重复上面的步骤，直到只剩下E为止。

    上面的说法是不够严禁的，因为它没有考虑，不过已经不远了：

    • 利用杨辉三角预算10，100，1000，10000…..的7的位数，这个很简单，而且也很快；
    • 循环体：
      去最高位highest，取除去最高位的剩下的数left；
      总数+=数的总位数*相应的10^N的7的位数（在第一步有预算的） ；
      如果highest>7，（比较悲剧，因为还要继续算），考虑只有最高位位7，其他位不为7的情况，这个简单；
      如果highest=7，那恭喜你，结束运算了，就差点，总数+=left，因为第三步已经算出00000..到70000..，所以还要考虑70000…到7ABCD…，退出循环。
    • 最后如果left>7，总数还得+1。

      最朴素的算法数据n上了百万就尽显吃力了，明显应付不过来。上面的方法可以秒过。

      下面给出代码：

      int table[20][20]={0};//杨辉三角表void yanghui()//计算杨辉三角{table[0][0] = 1;int u,v,j;for(int i=1; i<11; i++){u = 0,v = table[i-1][0],j = 0;while(u!=0||v!=0){table[i][j] = u + v;u = table[i-1][j],v = table[i-1][++j];}// while}// for}int tab0000[20];//记录10，100，1000，10000.....的7的位数void filltab0000()//计算10，100，1000，10000.....的7的位数{for(int i=1; i<=8; i++)//只算到10^8是因为溢出{int t = 1,ret = 0;while(t<=i){ret += table[i][t] * pow(9.0,i-t);t++;}// whiletab0000[i] = ret;}// for}int main(){yanghui();filltab0000();for(int i=0; i<=100000000; i++){int n = i,size = log10(n*1.0),ret1 = 0,ret2 = 0;while(n>10){int t10 = pow(10.0,size);//对于循环第一步int t = n/t10;int tt = n%t10;if(tt==n)//防止x00yzd中间出现多个0的情况{size--;continue;}// ifret1 += t*tab99[size];//对于循环第二步if(t>7)//对应循环第三步ret1 += 1*pow(9.0,size);else if(t==7)//对应循环第四步{ret1 = ret1 + tt;break;}// ifn = tt;}if(n>=7)ret1++;/*****下面一段代码是比对函数，是这个题目的最为朴素的算法*****/n = i;while(n){int t = n;while(t){if((t%10)==7){ret2 ++;break;}elset/=10;}// whilen--;}/*****上面面一段代码是比对函数，是这个题目的最为朴素的算法*****/if(ret1!=ret2){cout << i << " " << ret1 << " " << ret2 << " " << "不同" << endl;break;}// ifcout << i << " " << ret1 << " " << ret2 << " " << "相同" << endl;}// for}
      摘录一下老师的思路，这个思路很具启发性，但还有一些细节问题没有说好，老师也在第二天补充说明了：我是在第二天才搞定，我们群里有个忒牛逼的数据库的老师，深夜里把答案甩在群里，第二天才看到，最后还是他先KO，非常的郁闷并且很不服。

      23:59:11
      对于一个数N，

      去掉个位的数字有N%10个，乘以1是个位为7的数量
      再去掉十位的数字有N%100个，乘以9是十位为7的数量（个位不能再取7，所以乘9）
      再去掉百位的数字有N%1000个，乘以81是百位为7的数量（个位或十位都不能再取7，所以乘9的平方）
      依次类推。。。

      例如2000内有7的个数=200+20*9+2*81=542

      对于个位大于等于7的数字，最后的结果还要+1

      本文完 2012-06-01 00:58

      捣乱小子 www.daoluan.net PS：儿童节快乐！