1

将此标记为删除。请删除。

4

5 回答 5

1

除了保证不重复之外，可以做你想做的事的伪代码。

  1. 以您的 1 MB 分配。
  2. 随机设置每个字节。
  3. 回显到标准输出为“ 0.<bytes as integer string>”（会很长）
  4. 转到#2

不能保证您的“从不返回相同的数字”，但假设 Random.

于 2011-09-13T03:49:46.280 回答
1

分配大约一百万个字符并将它们最初设置为 all 0。

然后对函数的每次调用都会简单地增加数字并返回它，例如：

# Gives you your 1MB heap space.

num = new digit/byte/char/whatever[about a million]

# Initialise all digits to zero (1-based arrays).

def init():
    for posn ranges from 1 to size(num):
        set num[posn] to 0

 

# Print next value.

def printNext():
    # Carry-based add-1-to-number.
    # Last non-zero digit stored for truncated output.

    set carry to 1
    set posn to size(num)
    set lastposn to posn

    # Keep going until no more carry or out of digits.

    while posn is greater than 0 and carry is 1:
        # Detect carry and continue, or increment and stop.

        if num[posn] is '9':
            set num[posn] to '0'
            set lastposn to posn minus 1
        else:
            set num[posn] to num[posn] + 1
            set carry to 0
        set posn to posn minus one

    # Carry set after all digits means you've exhausted all numbers.

    if carry is 1:
        exit badly

    # Output the number.

    output "0."
    for posn ranges from 1 to lastposn
        output num[posn]

的使用lastposn可防止输出尾随零。如果您不关心这一点，您可以删除其中的每一行lastposn并从中运行输出循环1 to size(num)。

每毫秒调用一次将给你大约 10多个运行时间 - 大数字导致运行时间比宇宙年龄大的运行时间。

我不会采用您基于时间的解决方案，因为时间可能会改变 - 考虑夏令时或夏季时间以及人们因漂移而调整时钟。

这是一些演示它的实际 Python 代码：

import sys
num = "00000"
def printNext():
    global num
    carry = 1
    posn = len(num) - 1
    lastposn = posn

    while posn >= 0 and carry == 1:
        if num[posn:posn+1] == '9':
            num = num[:posn] + '0' + num[posn+1:]
            lastposn = posn - 1
        else:
            num = num[:posn] + chr(ord(num[posn:posn+1]) + 1) + num[posn+1:]
            carry = 0
        posn = posn - 1

    if carry == 1:
        print "URK!"
        sys.exit(0)

    s = "0."
    for posn in range (0,lastposn+1):
        s = s + num[posn:posn+1];
    print s

for i in range (0,15):
    printNext()

和输出：

0.00001
0.00002
0.00003
0.00004
0.00005
0.00006
0.00007
0.00008
0.00009
0.0001
0.00011
0.00012
0.00013
0.00014
0.00015
于 2011-09-13T04:08:54.450 回答
0

如果您使用 C 编程，则nextafter()函数系列是 Posix 兼容函数，可用于在任何给定值之后或之前生成下一个 double。如果您同时输出正值和负值，这将为您输出大约 2^64 个不同的值。

如果您需要打印出这些值，请使用 %a 或 %A 格式进行精确表示。从 printf(3) 手册页：“对于 'a' 转换，双参数转换为样式 [-]0xh.hhhhp±d... 的十六进制表示法（使用字母 abcdef）...” “默认精度就足够了如果存在以 2 为底的精确表示，则获取该值的精确表示..."

如果您想生成随机数而不是按顺序升序的数字，也许可以在 google 搜索 64-bit KISS RNG。网络上提供了 Java、C、Ada、Fortran等的实现。64位KISS RNG本身的周期是~2^250，但是64位双精度数并不多，所以有些数会在2^64输出内重新出现，但相邻值不同。在某些系统上，长双精度数具有 128 位值；在其他情况下，只有 80 或 96。使用 long doubles，您可以通过将两个随机数组合到每个输出中来相应地增加不同值输出的数量。

面试中这个问题的目的可能是弄清楚当你看到一个愚蠢的规范时，你是否能认出它。

于 2011-09-13T04:28:47.447 回答
0

您的方法最终会使用超过 1mb 的堆内存。每种表示数字的方式，如果您受到 1mb 堆的限制，那么只有有限数量的值。我会尽可能多地使用内存，并在每次调用时将最低有效位加一。这将确保在返回重复号码之前尽可能长时间地运行。

于 2011-09-13T03:40:19.727 回答
0

是的，因为没有随机要求，所以您有很大的灵活性。

我认为这里的想法非常接近于通过一些修改枚举正则表达式[0-9]*上的所有字符串：

  • 真正的字符串以序列开头0.

  • 你不能以 0结尾

那么你会如何枚举呢？一个想法是

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.11 0.12 0.13 0.14 0.15 ... 0.19 0.21 0.22 ... 0.29 0.31 ... 0.99 0.101 0.102 ...

您在这里需要的唯一状态是我认为的整数。只是巧妙地跳过最后的那些零（真的不难）。1 MB 的内存应该没问题。它存储了一个巨大的整数，所以我认为你在这里会很好。

（它与你的不同，因为我生成所有一个字符串，然后所有两个字符串，然后所有三个字符串，......所以我相信除了生成的最后一个数字之外不需要状态。）

那么我可能又错了；我没试过这个。

附录

好的，我会试试的。这是Ruby中的生成器

i = 0
while true
  puts "0.#{i}" if i % 10 != 0
  i += 1
end

在我看来还可以......

于 2011-09-13T03:46:31.487 回答