👩🏻‍🚒 💬 🍴 総当たりなしで整数除算で方程式を解く 😿 ☝🏾 👨🏿‍🤝‍👨🏽

最近、トースターに関する質問が出されました。これは、少し異なる解釈でここで説明するタスクに根ざしています。

プログラマーが時間通りにプロジェクトに合格し、賞品を受け取った。祝うために、彼らは自分たちを月に投げ入れ、すべてのお金でビールを買いました。彼らは同じ日にすべてを飲み、BTで続行することを決めましたが、もうお金が残っていませんでした。その後、ボトルを渡し、昨日の変更を追加し、再び昨日と同様にすべてを在庫に入れました。 SRとChetでも同じことが行われました。そして金ではお金はちょうど1本でした。考えた-1本のボトルの価格、彼らがコンテナをどれだけ取ったか（価格はセントなし）を覚えていました、そして誰も元々のお金の名前を挙げることができませんでした。このプロジェクトは大規模で大きなボーナスでした-それだけの価値はありません。イベントがこのように発展するためのPNの最小予算は？

次のように彼女を推論する

ネタバレ

連中は毎日現在の予算で許可されているだけの量のビールを購入したため（B、予算）-翌日の予算（NB、next_day_budget）は、コンテナの返却と昨日の変更からの収益から形成されました。 2つの変数は1つよりも複雑なので、1日の予算削減（BL、budget_loss）を考慮するように切り替えました。さらに

B L = （ P - R ） N

$BL =（P-R）N$ ここで、P、価格はビール1本のコストです。 R、返品は返品時のコンテナの価格、Nは1日あたりに購入したボトルの数です。

N = B / / P

$N = B // P$ 。その後、次のことを結論付けることができます。

B = N B + （ P - R ） （ B / / P ）

$B = NB +（P-R）（B // P）$

抽象的には次のような式になりました（1）：

x = a （ x / / b ） + c

$x = a（x // b）+ c$

そのような方程式を解くための徹底的な検索をせずにアプローチを見つけようとして、私は1時間以上を費やしましたが、最終的に本当に素晴らしい解決策を見つけました ~~が、本の余白は狭すぎ~~ます;）

この問題の優位性について幻想を抱かずに、その過程で受けた喜びを共有したいだけです。誰かがこれの代替方法または名前を知っているなら、私を啓発してください。私のような人たちと、せっかちな人たちと話し合うことをお勧めします。

この形式（2）の結果の方程式を考えます。

（ x - c ） / a = x / / b

$（x-c）/ a = x // b$

右側は整数値のみを取ることができるため、分子が左側の分母の倍数である場合にのみ式全体が意味を持ちます。これから、 xがcの値から始まり、次にステップaの値を持つ可能性があることは明らかです。

次に、式（1）を2つの関数として考えました

y 1 = x

$y1 = x$ そして

y 2 = a （ x / / b ） + c

$y2 = a（x // b）+ c$ 。それらが交差する引数で、それが解決策です。たとえば、写真を可能な限り最適に表示するように小さなパラメーター値を選択しました。したがって、 a = 3、 b = 7、 c = 9とします。

2番目の関数の段階的な性質により、グラフy1とy2は2つの点で交差します。x1 = 12とx2 = 15の場合、条件に従って、小さい方の最初の値に関心があります。したがって、徹底的な検索を行わずに交差領域を決定するために、3番目の関数を導入しました。これは、関数y2を下から制限し、次の方程式をもつ単なる直線です

y 3 = a / b （ x - （ b - 1 ） ） + c

$y3 = a / b（x-（b-1））+ c$ 。

ここで、2本の線（ y1とy3 ）の交点を見つけ、目的のxの制限から答えを調整することが残っています。確かに、条件に基づいて、分子の乗数の条件が式（2）の分母について満たされる値のみを取ることができます。

x = c + n a

$x = c + na$ ここで、 nは特定の自然因子です。これを行うには、簡単な方程式を解きます

x = a / b （ x - （ b - 1 ） ） + c

$x = a / b（x-（b-1））+ c$ 結果のルートが要件を満たさない場合は、最も近い適切なルートに移動します。補助関数y3には正の勾配があり、 y2のすべての値はその上にあるため、ルートは常に上方に調整する必要があります。したがって、この場合、線はx = 11.25（グラフ上の黒い点）で交差し、条件を満たす最も近い大きな値は12（赤い点）です。これが答えです。

Toasterの質問にはPythonタグがあったので、以下の関数を使用してこの問題を解決し、翌日の予算に基づいて当日の予算を見つけるためのスクリプトを示します。関数を必要な回数だけ適用すると、できれば答えが得られます！

def this_day_budget(next_day_budget): a = bottle_price - tare_return_price b = bottle_price c = next_day_budget x = (a - a*b + b*c)/(b - a) if (x - c) % a: # value does not match the increment x = ((xc)//a + 1) * a + c return x bottle_price = 7 tare_return_price = 4 party_duration_days = 5 last_day_budget = bottle_price for days_to_party_end in range(party_duration_days): if days_to_party_end == 0: current_budget = last_day_budget else: current_budget = this_day_budget(current_budget) print('first day budget was - %d' % current_budget)

結論の代わりに：

この例のタスクはパラメーター値として決定されました

a < b < c < x

$a <b <c <x$ 、および方程式自体

x = a （ x / / b ） + c

$x = a（x // b）+ c$ ; わずかな変更を加えた提案されたアプローチは、他の同様の場合にも適用可能です-出版物の目的は、一般的な場合の普遍的な解決策を導き出すことなく、原則自体を説明することだけでした-したがって、厳密に判断しないでください（Pythonコードを含む）。

総当たりなしで整数除算で方程式を解く

More articles: