プログラミングの競争でしばらく前に、私は不可解な問題に遭遇しました、そしてそれはそれ以来私を悩ませてきました。私はそれを逐語的に覚えていませんが、私はそれを再現するために最善を尽くします：
ジャックは数直線の0から始まり、いずれかの方向に1ユニットジャンプします。彼が連続してジャンプするたびに、前のジャンプより1単位長くなり、どちらの方向にもジャンプできます。数値を取得し、ジャックがその数値に到達するために行うジャンプの最小数を返すプログラムを作成します。
これが良い質問と見なされない場合、またはタイトルが誤解を招くと見なされる場合は、事前にお詫び申し上げます。
@supercat の正確で高速なソリューションについて詳しく説明し、そのような合計の長さを計算するだけでなく、最小の長さの合計を計算するアルゴリズムについて説明したいと思います。
t_k := 1 + 2 + 3 + ... + k >= |n| となる最小の整数 k を見つけます。t_k は |n| と同じパリティを持ちます。次に、体系的な方法で t_k の被加数の符号を反転させて合計 n にします。
詳細はこちら。t_k = k(k + 1)/2、三角数であることに注意してください。t_k = |n| の設定 k について解くと、(-1 + sqrt(1 + 8|n|))/2 の上限が得られます。したがって、k は上限、または 1 または 2 にそれを加えたものに等しく、これら 3 つの数値のいずれかで、n と同じパリティを持ち、最小になります。ここで、3 つの連続する三角数の集合 {t, t + s, t + s + (s + 1)} には、任意の正の整数 t, s に対して偶数と奇数の両方が含まれているという事実を使用しています。(単純に、t と s の 4 つのパリティの可能性をすべてチェックしてください。)
n の最小長の合計を見つけるには、最初に d := (t_k - n)/2 を計算します。t_k >= |n| なので t_k と n は同じパリティを持ち、d はセット {0, 1, 2, ..., t_k} にあります。ここで繰り返し減算します: d = a_k (k) + r_k, r_k = a_{k-1} (k-1) + r_{k-1}, ..., r_2 = a_1 (1) + r_1、各 a_i を選択{0, 1} で最大。以下の補題により、r_1 = 0. したがって、d = sum_{i=1}^k a_i i. したがって、n = t_k - 2d = sum_{i=1}^ki - sum_{i=1}^k 2a_i i = sum_{i=1}^k (1 - 2a_i) i と 1 - 2a_i は {-1 にあります。 、1}。したがって、シーケンス b_i := 1 - 2a_i はパスであり、k の最小性により、b_i は最小パスです。
ターゲット数 n=12 を考えてみましょう。アルゴリズム 3 によると、k の可能性は 5、6、または 7 です。対応する t_k の値は 15、21、および 28 です。28 は n と同じパリティを持つこれらの最小値であるため、k=7 であることがわかります。 . したがって、d = (t_k - n)/2 = 8 となり、アルゴリズムに従って 1 + 7 と書きます。したがって、12 への最短経路は -1 + 2 + 3 + 4 + 5 + 6 - 7 です。
最短経路は一般に一意ではないため、最短経路と言います。たとえば、1 + 2 -3 + 4 - 5 + 6 + 7 も機能します。
補題: A_k = {0, 1, 2, ..., t_k} とする。次に、{0, 1} のシーケンス a_i の合計 sum_{i=1}^k a_i i として表現できる場合にのみ、数値は A_k にあります。
証明: k の帰納法による。まず、0 = sum_{i=1}^0 1、空の合計。ここで、すべての k - 1 >= 0 に対して結果が成り立つと仮定し、数値 d が A_k にあると仮定します。繰り返し減算: d = a_k (k) + r_k、r_k = a_{k-1} (k-1) + r_{k-1}、...、各 a_i = 0 または 1 を {0, 1 で最大に選択} そして、最初の r_j が A_j にあるとき、いくつかの j < k で停止します。次に帰納仮説により、{0, 1} の一部の b_i について r_j = sum_{i=0}^j b_i i となります。次に、必要に応じて d = r_j + sum_{i=j+1}^k a_k i となります。逆に、a sum s := sum_{i=1}^k a_i i for a_i in {0,1} は 0 <= s <= sum_{i}^ki = t_k を満たすため、s は A_k にあります。
算術演算が一定時間であると仮定すると、n から k を計算するのに O(1) 時間かかるため、n への最小パスの長さになります。次に、d の最小長の合計を見つけるのに O(k) 時間がかかり、その合計を使用して n の最小長の合計を生成するのに O(k) 時間がかかります。したがって、O(k) = O(sqrt(n)) 時間はすべてアップします。
ジャンプの回数に関係なく、ジャックが移動できる正の最大距離を簡単に計算できます。特定の値kを合計する正のジャンプの極性を反転すると、ジャックは、そうでない場合よりも 2k カウント低くなります。任意の最大距離t 、および同じパリティの非負のn ( tが偶数の場合でも、 tが奇数の場合は奇数) がその距離以下の場合、合計nとなるジャンプの組み合わせを見つけることができます。 . したがって、ツリー、ナップザック、またはその他のそのようなものについて心配する必要はありません-いくつかのジャンプで十分かどうか、そしてそれが正しい「パリティ」を生成するかどうかだけです。
連続するn 個の整数の和の式は ですn(n+1)/2。たとえば、1+2+3+4=10= 4*5/2=10. これは、目標数に到達するために必要な最小ステップ数です。しかし、オーバーシュートする可能性があります。ターゲットが であるとし11ます。4 回のジャンプで に到達しますが10(計算したところ)、5に到達します5*6/2=15。ここで、11 の場合、ステップ サイズが のときにジャンプ バックし、正しく2に到達することにだけ注意してください。11オーバーシュートについては後で詳しく説明します。そもそもジャンプ回数の計算方法に戻ります。私たちの式はn(n+1)/2 = x、xが目標数です。二次方程式は、これに対する解が
(-1+/-sqrt(-1+8x)))/2
また
(-1-/+(sqrt(9x))/2
負の「バージョン」は常に虚数を生成しますが、これはここでは関係ありません。
(sqrt(9x) + 1)/2
その数の天井を取ると、最初に必要なジャンプ数が得られます。
オーバーシュートは少し複雑です。リーチの11例では、オーバーシュートは4( ) であるため、ジャンプをジャンプ15-11=4にするだけでよく、そこに 4 つのオーバーシュートを「隠しておく」必要があります。ただし、物事は必ずしも単純ではありません。基本的な観察は、オーバーシュートは偶数でなければならないということです。それ以外の場合、オーバーシュート/2 ステップはありません。歩数の求め方はこちら+2-212-1-2+3+4-5+6+77512
5であることがわかります。153。したがって、12の場合、 の歩留まりとオーバーシュートを試み5ます。次に、6 ステップの降伏と のオーバーシュートを試みます。最後に、降伏ステップと のオーバーシュートを試みます。これが最小ステップ数です。ただし、これはおそらく数式で計算できます。15321972816
ジャックの進行状況をバイナリ ツリーとしてモデル化できます。左側のノードは後方へのジャンプを表し、右側のノードは前方へのジャンプを表します。
各ノードの値は、Jack の現在の位置です。
ノードの深さは、現在のジャンプの長さに対応します。
編集- ツリーの上位のノードと同じ値を持つノードをプルーニングすることはできません。これは、深さが異なるため、子の値が異なるためです。
検索スペースが急速に拡大しないようにするには、値が前のノードの繰り返しであるノードを積極的に削除する必要があります。
また、すべての値が右側のサブツリーの対応する値の否定であるため、ルートの下の左側のサブツリー全体を刈り込むことができます。例えば：
右のサブツリー: 0 + 1 + 2 + 3 - 4 = 2
左サブツリーのミラー イメージ: 0 - 1 - 2 - 3 + 4 = -2
幸いなことに、ツリーは多くの重複を生成するようです。たとえば、深さ = 7 では、32 ノード (正しいサブツリーのみを扱っているため 64/2) ではなく、6 つの異なるノードしかないように見えます。
4 = 0 + 1 + 2 + 3 + 4 - 5 + 6 - 7
14 = 0 + 1 + 2 + 3 + 4 + 5 + 6 - 7
16 = 0 + 1 + 2 + 3 + 4 + 5 - 6 + 7
18 = 0 + 1 + 2 + 3 + 4 - 5 + 6 + 7
20 = 0 + 1 + 2 + 3 - 4 + 5 + 6 + 7
28 = 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7
残りの 32 の可能な組み合わせはすべて、ツリーの上位にある正の数か、鏡像の左側のサブツリーからの負の数のいずれかのようです。
そのため、探している番号が見つかるまで幅優先検索を行います。
問題は次のとおりです。
$ k（k + 1）/ 2 = a + b $となるような最初の正kの自然の合計が最小のものを見つけます。ここで、$ n = a--b$です。k
連立方程式があります。
k(k+1)/2 = a + bn = a - ba, b, k正の整数です未知数は3つあり、方程式は2つだけです。組み合わせて、以下を満たすターゲット方程式を取得できます。
ある正の整数でなければならない場合、与えkられた整数に対してこの解が満たされるように、最小の正を見つける必要があります。いくつかのことに注意しましょう：na
nが偶数の場合k、k+1またはは4で割り切れる必要があります。つまり、k = 0 or 3 mod 4。nが奇数の場合、4で割り切れることkもできません。k+1つまり、k = 1 or 2 mod 4。これは、すべての数値が整数であるという部分を処理します。ポジティブであるという部分を処理するためkにa、私たちはそれを規定する必要があります
k >= floor(sqrt(2n))ふぅ。さて、例として：
n = 7と言います。そうすると、4で割り切れることも、割り切れないkこともわかりません。同様に、 。4で割り切れないことがわかっているので、すぐにスキップできます。私たちは私たちのシステムに入ります：k+1k >= 4k = 4kk = 5
n = 7
k = 5
a = 11
b = 4
これらの数値はすべて機能するため、有効な解決策があります。最初に最小のものを見つけなければならないような方法でソリューションを選択しましたk。気にかければ、ジャックが使用するジャンプのシーケンスを再構築することもできます。この場合、それは簡単です。ジャックは右に11ジャンプし、左に4ジャンプします。左に4ジャンプする唯一の方法は、左に1ジャンプ、左に3ジャンプすることです。したがって、ジャックは次のようにジャンプします。
----------J------N---
---------J-------N--- -1
-----------J-----N--- +2
--------J--------N--- -3
------------J----N--- +4
-----------------J--- +5
しかし、あなたの問題については、うまくいくものを見つけたらk、それで終わりです。k動作する値を見つける前に、の多くの値を試す必要はありません。
1 から j までの合計が、同じパリティの目標数よりも大きくなるように、必要な数 j を探しています。
Python 2.7 での簡単な作業コードを次に示します。
def numberOfJumps(n):
n = abs(n)
j = 0
while True:
s = j*(j+1)/2
if s >= n and not (s - n)%2:
break
j += 1
return j
for i in range(10):
print i, numberOfJumps(i)
-n と n は同じ量のジャンプを必要とするため、問題は正の数に単純化できます。シーケンス内の各数字に対して反対方向にジャンプするだけです。
次に、n に到達するには、正のジャンプのみの合計が n 以上に到達することを確認する必要があります。
また、合計のパリティがターゲット数と同じであることを確認する必要があります。これは、負の方向にジャンプすると合計に偶数の差が生じ、そのパリティが変化しないためです。
1 + 2 + 3 + 4 + 5 = 15 をジャンプするとします。シーケンス内の数字の任意の組み合わせを反転すると奇数になるため、差は偶数になります。