puzzle - 数値が 3 で割り切れるかどうかを調べる

Question

数値が 3 で割り切れるかどうかを判断するコードを記述します。関数への入力は 0 または 1 の単一ビットであり、これまでに受け取った数値が 3 で割り切れる数値のバイナリ表現である場合、出力は 1 である必要があります。ゼロ。

例:

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

これはインタビューの質問に基づいています。論理ゲートの図面をお願いしますが、これはスタック オーバーフローであるため、任意のコーディング言語を受け入れます。ハードウェア実装 (verilog など) のボーナス ポイント。

パート a (簡単):最初の入力は MSB です。

パート b (少し難しい):最初の入力は LSB です。

パート c (難しい): (a) と (b) では、どちらが速くて小さいですか? (理論的には Big-O の意味ではありませんが、実際にはより速く/より小さくなります。) 次に、より遅く/より大きなものを取り、より速く/より小さなものと同じくらい速く/小さくします。

Answer 1

数値が 11 の倍数であるかどうかを判断するには、10 進数を交互に足したり引いたりすることによって、かなりよく知られたトリックがあります。最後に得られる数が 11 の倍数である場合、最初の数も 11 の倍数です。

47278 4 - 7 + 2 - 7 + 8 = 0、11 の倍数 (47278 = 11 * 4298)
52214 5 - 2 + 2 - 1 + 4 = 8、11 の倍数ではない (52214 = 11 * 4746 + 8)

同じトリックを 2 進数にも適用できます。2 進数が 3 の倍数になるのは、そのビットの交互の合計も 3 の倍数である場合だけです。

4 = 100 1 - 0 + 0 = 1、3 の倍数ではない
6 = 110 1 - 1 + 0 = 0、3 の倍数
78 = 1001110 1 - 0 + 0 - 1 + 1 - 1 + 0 = 0、3 の倍数
109 = 1101101 1 - 1 + 0 - 1 + 1 - 0 + 1 = 1、3 の倍数ではない

MSB から始めるか LSB から始めるかに違いはないので、次の Python 関数はどちらの場合でも同じように機能します。ビットを 1 つずつ返す反復子が必要です。 multiplier1 と -1 の代わりに 1 と 2 を交互に使用して、負の数の剰余を取らないようにします。

def divisibleBy3(iterator):

    multiplier = 1
    accumulator = 0

    for bit in iterator:
        accumulator = (accumulator + bit * multiplier) % 3
        multiplier = 3 - multiplier

    return accumulator == 0

Answer 2

ここで...何か新しい...任意の長さの2進数（数千桁でも）が3で割り切れるかどうかを確認する方法.

-->((0))<---1--->()<---0--->(1)        ASCII representation of graph

写真から。

1. 二重円から始めます。
2. 1 または 0 を取得するとき、その数字が円の内側にあれば、その円の中にとどまります。ただし、数字が線上にある場合は、線を越えて移動します。
3. すべての数字が消費されるまで、ステップ 2 を繰り返します。
4. 最終的に二重円になった場合、2 進数は 3 で割り切れます。

これを使って 3 で割り切れる数を生成することもできます。これを回路に変換するのは難しいとは思いません。

グラフを使用した1つの例...

11000000000001011111111111101 は 3 で割り切れます (再び二重円になります)

自分で試してみてください。

2 進数を 10 進数に変換する場合など、MOD 10 を実行する場合にも同様のトリックを実行できます。(10 個の円、それぞれ二重の円で囲まれ、モジュロから得られる 0 から 9 の値を表します)

編集:これは左から右に実行される数字のためのものですが、逆言語を受け入れるように有限状態マシンを変更することは難しくありません。

注:グラフの ASCII 表現では、() は 1 つの円を表し、(()) は 2 つの円を表します。有限状態マシンでは、これらは状態と呼ばれ、二重丸は受け入れ状態 (最終的に 3 で割り切れることを意味する状態) です。

Answer 3

へー

LSB の状態テーブル:

S I S' O
0 0 0  1
0 1 1  0
1 0 2  0
1 1 0  1
2 0 1  0
2 1 2  0

説明: 0 は 3 で割り切れます。0 << 1 + 0 = 0. S = (S << 1 + I) % 3and O = 1ifを使用して繰り返しS == 0ます。

MSB の状態テーブル:

S I S' O
0 0 0  1
0 1 2  0
1 0 1  0
1 1 0  1
2 0 2  0
2 1 1  0

説明: 0 は 3 で割り切れます。0 >> 1 + 0 = 0. S = (S >> 1 + I) % 3and O = 1ifを使用して繰り返しS == 0ます。

S'は上記とは異なりますが、OS'は同じケース (00 と 11) に対して 0 であるため、同じように機能します。O はどちらの場合も同じであるため、O_LSB = O_MSB であるため、MSB を LSB と同じくらい短くするには、またはその逆にするには、両方の中で最も短いものを使用します。

Answer 4

