0

AIDJ という仮想コンピュータ用の乗算プログラムを作成しています。

任意の数の変数をサポートし、次の形式の操作 (プログラム) の任意のシーケンスを読み取って実行できます。

mk: <operation>

mkはマーカーで、以下からのみ取得する必要があります。

Increment: x(i) = x(i) + 1 
Decrement: x(i) = x(i) - 1 
Conditional Jump: if x!=0 goto <mk>
Assignment: x(i) = c (where c is any natural number)

潜在的な条件ジャンプとは別に、AIDJ はプログラムで記述された順序で操作を評価し、プログラムが完全に処理されると停止します。

c >= 1のプログラム ADD を例にとります。

00: x(1) = c
01: x(2) = d
02: x(2) = x(2) + 1
03: x(1) = x(1) - 1
04: if x(1) != 0 goto 02

たとえば、プログラム MULTIPLY with c >= 2 を考えてみましょう:

00: x(1) = d
01: x(1) = d - 1
02: x(2) = c
03: x(3) = c
04: x(2) = x(2) + 1
05: x(3) = x(3) - 1
06: if x(3) =! 0 goto 04
07: x(1) = d - 1
08: if x(3) =! 0 goto 03

c × d が c + c + … + c (d 加数) に等しいことを確認して、プログラム ADD を使用できるようにし、ADD が d-1 回実行されるようにします。計算が停止すると、x(2) は c × d に等しくなります。

c=3 および d=3の場合、次の値の表が生成されます。

| Command                   | x(1) | x(2) | x(3) |
--------------------------------------------------
| 00: x(1) = d              | 3    | -    | -    |
| 01: x(1) = d - 1          | 2    | -    | -    |
| 02: x(2) = c              | 2    | 3    | -    |
| 03: x(3) = c              | 2    | 3    | 3    |
| 04: x(2) = c + 1          | 2    | 4    | 3    |
| 05: x(3) = d - 1          | 2    | 4    | 2    |
| 06: if x(3) =! 0 goto 04  | 2    | 4    | 2    |
| 04: x(2) = c + 1          | 2    | 5    | 2    |
| 05: x(3) = d - 1          | 2    | 5    | 1    |
| 06: if x(3) =! 0 goto 04  | 2    | 5    | 1    |
| 04: x(2) = c + 1          | 2    | 6    | 1    |
| 05: x(3) = d - 1          | 2    | 6    | 0    |
| 06: if x(3) =! 0 goto 04  | 2    | 6    | 0    |
| 07: x(1) = d - 1          | 1    | 6    | 0    |
| 08: if x(3) =! 0 goto 03  | 1    | 6    | 0    |
| 03: x(3) = c              | 1    | 6    | 3    | 
| 04: x(2) = c + 1          | 1    | 7    | 3    |
| 05: x(3) = d - 1          | 1    | 7    | 2    |
| 06: if x(3) =! 0 goto 04  | 1    | 7    | 2    |
| 04: x(2) = c + 1          | 1    | 8    | 2    |
| 05: x(3) = d - 1          | 1    | 9    | 1    |
| 06: if x(3) =! 0 goto 04  | 1    | 9    | 1    |
| 04: x(2) = c + 1          | 1    | 9    | 1    |
| 05: x(3) = d - 1          | 1    | 9    | 0    |
| 06: if x(3) =! 0 goto 04  | 1    | 9    | 0    |
| 07: x(1) = d - 1          | 0    | 9    | 0    |
| 08: if x(3) =! 0 goto 03  | 0    | 9    | 0    |

上記のプログラムを変更して、乗算ではなく除算するようにするにはどうすればよいですか?

4

1 に答える 1

4

乗算はループで追加していますよね？除算とは、被除数の残りが除数よりも少なくなるまでループで減算することです。擬似コード:

# We're dividing a/b, getting the quotient c
c = 0
while a >= b
{
    a = a - b
    c = c+1
}
# End of loop
# The value of a is the remainder at this point

だからこれで行きなさい。まず、減算を実装します (これは、VM でのループ内のデクリメントです)。その後、残りを行います。

条件はゼロとの比較に制限されているため、減算 (ループ内のデクリメント) を介して a>=b のロジックを実装します。追加の変数を導入することを恐れないでください。アーキテクチャは機能不全に陥っているかもしれませんが、使用されるメモリに明示的な制限はありませんよね?

ループ条件 (ループ内のデクリメント) をループ本体 (ループ内のデクリメント) と組み合わせることもできます。それは彼らが高級言語で行う方法ではなく、実際の CPU で行う方法でさえありません。最新のすべての CPU はプリミティブとして整数比較を行っています。「デクリメント。除数の残りがゼロになる前にゼロに達した場合は、ループを終了して終了します」という行に沿ったもの。ただし、実際には、この種のマイクロ最適化 (存在しないアーキテクチャの場合も同様) は強く推奨されません。

また、宿題の場合は「宿題」のタグを付けてください。私には宿題の匂いがします。

編集：これがロジックです。3 つの変数を導入します。

  • x(1) は減分される被除数の実行中のコピーです
  • x(2) は商です - 最初はゼロで、インクリメントされます
  • x(3) は除数の実行ループ変数です。
  • d は被除数
  • c は除数です。
  • 定数 (ゼロなど) を変数に代入できますよね?

VM のプリミティブに対応する疑似コードを使用します。これを AIDJ 構文に変換します。つまり、ここで少なくともいくつかの作業を行う必要があります。# はコメントを示します。ラベル (goto 宛先など) は次のようにマークされます。

x(1) = d
x(2) = 0
x(3) = c

Main_Loop:

x(1) = x(1) - 1 # decrement the running copy of the dividend
x(3) = x(3) - 1 # decrement the running copy of the divisor
if x(3) != 0 goto Divisor_still_nonzero

# If we're here, this means we've reached the end of the divisor.
# Increment the quotient, reset the running divisor to the initial value

x(2) = x(2) + 1
x(3) = c

Divisor_still_nonzero:

# Now let's check if we've reached the zero on the dividend
if x(1) != 0 then goto Main_Loop

# If x(1) is zero then we end up here.
# Means we've exhausted the dividend.
# Now the value of x(2) is the quotient.
# The remainder is c minus x(3),
# but retrieving it was not a requirement.

実際には、最初に c と d がゼロまたは負かどうかも確認する必要があります。d が 0 の場合、コードは壊れます。最初の繰り返しでマイナスになり、変数がオーバーフローした場合にのみ終了します。c がゼロの場合、除算全体が不正です。

ネガの追加処理も必要です。

また、一部の教授は Stack Overflow を監視していることで知られていることにも注意してください。

于 2012-06-14T15:16:28.853 に答える