問題タブ [taocp]

次に例を示します。

1. [00] 2009 年のバイナリ形式...
2. [05] どの文字が...
3. [10] 4 ビット量 -- 半バイト、または 16 進数...
4. [15] キロバイト...
5. [M13] x が 0 と 1 の任意の文字列の場合...
6. [M20] 証明するか反証するか…

[00]、[05]、[10]、[15]、[M13]、[M20] の意味は何ですか?

私が試してみました：

• グーグルtaocp exercises square brackets
• 角かっこで囲まれた数字のパターンを探します。
  • それらは両方とも増加および減少します
  • ほとんどが 5 の倍数ですが、すべてではありません。
  • Mが付いているものは時々現れます
  • M は唯一のプレフィックスです
  • コードは一意ではありません
• グーグル"the art of computer programming" exercises brackets
• グーグル"the art of computer programming" M13
  • M がマイルストーンを意味することを示すhttp://dl.acm.org/citation.cfm?id=1312683を表示します。
• グーグル"the art of computer programming" [00]
• 説明している本の付録を探す
• いくつかの質問の横にある>も考慮してください

運が悪い！

次のフレーズの「lg」はどういう意味ですか?

「... M _t [ x ] を参照するとき、 xの最下位 lg tビットを無視します。」（クヌース、2005年、4～5ページ）。

文脈から、「lg t」は「t -1」を意味するように思われるので、lg 2 は 1 で、lg 5 は 4 になります。

参考文献

Knuth、DE (2005)。The art of computer programming: Volume 1, fascicle 1 : MMIX、新しい千年紀の RISC コンピューター。ニュージャージー州アッパーサドルリバー：アディソンウェズリー。

TAOCP の 3 巻を調べてみると、短いランダム シーケンスのソースが見つかりません。

また、すべての 2^16 値が返されるように const を検証するためのアルゴリズムと、場合によっては MIX プログラムもありました。少なくともそれは私が覚えていることです。また、(2^16)+1 は素数であるが、残念ながら (2^32)+1 も (2^64)-1 も素数ではないため、上記の再帰が機能するという事実も同じ一般的な領域にありました。

FWIW、const を iconst = 1/const (mod 0x10001) に置き換えると、逆の順序でシーケンスが生成されます。すなわち const*iconst%0x10001 = 1

単純な整数除算 (9/2=?) を実行しようとしていますが、MIX ビルダーが整数オーバーフロー エラーをスローします。私は何か間違ったことをしていますか？コードは次のとおりです。

私はThe Art of Computer Programming を読んでいます。私には理解できない高度な数学の瞬間がありますが、いくつかの演習は楽しいものでした。

それらの1つを行った後、答えに行きます。本が示唆するものよりも良かったか悪かったかを確認します（通常は悪い）、しかし、現在取り組んでいるものの答えがわかりませんとにかく伝えようとする。

本の質問と提案された解決策はここにあります

私が理解したのは、それtが「欠落している」要素の数であるか、一般的な定数である可能性があるということですが、私が本当に理解していないのは、それらのコンポーネントに基づいてそれらをソートするための一見恣意的な指示であり、私には回転のように見えます一見、元の順序に近づくことはできないため、ホイールを所定の位置に配置します。そして、(とりわけ) 対になった名前の一部を数字に置き換える決定 (ファイル G には、n−t < i ≤ n のすべての対 (i,xi) が含まれます)。

だから私の質問は、単純に、この答えからアルゴリズムを抽出するにはどうすればよいですか?

ちょっとした説明：

私はそれが何を目指しているのか、そしてそれをどのように C++ に翻訳するのかを理解しています。私が理解していないのは、なぜ入力ファイルのコピーをソートすることになっているのか、そうであればどの基準でソートするのか、ペアの片側を数値に変更する理由などです。

私は Knuth のThe Art of Computer Programmingに取り組んでいますが、MIX アセンブリ言語、特に DIV 演算子について質問があります。

133 ページで、彼は DIV 演算子がどのようにアキュムレータと拡張レジスタに影響を与え、これらのレジスタと入力メモリ セルの特定の状態が与えられるかの例を示します。質問は、このスタック オーバーフローの投稿で説明されています (そして答えられていると思います): How does division work in MIX?

私の問題は、答えた人が、rAX (レジスタ A と X) に格納されている 10 バイトの単語の値を、私が理解できない方法を使用して単一の数値に変換したことです。

手で除算を行う場合、バイトを単一の数値に変換すると、-210,501,825 が得られます (最小の種類のバイトを使用している場合 - Knuths book では 6 ビット (!))。

誰かがこの変換について教えてくれますか?

ありがとう、サム

mysql の gen_lex_hash.cc を読んでいますが、説明がわかりません:

提示されたアルゴリズムのアイデアは 、Donald E. Knuth の「The Art of Computer Programming」 第 3 巻「ソートと検索」で参照できます (第 6.3 章「デジタル検索」 - 章の名前と番号は 、ロシア語版からの逆翻訳です :))

以上の流れでは、詳細が理解できず、詳しい説明が見当たらない。

これを理解するために、プログラムをデバッグしましたgen_lex_hashが、次のように何も役に立ちません。

1. 0,-1どういう意味ですか？

アドバイスをいただければ幸いです。