4

次の機能を正確に説明してほしい。 

void ToBin(int n){
  if (n>1)
     ToBin( n/2 );
  printf( "%d", n%2 );
}

例:
I が入力された場合7、binary に変換するとどうなりますか (関数の動作) 111。

理解できるまで段階的な説明をお願いします。

編集
同じ機能ですが、結果をより明確に印刷します。

void ToBin( int n ){
   printf("%d/2= %d -> %d\n", n, n/2 ,n%2);
   if (n>1)
      ToBin( n/2 );
}
4

10 に答える 10

5

特に7の場合：

まず、n = 7 なので、n > 1 です。したがって、ToBin は n / 2 = 3 で再度呼び出されます。

n = 3 なので、n > 1 です。したがって、ToBin は n / 2 = 1 で再度呼び出されます。

ここで、n = 1 であるため、n は 1 より大きくありません。したがって、1 % 2 = 1 が出力され、制御は前のフレームに戻ります。

ここでは、n = 3 と 3 % 2 = 1 が出力され、制御は再びフレームをジャンプして戻ります。

ここでは、n = 7、および 7 % 2 = 1 が出力され、関数が終了し、ToBin フレームが残っていないため、最初に ToBin を呼び出した関数に制御が戻されます。

一般に、この関数は次のように機能します。

数値の 2 進数表現は、元の数値の最下位ビットが追加された、その半分の数値の下限の 2 進数表現と同じです。

したがって、関数は、その値が 1 ビットになるまで、入力の半分のフロアのバイナリ表現を繰り返し取得します。次に、数値の最上位ビットであるそのビットが出力され、その後、各ビットが重要度の降順で出力されます。

于 2013-08-07T05:09:23.333 に答える
3

これは再帰的な関数呼び出しです。n%2基本的には、整数の最後のビット (バイナリ表現) を切り取るだけです。(2 は 2 進数であるため、基数は 2 つ考えられます)。はn/2(整数除算によって) 最下位ビットを削除し、それを次の再帰レベルに渡します。

したがって、各再帰レベルは、あるレベルで整数が 1 でなくなるまで、渡された整数の最下位ビットを削除します。1 の場合、if失敗し、それ以上の再帰呼び出しは行われません。これで、再帰がロールバックされます。最初にprintf最後の再帰呼び出しが実行され、呼び出し元から渡された整数の最下位ビットが出力されます。したがって、レベルでは基本的に数値kのk^ 番目のビットが出力されます。k番目のレベルでは、k-1再帰関数呼び出しのチェーンで最下位ビットが削除され、レベルの呼び出しには最下位ビットが削除されkた整数があるk-1ためです。したがって、あらゆるレベルで、printf再帰が先頭に戻るまで、渡された整数の LSB を出力します。

これがグラフィカルな表現です。のためにn = 10。のバイナリはnです1010。理解を深めるために、さまざまな値でそのような図を自分で描いてみてください。

          ToBin (10 = 1010)          print 10%2 = 0
             |                           ^
             call ToBin (10/2)           |
             |                           |
             V                           |
          ToBin (5 = 101)            print 5%2 = 1
             |                           ^
             call ToBin (5/2)            |
             |                           |
             V                           |
          Tobin (2 = 10)             print 2%2 = 0
             |                           ^
             call ToBin (2/2)            |
             |                           |
             V                           |
          ToBin (1 = 1)              print 1%2 = 1
             |                           ^
             if condition fails,         |
             |  roll back.               |
             |                           |
             |                           |
             +------>------>------>------+
于 2013-08-07T05:25:43.393 に答える
2

数値の基数 2 表現を見つけるには、次のようなビットを探しますb0...bn。

n = bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0

ここで、 を見つけることに焦点を当てますb0, b1, ..., bn。ご了承ください

(bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) % 2 = b0

なぜならb0 * 2^0 % 2 = b0、bj * 2^j % 2 = 0いつj >= 1から、2^j % 2 = 0もしj >= 1。そう、

       n = bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0 
=> n % 2 = (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) % 2 = b0

私たちはそれを発見しましたb0 = n % 2。この重要な事実ナンバーワン。

では、2 で割ってみましょう。

n / 2 = (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0)
      = bn * 2^(n - 1) + b_(n - 1) * 2^(n - 2) + ... + b1 * 2^1

では、ここで止めましょう。のバイナリ表現を詳しく見てみましょうn / 2。n最後のビットを切り落としたのバイナリ表現とまったく同じであることに注意してください。あれは

    n = bn b_(n-1) ... b1 b0
n / 2 =   b_n b_(n-1) ... b1

これが 2 番目の重要な事実です。

それでは、学んだことをまとめてみましょう。

  1. の 2 進数表現nは、 の 2 進数表現n / 2の最後の桁がn追加された の 2 進数表現です。これは重要な事実その 2 からです。

  2. のバイナリ表現の最後の桁は、 をn計算することで計算できますn % 2。これは重要な事実 1 からです。

