minker 发表于 2013-8-24 09:28

很久没出现题目了，今天想到一点点东西，拿来和大家讨论一下。

本帖最后由 minker 于 2013-8-24 09:41 编辑

首先是一道老题：

　　0在这十句话里出现的次数是_____；
　　1在这十句话里出现的次数是_____；
　　2在这十句话里出现的次数是_____；
　　3在这十句话里出现的次数是_____；
　　4在这十句话里出现的次数是_____；
　　5在这十句话里出现的次数是_____；
　　6在这十句话里出现的次数是_____；
　　7在这十句话里出现的次数是_____；
　　8在这十句话里出现的次数是_____；
　　9在这十句话里出现的次数是_____；

这道题应该很多人都做过，没做过的试5分钟估计怎么也试出来了。这道题不是这个帖子的核心。

首先我们在上面这道题加一个每个人都应该默认的条件：空里只允许填0-9这几个数。

好，现在我们把这道题扩展，再写几句，变成
　　0在这(K+1)句话里出现的次数是_____；
　　1在这(K+1)句话里出现的次数是_____；
　　2在这(K+1)句话里出现的次数是_____；
　　……
　　K在这(K+1)句话里出现的次数是_____；
不好意思刚才脑子抽筋了，这道题解析解很明显，和上面基本一样，不考虑这个。这也不是我的初衷。

重要的是：假设我用计算机去编程算它，请问复杂度是多少？
显而易见，n^n的复杂度是一定可以完成的。但是这道题明显不需要如此可怕的复杂度。

请证明你的结论。

小小白 发表于 2013-8-24 09:35

金钱上你们难为吊死就算了，智商上也来？

=IF=MIND 发表于 2013-8-24 09:37

金钱上你们难为吊死就算了，智商上也来？

Springsun 发表于 2013-8-24 10:02

问复杂度。。。。。。。
首先得解出来。。。。。。。
老夫时日不多了，这种问题还是留给年轻人吧。

minker 发表于 2013-8-24 10:02

Springsun 发表于 2013-8-24 10:02 static/image/common/back.gif
问复杂度。。。。。。。
首先得解出来。。。。。。。
老夫时日不多了，这种问题还是留给年轻人吧。

答案很好找啊。。和到9是一样的。。

复杂度就是个算法的估计。。我是想不到N!以下的方法了，来讨论一下

八达通 发表于 2013-8-24 10:08

金钱上你们难为吊死就算了，智商上也来？

别愁BloodBrood 发表于 2013-8-24 10:12

屌丝没看懂

Springsun 发表于 2013-8-24 10:20

编程和数学的思路完全不一样啊。编程根本不需要什么解析解，可以用很暴力的方法穷举得出答案，当然如果码农有很好的数学功底倒是可以用解析解来优化。举个简单的例子就是求最大公约数，如果不知道“欧几里德算法”，肯定是用从1穷举到小的那个数为止。

minker 发表于 2013-8-24 10:24

Springsun 发表于 2013-8-24 10:20 static/image/common/back.gif
编程和数学的思路完全不一样啊。编程根本不需要什么解析解，可以用很暴力的方法穷举得出答案，当然如果码农 ...

我就是说的枚举。解析解很好得到。

我想问的是，这道题的枚举是什么复杂度的。

啊当 发表于 2013-8-24 10:25

Log2n
不解释

minker 发表于 2013-8-24 10:30

啊当 发表于 2013-8-24 10:25 static/image/common/back.gif
Log2n
不解释

求方法。。我连n!都没想出来，你瞬间就log n了。。太厉害了。。。怎么做的？

fell 发表于 2013-8-24 11:17

还好有播放器
页: [1]
查看完整版本: 很久没出现题目了，今天想到一点点东西，拿来和大家讨论一下。