1

これを削除対象としてマークします。削除してください。

4

5 に答える 5

1

あなた以外のことを実行できる疑似コードは、繰り返しがないことを保証します。

  1. 1 MB の割り当てを取得します。
  2. バイトごとにランダムに設定します。
  3. " " として stdout にエコーし0.<bytes as integer string>ます (非常に長くなります)。
  4. ＃2に行く

あなたの「同じ数を決して返さない」ことは保証されていませんが、Random の適切な実装を前提として、非常にありそうにありません (2^8192 分の 1)。

于 2011-09-13T03:49:46.280 に答える
1

約 100 万文字を割り当て、最初は 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

メソッドは、最終的に 1 MB を超えるヒープ メモリを使用します。数値を表現するあらゆる方法で、1 MB のヒープに制約されている場合、値の数は有限です。可能な最大量のメモリを使用し、呼び出しごとに最下位ビットを 1 ずつ増やします。これにより、繰り返される数値を返す前に、できるだけ長く実行することが保証されます。

于 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 で十分です。巨大な巨大な整数を格納するので、ここでいいと思います。

（1文字列全て、2文字列全て、3文字列全てを生成するので、あなたのものとは異なります...だから、最後に生成された数字以外の状態は必要ないと思います。）

繰り返しますが、私は間違っているかもしれません。私はこれを試していません。

補遺

わかりました試してみます。これがRubyのジェネレーターです

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

私には大丈夫に見えます....

于 2011-09-13T03:46:31.487 に答える
0

C でプログラミングしている場合nextafter()、関数のファミリは、特定の値の前後に次の double を生成するのに役立つ Posix 互換関数です。正の値と負の値の両方を出力すると、約 2^64 の異なる値が出力されます。

値を出力する必要がある場合は、正確な表現のために %a または %A 形式を使用してください。printf(3) のマニュアル ページから: 「'a' 変換の場合、double 引数は [-]0xh.hhhhp±d... のスタイルで (文字 abcdef を使用して) 16 進表記に変換されます。」 「デフォルトの精度で十分です。基数 2 の正確な表現が存在する場合、値の正確な表現のために..."

昇順の乱数ではなく、乱数を生成したい場合は、Google で 64 ビット KISS RNG を検索してください。Java、C、Ada、Fortranなどでの実装は、Web 上で入手できます。64 ビットの KISS RNG 自体の周期は ~ 2^250 ですが、64 ビットの倍精度数はそれほど多くないため、いくつかの数は 2^64 の出力内に再表示されますが、隣接する値は異なります。一部のシステムでは、long double の値は 128 ビットです。他のものでは、80 または 96 のみです。long double を使用すると、2 つの乱数を各出力に組み合わせることで、出力されるさまざまな値の数を増やすことができます。

インタビューでのこの質問のポイントは、それを見たときにばかげた仕様を認識できるかどうかを判断することかもしれません.

于 2011-09-13T04:28:47.447 に答える