珍珠湾ART

标题: 程序竞赛 [打印本页]

作者: constant 时间: 2005-11-28 04:54
标题: 程序竞赛

难度：++++

一个长为n的数组，里面的数为1到n-1的整数。找出一个重复的值。

不够难？能够用的存储单元有限制：存在一个与n无关的c，使用的存储单元不超过c*log(n)。例如n是64位整数时，使用的存储单元不能超过8c bytes，即最多存c个64位整数。

作者: 乱弹 时间: 2005-11-28 15:44
标题: 一点疑问

这些数存在哪里呢？就是计算空间复杂度的时候，计不计入图灵机上input tape 的空间使用数。

当然我猜想你这里是要求用实际的程序，不过也有类似问题。

作者: constant 时间: 2005-11-28 19:42
标题: 回复：一点疑问

数组是 read only 的。可用内存是指数组以外能存能取的部分。

还忘了一个条件：程序的速度要求是 O(n)。

作者: QL 时间: 2005-12-1 05:00
标题: 回复：程序竞赛

Interesting question, can you hold off posting your answer?

作者: constant 时间: 2005-12-1 05:32
标题: Sure. How long do you need?

Sure. How long do you need?

作者: QL 时间: 2005-12-1 07:11
标题: 回复：Sure. How long do you need?

Hmmm, another ++++ problem. I'd like to try to solve them in the same order as they were raised.

作者: Archi 时间: 2005-12-4 11:08
标题: The problem is confusing

If there is only one redundant number, sum up the array. The number is Sum(array)-(1+2+..+(n-1)).

If there are two redundant numbers, calculate the usual sum and the sum of squares, we can resolve the two redundant numbers by solving two equations.

If the number of redundant numbers is unspecified and n can be arbitrarily large, I don't know how to do it in O(n).

欢迎光临珍珠湾ART (http://zzwav.com/)