手作業で行う簡単な方法は次のとおりです。1 = 2 ² mod 3なので、正の整数ごとに1 = 2 ^{2nmod3が得られます。}さらに、2 = 2 ^{2n + 1} mod 3です。したがって、奇数ビット位置の1ビットをカウントし、この数に2を掛けて、偶数ビット位置の1ビット数を加算することにより、整数が3で割り切れるかどうかを判断できます。結果に加えて、結果が3で割り切れるかどうかを確認します。

例：57 _{10 =} 1110012 。奇数の位置に2ビット、偶数の位置に2ビットがあります。2 * 2 + 2 = 6は3で割り切れます。したがって、57は3で割り切れます。

質問c）を解決するための考えもここにあります。2進整数のビット順序を逆にすると、すべてのビットが偶数/奇数の位置に留まるか、すべてのビットが変化します。したがって、整数nのビットの順序を逆にすると、nが3で割り切れる場合に限り、3で割り切れる整数になります。したがって、質問a）の解は、質問b）の変更なしで機能し、その逆も同様です。うーん、多分これはどちらのアプローチが速いかを理解するのに役立つかもしれません...

Answer 5

算術モジュロ 3 を使用してすべての計算を行う必要があります。これが方法です。

MSB:

number=0
while(!eof)
    n=input()
    number=(number *2 + n) mod 3

if(number == 0)
    print divisible

最下位:

number = 0;
multiplier = 1;
while(!eof)
    n=input()
    number = (number + multiplier * n) mod 3
    multiplier = (multiplier * 2) mod 3

if(number == 0)
   print divisible

これは一般的な考えです...

さて、あなたの役割は、これが正しい理由を理解することです。

はい、自分で宿題をしてください ;)

Answer 6

mod 3これは、数値が整数クラスの容量を超えて大きくなるため、ここでは使用できないことを意味します。

アイデアは、数に何が起こるかに注目することです。右にビットを追加する場合、実際に行っていることは、左に 1 ビットシフトして新しいビットを追加することです。

左シフトは 2 を掛けることと同じで、新しいビットを追加することは 0 または 1 を追加することです。0 から開始すると仮定すると、最後の数値の modulo-3 に基づいてこれを再帰的に行うことができます。

last | input || next | example
------------------------------------
0    | 0     || 0    | 0 * 2 + 0 = 0
0    | 1     || 1    | 0 * 2 + 1 = 1
1    | 0     || 2    | 1 * 2 + 0 = 2
1    | 1     || 0    | 1 * 2 + 1 = 0 (= 3 mod 3)
2    | 0     || 1    | 2 * 2 + 0 = 1 (= 4 mod 3)
2    | 1     || 2    | 2 * 2 + 1 = 2 (= 5 mod 3)

---

左に少し追加するとどうなるか見てみましょう。まず、次のことに注意してください。

2 ²ⁿ mod 3 = 1

と

2 ²ⁿ⁺¹ mod 3 = 2

したがって、現在の反復が奇数か偶数かに基づいて、mod に 1 または 2 を追加する必要があります。

last | n is even? | input || next | example
-------------------------------------------
d/c  | don't care | 0     || last | last + 0*2^n = last
0    | yes        | 1     || 0    | 0 + 1*2^n = 1 (= 2^n mod 3)
0    | no         | 1     || 0    | 0 + 1*2^n = 2 (= 2^n mod 3)
1    | yes        | 1     || 0    | 1 + 1*2^n = 2
1    | no         | 1     || 0    | 1 + 1*2^n = 0 (= 3 mod 3)
1    | yes        | 1     || 0    | 2 + 1*2^n = 0
1    | no         | 1     || 0    | 2 + 1*2^n = 1

Answer 7

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

この最後の入力は であるべきではありません12か、それとも質問を誤解していますか?

Answer 8

実際、LSB メソッドを使用すると、これが簡単になります。C:

MSB メソッド:

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
  unsigned value = 0;
  char *p = input;
  if (*p == '1') {
    value &= 1;
  }
  p++;
  while (*p) {
    if (*p != ',') {
      value <<= 1;
      if (*p == '1') {
        ret &= 1;
      }
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

LSB 方式:

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
  unsigned value = 0;
  unsigned mask = 1;
  char *p = input;
  while (*p) {
    if (*p != ',') {
      if (*p == '1') {
        value &= mask;
      }
      mask <<= 1;
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

個人的には、これらのうちの 1 つが他のものと大きく異なるとは信じがたいです。

Answer 9

ネイサン・フェルマンはパートaとパートbで正しい方向に進んでいると思います（ただし、bには追加の状態が必要です。数字の位置が奇数か偶数かを追跡する必要があります）。

パートCの秘訣は、各ステップで値を否定することだと思います。lastつまり、0は0になり、1は2になり、2は1になります。

Answer 10

数字の合計が 3 で割り切れる場合、数字は 3 で割り切れます。

したがって、数字を追加して合計を取得できます。

• 合計が 10 以上の場合は、同じ方法を使用します
• 3, 6, 9 なら割り切れる
• 合計が 3、6、9 以外の場合、割り切れません