11

ここでこの質問をするのが適切かどうかはわかりませんが、プログラミングとコードが関係するので、ここが適切な場所であることを願っています。

Programmers and Computer Science SE に投稿しようとしましたが、このサイトにリダイレクトされました。

問題は、フィボナッチ数を計算するレジスタ マシン コード/プログラムをどのように作成できるかということです。コードの構文は、実際には非常に単純です。

(以下は参考用です。長い投稿で申し訳ありません)
(詳細については、Richard Carl Jeffrey による Formal Logic: Its Scope And Limits に関する本を参照してください)

ウィキペディアによると、レジスタ マシンは、チューリング マシンと同様の方法で使用される抽象マシンの一般的なクラスです。(プロセッサ) レジスタは、CPU またはその他のデジタル プロセッサの一部として使用できる少量のストレージです。

レジスターを空のバケツとしてモデル化することで問題を単純化でき、ビー玉や岩をレジスター (「バケツ」) に入れることができます。ルールは、ビー玉をバケツに追加または削除して計算を実行することです。

ルールは次のとおり
です。 1. レジスター マシンは有限数のバケツを使用し、ビー玉は際限なく供給されます。
2. 各バケットは個別に識別できます。ビー玉は区別できる必要はありません。
3. レジスタ マシン プログラムは、有限の命令セットです。
- ビー玉をバケットに追加する (そして次の命令に進む)。
- または、ビー玉をバケツから取り除く (そして、できる場合は次の指示に進み、できない場合は別の指示に進みます)。
4. プログラムは、フローチャートまたは命令リストで記述できます。

これは、加算を実行するレジスタ マシン プログラムの例です。
A、B、C をバケットとします。
1. (-B; 2,4) は、バケツ B からビー玉を 1 つ取り除くことを意味し、できる場合は命令 2 に進み、できない場合は 4
に進みます。 3
3. (+C; 1) は、バケツ C にビー玉を 1 つ追加し、命令 1 に進むことを
意味します。できない場合
5. (+B; 4) は、バケツ B にビー玉を 1 つ追加し、手順 4 に進むことを意味します。

バケツ A に 3 個のビー玉があり、バケツ B に 2 個のビー玉があり、バケツ C に 4 個のビー玉があると仮定すると、簡単に示されます。このアルゴリズムを実行すると、|A|+|B| になります。= 3+2 = バケツ A と |B|+|C| に 5 個のビー玉 = 2+4 = バケツ B に 6 個のビー玉。

（上記の例が説明目的で十分に明確であることを願っています）

（さて、ここで質問です）

ここで、バケット A に n を入力すると、(バケット A にも) n 番目のフィボナッチ数を返すレジスタ マシン コードを書きたいと思います。フィボナッチ数は、0 (0 番目)、1 (1 番目)、1 = 0 + 1 (2 番目) などです。任意の数のバケットを使用できます。目標は、コードをできるだけ単純に記述することです (つまり、指示が最も少ない)。フィボナッチ再帰関係は、F(0)=0 および F(1)=1 の場合、F(n)=F(n-1)+F(n-2) です。

ここに私の試みとコードがあります:
私の考えは、バケット A を入力として、最後に出力 F(n) として使用することです (質問にはバケット A の出力が必要なので)、バケット B を「カウンター」として、バケット C を F として使用します。 (n-1) であり、バケット D は F(n-2) です。
1. (+C; 2)
2. (-A; 3,4)
3. (+B; 2)
4. (-D; 5,7)
5. (+A; 4)
6. (-C; 5,7)
7. (-B; 6,-)

しかし、残念ながら私のコードは最大 n=2 でしか機能しません。コードを n>2 で機能させるのに苦労しています。

私はこの昼夜を問わず考えてきました。誰かがこれについて私を助けてくれれば幸いです。ご不明な点がございましたら、お気軽にお問い合わせください。

よろしくお願いします！

4

4 に答える 4

4

以下は、11 命令でタスクを実行するレジスタ マシンをシミュレートする Python コードの例です。

# Store loop counter in 4
# Store F(n) in 1
# Store F(n+1) in 2
# Redistribute 2 to 1 and 3 to get F(n+1)+F(n),0,F(n+1)
# then move back to the order F(n+1),F(n+1)+F(n),0
code={1:(-1,2,3),   # Move n to 
      2:(+4,1),     #    bin 4 to act as loop counter
      3:(+2,4),     # Initialise bin 2 with F(1)=1
      4:(-4,5,0),   # Check for completion
      5:(-2,6,8),   # redistribute F(n+1)
      6:(+1,7),     #    to bin 1
      7:(+3,5),     #    and bin 3
      8:(-1,9,10),  # Move bin 1 to
      9:(+2,8),     #    bin 2
      10:(-3,11,4), # and bin 3
      11:(+1,10)}   #    to bin 1

def fib(n):
    buckets=[0,n,0,0,0]
    instruction_pointer = 1
    while instruction_pointer:
        ins = code[instruction_pointer]
        x = ins[0]
        if x>0:
            buckets[x]+=1
            instruction_pointer = ins[1]
        else:
            x=-x
            if buckets[x]>0:
                buckets[x]-=1
                instruction_pointer = ins[1]
            else:
                instruction_pointer = ins[2]
    return buckets[1]

