アドベント・オブ・コード&#-デイクローの仕掛け

13 日目: 爪の仕掛け (数学、数学、その他の数学)。

ソリューションへのリンク

今日のチャレンジは、気分転換のために Python で行われました。この選択は次の目的で行われました:
a) 私の Python をテストする / Python をもっと学ぶ
b) 今日は非常に重い数学パズルのように見えたので、Python が最適だと感じました。そして、私は間違っていませんでした。間違っていません - 電光石火の速さでした。

今日のパズルへようこそ、数学のレッスン 悲しい顔、これを解く方法が分かりませんでした (パート 2)。最初はブルートフォースでループしてみました (正しい「ルート」が見つかるまで、最大 100 回）。

予想通り、パート 1 ではうまくいきました。しかし、パート 2 では、これは当てはまらないとわかっていたので、戻って数学的アプローチを探しました。これはチームが私たちを押し進めているものに違いないという予感がありました。グーグルでいろいろ調べた結果、Cramers Rule (初めて聞きました) を見つけました。

課題は次のとおりです。

ボタンを押して賞品を獲得するための最小コストを計算します。

パート 1 では、ボタンを押してターゲットに到達できるかどうか、また、100 回押し以内に獲得できる賞品の最大量と、そのためのコストを決定します。

パート 2 では、大きな座標オフセットを処理することでパフォーマンスを最適化し、基本的に 100 回のボタン押下制限を取り除き、賞品の位置を奈落の底に押し込みます。

解決

クラマーの法則は、各マシンで賞品に到達するために爪を動かす方法を説明する一次方程式を効率的に解くことができるため、この問題を解決するための優れたアプローチであると思われます。クラマーの法則が適用される理由と方法を詳しく見てみましょう:

問題の内訳

各クレーンマシンには 2 つの方程式があります:

式 1 (ボタン A から):
a1 * A b1 * B = c1

式 2 (ボタン B から):
a2 * A b2 * B = c2

ここで、a1 と b1 はボタン A の X 軸と Y 軸に沿った移動、A は A ボタンが押された回数、c1 は目標位置ですX 軸上 (賞品の位置)。

ここで、a2 と b2 はボタン B の X 軸と Y 軸に沿った動き、B は B ボタンが押された回数、c2 は Y 軸上のターゲット位置 (賞品の位置) です。

それぞれのクレーンゲームについて、座標 (c1, c2) の景品にクローを合わせるための、ボタン A と B を押す回数 (ボタン A と B を押す必要がある回数) を求めます。 X 軸と Y 軸上。

クラマーの法則がなぜ役立つのか

クラマーの法則は、連立一次方程式を解くために特別に設計されています。連立一次方程式は、共通の変数を共有する 2 つ以上の方程式のセットであり、目標は、すべての方程式を一度に満たす変数の値を見つけることです。

もっと簡単に言うと:

物事の関係を説明する複数の方程式があると想像してください。

各方程式は同じ変数 (x と y など) を使用しており、すべての方程式を同時に真にするこれらの変数の値を見つけようとしています。

この場合、各マシンのボタン構成は 2x2 連立一次方程式として表すことができ、A (ボタン A が押される) と B (ボタン B が押される) という 2 つの未知数を解きます。

開発者は将来的に Cramer's Rule を使用することをどのようにして知ることができるでしょうか?

方程式系: 開発者が最初に行うことは、問題が線形方程式系を解く必要があることを特定することです。

パターン認識: 開発者は、これが 2x2 システムであり、クラマーの法則がそれを解決する簡単な方法であることを認識します。

*行列式と行列: * 彼らは、行列式を使用して線形方程式の未知数を解くことができ、行列式が 0 の場合は問題がある (解が存在しないか無限である) ことを示していることを思い出します。

シンプルさと明確さ: クレイマーの法則は、反復法や複雑な代数を必要とせずに、A と B の値を見つけるためのシンプルで直接的な方法を提供します。

例：初めてのクローマシン

ボタンの動きと賞品の位置は次のとおりです。

Button A moves the claw X+94, Y+34.
Button B moves the claw X+22, Y+67.
Prize location is at X=8400, Y=5400.

連立方程式があります:

94 * A + 22 * B = 8400   (Equation for X-axis)
34 * A + 67 * B = 5400   (Equation for Y-axis)

ステップ 1: 行列式を計算する 主な決定要因 D:
行列式 D は次の式を使用して計算されます:

D = a1 * b2 - a2 * b1

D = (94 * 67) - (34 * 22)
D = 6298 - 748
D = 5550

次に、次の式を使用して行列式 D_x を計算します。

D_x = c1 * b2 - c2 * b1

D_x = (8400 * 67) - (5400 * 22)
D_x = 562800 - 118800
D_x = 444000

ここで、次の式を使用して行列式 D_y を計算します。

D_y = a1 * c2 - a2 * c1

D_y = (94 * 5400) - (34 * 8400)
D_y = 507600 - 285600
D_y = 222000

ステップ 2: A と B を解く クラマーの法則を使用して、A と B を解決します:

A = D_x / D
B = D_y / D

A = 444000 / 5550
A = 80

B = 222000 / 5550
B = 40

ステップ 3: 有効な整数を確認する AもBも整数なので、このクレーンゲームで賞品を獲得できる可能性があります。

ステップ 4: 総コストを計算する ボタン A を押すコストは 3 トークン、ボタン B を押すコストは 1 トークンです。したがって、賞品を獲得するための合計費用は次のとおりです:

Button A moves the claw X+94, Y+34.
Button B moves the claw X+22, Y+67.
Prize location is at X=8400, Y=5400.

パート 2 - 同じロジックを使用しますが、唯一の違いは、賞品座標の X 軸と Y 軸の両方に 10^13 オフセットを追加することです。

それが大変なことであることは承知していますが、それを理解する/理解するまでにはかなりの時間がかかったと思います。チャットをしていただければ幸いです。Twitter までご連絡ください。

以上がアドベント・オブ・コード&#-デイクローの仕掛けの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。