-3

私はRobertSedwickによるアルゴリズムを読んでいます。

これが本です

ページ番号：214。

以下のテキストは、数値の2進表現からの参照です。

ここでRobertSedwickは、次のプログラムは2進数への対応に触発されていると述べました。以下に述べる定規を描くための非再帰的プログラム

void rule(int l, int r, int h)
  { 
    for (int t = 1, j = 1; t <= h; j += j, t++)
      for (int i = 0; l+j+i <= r; i += j+j)
        mark(l+j+i, t);
  }

図5.10の著者は、定規を非再帰的に描画するために、長さ1の描画マークとスキップ位置を交互に使用し、次に長さ2の描画マークと残りの位置をスキップするように交互に配置します。

上記について以下の質問があります。

  1. 私の質問は、プログラムが2進数への対応に触発されていると著者がどのように述べたかです。
  2. 図5.10で、著者は位置をスキップするとはどういう意味ですか？ここではどのポジションを参照していますか？
  3. 図5.10では、最初の図のマークは何ですか？

rule（0,8,3）で説明してください。

4

2 に答える 2

1

#1 について、ある範囲の数値を 2 進数で書き留め、下位の x ビット以外をすべてマスクすると、繰り返しパターン (例: x=4) が得られます。

 0 = 0000
 1 = 0001
 2 = 0010
 3 = 0011
 4 = 0100
 5 = 0101
...
14 = 1110
15 = 1111
16 = 0000
17 = 0001
...

一連の 1 で終わる数字を探すと、興味深いパターンが見つかります。上記を反時計回りに 90 度回してスペースを節約します。

010101010101010101010101010101010101010101010101
001100110011001100110011001100110011001100110011 ....
000011110000111100001111000011110000111100001111
000000001111111100000000111111110000000011111111

1 の末尾の文字列のみを ! に置き換えます。

0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!
001!001!001!001!001!001!001!001!001!001!001!001! ....
0000111!0000111!0000111!0000111!0000111!0000111!
000000001111111!000000001111111!000000001111111!

他のすべてをスペースに置き換えると、繰り返される定規パターンが得られます。

 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
   !   !   !   !   !   !   !   !   !   !   !   ! ....
       !       !       !       !       !       !
               !               !               !

考えてみると、一連の 1 の長さ (マークの長さに対応) がその発生頻度にどのように対応し、それがどのように上記のパターンにつながるかがわかります。

于 2012-09-10T19:15:14.970 に答える
0

ここで何かが欠けているのは、読者ではなく、このテキストの著者だと思います。本から投稿されたコードにはコメントがありません。特に、3 つのパラメーターの意味を正確に示す @param タグがありません。投稿された説明にも何かが欠けているようです。

＃2での私の推測は次のとおりです。定規を見ると、0.25または0.75インチよりも0.5インチの方が大きいマークがあります. 最初に 0.5 インチのマークを配置し、次に 1/4 インチのマークを配置するときに「位置をスキップ」します。これは、1/4 インチのマークの半分を描画する必要がないためです。たとえば、1" と 3" の間のマークを 1/4" ずつ数えて埋めると、次のようになります。

1.25 [スキップ] 1.75 [スキップ] 2.25 [スキップ],,...

別の言い方をすれば、1/4 インチのマークを配置するとき、実際には 4 分の 1 ではなく 0.5 インチでカウントしています。本から投稿されたコードでは、これがおそらくj+j内部ループに表示される理由です。これは、j が現在のマーカー値であることを示しています (最初は 1/4、次に 1/2、次に 1/8)。すべてが整数で行われるため、おそらく j=1 は 1/16" に対応し、2j、4j、8j はマーカー値です。

于 2012-09-10T10:58:03.733 に答える