6

1秒以内に任意のn<=600の最短の加算チェーン（sac）をどのように計算できますか？

ノート

これは今月のコディリティに関するプログラミングコンテストです。

加算チェーンは、x ^ nを（連続した乗算によって）計算するための最も経済的な方法であるため、数値的に非常に重要です。

KnuthのArtofComputer Programming、Volume 2、Seminumerical Algorithmsには、加算チェーンといくつかの興味深いプロパティの優れた紹介がありますが、厳密なパフォーマンス要件を満たすことができるものは見つかりませんでした。

私が試したこと（ネタバレ注意）

最初に、（高度に分岐した）ツリーを構築しました（開始1-> 2->（3-> ...、4-> ...））。各ノードnについて、ルートからnへのパスがnの袋です。ただし、値が400を超える場合、実行時間はコーヒーを作る場合とほぼ同じです。

次に、そのプログラムを使用して、検索スペースを削減するためのいくつかの便利なプロパティを見つけました。これで、コーヒーを作りながら、600までのすべてのソリューションを構築することができます。しかし、nの場合、nまでのすべての解を計算する必要があります。残念ながら、codilityはクラス初期化の実行時間も測定します...

問題はおそらくNP困難であるため、ルックアップテーブルをハードコーディングすることになりました。でも、codilityがsacの作成を依頼したので、ルックアップテーブルを念頭に置いているかどうかわからないので、汚くて詐欺師のように感じます。したがって、この質問。

アップデート

ハードコーディングされた完全なルックアップテーブルが進むべき道だと思う場合、完全な計算/部分的に計算されたソリューション/ヒューリスティックが機能しないと思う理由を説明できますか？

4

2 に答える 2

4

この問題のゴールデン証明書を取得しました。問題はサイトでまだ利用できるため、完全な解決策は提供しません。代わりに、いくつかのヒントを提供します。

  1. ディープファースト検索を行うことを検討してください。
  2. n < 12509 ごとに最小のスターチェーンが存在します
  3. 検索スペースをどのように切り詰めるかを知る必要があります。
  4. 探しているチェーンの長さの適切な下限が必要です。
  5. すべてではなく、1 つのソリューションだけが必要であることを忘れないでください。

幸運を。

于 2012-04-21T13:10:52.807 に答える
1

加算チェーンは、x^n (連続乗算による) を計算する最も経済的な方法であるため、数値的に非常に重要です。

本当じゃない。これらは、常に x^n を計算する最も経済的な方法とは限りません。グラハムら。すべて が次のことを証明しました。

足し算チェーンの各ステップに、そのステップの数値の積に等しいコストが割り当てられている場合、コストを最小化する「バイナリ」足し算チェーンが表示されます。

x^n (mod m) を計算すると、状況は劇的に変化します。これは、暗号化などでよくあるケースです。

さて、あなたの質問に答えます。回答を含むテーブルをハードコーディングする以外に、ブラウアー チェーンを試すことができます。

Brauer chain (別名 star-chain) は、各新しい要素が前の要素といくつかの要素 (おそらく同じ) の合計として形成される加算連鎖です。Brauer chain は n < 12509 の場合は嚢です。Daniel を引用します。J.バーンスタイン：

Brauer のアルゴリズムは、「左から右への 2^k-ary メソッド」または単に「2^k-ary メソッド」と呼ばれることがよくあります。非常に人気があります。実装は簡単です。n のチェーンを構築することは、n のビットを検査するという単純な問題です。多くのストレージを必要としません。

ところで。Brauer の連鎖計算の適切な C/C++ 実装を知っている人はいますか? 私は、x^n と x^n (mod m) の両方のケースで、バイナリと Brauer のチェーンを使用した累乗時間の比較に部分的に取り組んでいます。

于 2013-04-06T21:09:13.933 に答える