when n = 0. その場合、 のバイナリ表現はnです0。で割るというルールを使用しようとすると、22 で割ることをやめることはありませんn = 0。

したがって、 のバイナリ表現を計算するにはn、まず のバイナリ表現を計算しn / 2、次に の結果を追加しますがn % 2、 の場合は必ず処理してn = 0ください。コードでそれを書きましょう：

// print binary representation of n
void ToBin(int n) {
    if(n > 1) { // this is to handle zero!
        ToBin(n / 2); // this will print the binary representation of n
    }
    print(n % 2); // this will print the the last digit
}
于 2013-08-07T05:22:45.953 に答える
2 
order    call    print
  1    ToBin(7)    1
          ↓        ↑
  2    ToBin(3)    1
          ↓        ↑
  3    ToBin(1) →  1

それが再帰です

たぶん、再帰方程式を見つける必要があります。

于 2013-08-07T05:19:47.167 に答える
1 
ToBin(7)
n=7 if(7>1)
    ToBin(7/2=3) call ToBin(3)
    {
     ToBin(3)
     n=3 if(3>1)
     ToBin(3/2=1) call ToBin(1)
     {
       ToBin(1)
       n=1 if(1>1)
         false
       print n%2=> 1%2= 1
      }     
    print n%2=> 3%2= 1
    }
print n%2=> 7%2= 1
于 2013-08-07T05:19:21.390 に答える
1

あなたは7を入力します

call 1) 7>1 true ,call ToBin(7/2)=ToBin(3.5) , pending print(7%2)=1
call 2) 3>1 true ,call ToBin(3/2)=ToBin(1.5) , pending print(3%2)=1
call 3) 1>1 false ,dont call ToBin(1/2), print(1%2)=1

、

print 1
pop function activation record for call 3)
pending print 1
pop function activation record for call 2)
pending print 1
pop function activation record for call 1)
So your output is 111
于 2013-08-07T05:11:52.343 に答える
1

再帰により、他の場合よりも理解しにくくなっている可能性があります。まず、ステートメントを並べ替えると、次のようになることに注意してください。

void ToBin(int n){
  printf( "%d", n%2 );
  if (n>1)
     ToBin( n/2 );
}

これで、数字が逆順で出力されます。もちろん、これはあなたが望むものではありませんが、再帰呼び出しが最後にあるので、反復形式に変換するのは簡単です:

void ToBin(int n) {
  do {
    printf( "%d", n%2 );
    n = n/2;
  } while(n > 1);
}

このコードから、次のことがわかります。

  • 2 を法とする数値を出力します。
  • 数値を 2 で割ります。
  • 数値が 1 より大きい場合は、繰り返します。

基数 10 の数値が与えられた場合、10 で割ることができると考えてください。剰余と被除数は、それぞれ最下位桁と 1 桁シフトされた数値です。これは 2 進数でも機能します。ただし、10 で除算するのではなく、2 で除算します。

基本的に、アルゴリズムは次のようになります。

  • 最下位桁を出力します。
  • 数値を 1 桁シフトします。
  • 数が 1 より大きい場合は、繰り返します。

これを再帰形式で書き、再帰と出力を入れ替えると、最上位から最下位の順に数字を出力します。ほら。

于 2013-08-07T05:13:54.947 に答える
0

その再帰出力剰余 (% 操作) を次のように 2 で除算します。

ToBin()n入力引数が 1 より大きくなるまで自分自身を呼び出しています

 2 | 7
 ------     remainder   /|\
 2 | 3  ---> 1           |    down to top
 ------                  |
   | 1  ---> 1           |
     -------------------->
于 2013-08-07T05:13:10.653 に答える
0

n が 7 の場合、各レベルでの再帰呼び出しは次のとおりです。

 1.ToBin(7)--> 2. ToBin(3) --> 3. ToBin(1)

値が返されるようになりました。7%2 が 1 であるため、最初のケースでは 1 です。


2 番目のケースでは 3%2 が 1 であるため 1、3 番目のケースでも 1%2 が 1 であるため 1 です。

したがって、111が出力です

注:すべての再帰呼び出しには、そのスタックに独自の n があるため、n は最初の呼び出しでは 7、2 番目の呼び出しでは 3、3 番目の呼び出しでは 1 です。

于 2013-08-07T05:13:22.963 に答える
0

関数ToBinは再帰（関数呼び出し自体）を使用し、このアルゴリズムを使用します：

基数 10 の整数から基数 2 (バイナリ) の同等の数値に変換するには、数値を 2 で割り、余りを最下位ビットにします。(整数) の結果は再び 2 で除算され、その剰余は次の最下位ビットになります。このプロセスは、商がゼロになるまで繰り返されます。

于 2013-08-07T05:13:41.483 に答える