八达网

标题: 很久没出现题目了，今天想到一点点东西，拿来和大家讨论一下。 [打印本页]

作者: 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
问复杂度。。。。。。。
首先得解出来。。。。。。。
老夫时日不多了，这种问题还是留给年轻人吧。

答案很好找啊。。和到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
编程和数学的思路完全不一样啊。编程根本不需要什么解析解，可以用很暴力的方法穷举得出答案，当然如果码农 ...

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

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

作者: 啊当 时间: 2013-8-24 10:25
Log2n
不解释

作者: minker 时间: 2013-8-24 10:30

啊当发表于 2013-8-24 10:25
Log2n
不解释

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

作者: fell 时间: 2013-8-24 11:17
还好有播放器

欢迎光临八达网 (https://www.8-da.com/)