for n in xrange(10):
    print n,fib(n)
于 2013-05-28T19:14:54.547 に答える
2

私はこれでクラックを取ります。機械語が必要なので、最も簡単な方法は、比較的低レベルの疑似コードを記述し、そこから機械語に取り組むことです。考える必要がある主な事柄は、ifステートメントを作成する方法、あるレジスタを別のレジスタに等しく設定する方法、およびループを実行する方法です。

これを行うためのより効率的な方法があることは事実上保証できますが、これは出発点であるべきです。

レジスタ 'n' に意図した反復回数 >2 が既にあると仮定して、私が行う疑似コードを次に示します。

A = 0
B = 1
C = 1
DO
  A = B + C // Note, this is really A = 0, A += B, A += C
  C = B  // Similarly, C = 0, C += B
  B = A  // B = 0, B += A
WHILE N- > 0

これを登録コードに変換するのは難しくありません。

1.   B+, 2 // B = 1
2.   C+, 3 // C = 1
3.   A-, 3, 4 // Get A down to 0 - not necessary, just here for clarity
4.   D-, 4, 5 // Get temporary variable D down to 0. - not necessary, just here for clarity
5.   B-, 6, 8 // Copy B into A (part of adding) and temporary variable D
6.     A+, 7  // A = B
7.     D+, 5  // D = B
8.   C-, 9, 10 // Add C into A = B
9.     A+, 8  // A += C
10.  N-, 11, -// Check your N count
11.    D-, 12, 13 // Copy D (the old B) into C
12.      C+, 11  // C = D
13.    A-, 14, 5 // Copy A into B
14.      B+, 13  // B = A

A と D を初期化した場所で、不要な 2 行を保持していることがわかります。これらは 0 から始まり、ループごとに 0 まで読み取られるため、これらの行は不要であり、最終結果は次のようになります。

1.   B+, 2                       // B = 1
2.   C+, 3                       // C = 1
3.   B-, 4, 6 // Copy B into A (part of adding) and temporary variable D
4.     A+, 5                     // A = B
5.     D+, 3                     // D = B
6.   C-, 7, 8 // Add C into A = B
7.     A+, 6                     // A += C
8.   N-, 9, -// Check your N count, or exit
9.     D-, 10, 11 // Copy D (the old B) into C
10.      C+, 9                   // C = D
11.    A-, 12, 3 // Copy A into B
12.      B+, 12                  // B = A

繰り返しますが、完璧ではないことは確かですが、近づけるはずです。お役に立てれば！

編集

質問を読み直すと、「N」が A で始まることがわかります。私のアルゴリズムはそれでは機能しないため、移動するには 2 行を前に追加する必要があります。また、書式設定が元の OP と一致しないことがわかったので、一致するように変更しました (スペースとコメントを与えるか取る):

1.   (-A; 2, 3) // Move the "N" value out of A into N
2.     (+N; 1)                     // N = A
3.   (+B; 4)                       // B = 1
4.   (+C; 5)                       // C = 1
5.   (-B; 6, 8) // Copy B into A (part of adding) and temporary variable D
6.     (+A; 7)                     // A = B
7.     (+D; 5)                     // D = B
8.   (-C; 9, 10) // Add C into A = B
9.     (+A; 8)                     // A += C
10.  (-N; 11, -)// Check your N count, or exit
11.    (-D; 11, 13) // Copy D (the old B) into C
12.      (+C; 11)                   // C = D
13.    (-A; 14, 5) // Copy A into B
14.      (+B; 13)                   // B = A
于 2013-05-28T19:08:31.673 に答える
0

わかりました。これでうまくいくと思います(わからない場合は、修正を試みます。) 関数が実行されたら、次の行に進みます (したがって、F1 が実行されて戻った後、すぐに F2 から始めます)。

Buckets:
A: Initial Value and Final Answer
B: First Counter
C: Second Counter
D: Adding bucket
I: Copy of C for next iteration
J: temporary bucket used for copying

1: +B,3 //loads the first counter
2: +C,4 //loads the second counter
3: -A,3,L
4: F1, 4
5: F2, 5
6: F3, 3

F1:: //makes a copy of C
  Fa: -C,Fb,Fd
  Fb: +I,Fcv //I is now the copy of C
  Fc: +J,Fa
  Fd: -J,Ff,Fg
  Ff: +C,fd
  Fg: return

F2:: //Sums B and C
  Fa: -B,Fc,Fb //adds up B 
  Fb: -C,Fd,Fe //adds up C
  Fc: +D,Fa
  Fd: +D,Fb 
  Fe: -D,Ff,Fg
  Ff: +C,Fe //Copies result to C
  Fg: return

F3:: //copys old C into B
  Fa: -I,Fb,Fc
  Fb: +B,Fa
  Fc: //return

L:: //puts value of C into A for result
  Fa: -C,Fb,DONE
  Fb: +A,Fa
于 2013-05-28T19:22:22.620 に答える