【趣味编程】“至少出现一次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++;
		}// while
		tab0000[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;
			}// if

			ret1 += t*tab99[size];		//	对于循环第二步

			if(t>7)								//	对应循环第三步
				ret1 += 1*pow(9.0,size);
			else if(t==7)					//	对应循环第四步
			{
				ret1 = ret1 + tt;
				break;
			}// if
			n = tt;
		}

		if(n>=7)
			ret1++;

		/*****下面一段代码是比对函数,是这个题目的最为朴素的算法*****/
		n = i;
		while(n)
		{
			int t = n;
			while(t)
			{
				if((t%10)==7)
				{
					ret2 ++;
					break;
				}
				else
					t/=10;
			}// while
			n--;
		}
		/*****上面面一段代码是比对函数,是这个题目的最为朴素的算法*****/

		if(ret1!=ret2)
		{
			cout << i << " " << ret1 << " " << ret2 << " " << "不同" << endl;
			break;
		}// if
		cout << 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/blog PS:儿童节快乐!

31 May 2012

disqus 可能被墙~