数を1つに減らすための最小ステップ数
1. 序章
このチュートリアルでは、最小数の操作を使用して数を1に減らす方法について説明します。 使用する操作は、1を加算し、1を減算し、数が偶数の場合は2で除算することです。
問題を解決するための3つのアプローチについて説明し、どのアプローチが最適な答えを提供するかを確認します。
2. 問題の定義
この問題では、数が与えられ、最小の操作数を使用してこの数を1に等しくなるように減らす必要があります。
毎回、次のいずれかの操作を使用できます。
- 現在の番号に1を追加します。したがって、新しい番号はになります。
- 現在の番号から1を引きます。したがって、移動する新しい番号はです。
- 偶数の場合、2で割ることができます。したがって、取得する新しい数値はです。
たとえば、が28に等しい場合、最適なソリューションは6つのステップを使用することです。
また、が13に等しい場合、最適なソリューションは5つのステップを使用することです。
3. 非最適な欲張りアプローチ
この貪欲なアプローチは、現在のステップの数を可能な限り減らす操作を使用しようとします。 ご存知のように、この数は奇数でも偶数でもかまいません。 数値が奇数の場合、2による除算は使用できないため、1を減算する演算を使用します。
一方、数が偶数の場合は、1を引くか、2で割ることができます。 貪欲なアプローチに従っているため、数値を2で割ることを選択します。
たとえば、が10に等しい場合、欲張りアプローチは次の4つのステップの後に1に到達します。
この貪欲なアプローチが常に最適なソリューションを提供するとは限らないことを証明できます。 反例は、が15に等しい場合です。 貪欲なアプローチでは、次の6つのステップが提供されます。
ただし、次の5つの手順のみを使用して、より適切な解決策を見つけることができます。
したがって、この貪欲なアプローチは高速であると結論付けることができますが、常に最適なソリューションが得られるとは限りません。
4. BFSアプローチ
BFS アルゴリズムを使用して、グラフ理論内で問題の解決策を見つけることができます。
4.1. 一般的なアイデア
各数値をグラフ内のノードと考えてみましょう。 また、グラフのエッジを考慮して、ノードをノードとに接続することもできます。 さらに、偶数の場合は、それも接続されます。
4.2. 実装
このアプローチの実装を見てみましょう。
最初に、配列をで初期化します。これは、から始まる各数値に到達するためのステップ数を保持します。
配列サイズは開始数の2倍である必要があることに注意してください。 その理由は、開始番号に1を追加し続ける場合があるためですが、そこから2で割ってに戻ることができるため、到達しても意味がありません。 また、BFSアルゴリズムのキューを定義します。
次に、開始番号であるので、の答えをゼロに設定し、それをキューにプッシュします。 その後、キューが空でない限り、キューから番号を抽出し続けます。 番号ごとに、この番号が1であるかどうかを確認します。 この場合、アルゴリズムがターゲット番号1に到達したため、ループを停止します。
それ以外の場合は、以前に見つかった回答を確認して、、に到達します。 からこれらの番号に到達する方が以前に見つけた方法よりも優れている場合は、を更新して番号をキューにプッシュします。
配列のサイズを尊重するために、新しい数が1を超えたり、1を下回ったりしないようにすることに注意してください。 また、偶数の場合は2で割る演算のみを使用します。
最後に、を返します。これには、数値1に到達するための最小ステップ数が含まれています。
4.3. 複雑
BFSアルゴリズムの複雑さは、です。ここで、は頂点の数、はエッジの数です。 この場合、頂点の数はです。ここで、は開始する数です。 一方、最悪の場合、各番号は3つの番号に接続できます。 したがって、エッジの数はです。
結果として、全体の複雑さはになります。ここで、は開始番号です。
5. 最適な欲張りアプローチ
セクション3で貪欲なアプローチを更新して、新しい最適なアプローチを取得できます。
5.1. 理論的アイデア
まず、問題を偶数か奇数かに基づいて2つのケースに分けましょう。 偶数の場合、最適なステップは数値を2で割ることであることが証明できます。
その理由は、2つの加算演算を使用してから、2で除算することで、3ステップを使用するのと同じように到達できるためです。 ただし、この数に達するには、2で除算してから1を加算する2つのステップを使用します。 したがって、合計2つの操作を使用します。
また、2つの減算演算を使用してから、2で除算することもできます。 この場合、3つのステップを使用することに等しいに到達します。 ただし、2で除算してから1を引くと、同じ数を得ることができます。 したがって、合計2つの操作のみを使用します。
さらに、これら2つの演算は互いに打ち消し合うため、1を加算および減算するオプションを削除できます。 したがって、が偶数の場合は、常に2で割るのが最適です。
一方、奇数の場合は、複数のケースを考慮する必要があります。 奇数の場合の最下位2ビットを考えてみましょう。 2つのケースがあります（は残りの数を表します）。 偶数に2で割ってに到達するという最適な選択があるという事実を利用できます。
の場合 ：
- 追加しようとすると、に到達します。 次に、に到達するために部門と一緒に行く必要があります。 その後、2つのオプションがあります。
- リーチするために追加し、その後、リーチするために分割します。 したがって、4つの操作で到達します。
- または、減算してに到達し、次に除算してに到達します。 したがって、4つの操作で到達します。
- 一方、減算すると、が得られ、その後、2つの除算を行ってに到達します。 その結果、次のようになります。
- 3つの操作で到達できます。
- また、4回の操作でリーチするためにもう1つ追加を実行できます。
結果として、2進表現で終わる数値の場合、減算は常に加算に対してより良いまたは同等の答えを与えることがわかります。
他の場合は：
- 追加しようとすると、が取得されます。 したがって、を取得するには2回除算する必要があります。 その結果、次のような場合があります。
- 到達するには3つの操作が必要です。
- 到達するには、追加の減算が必要です。 したがって、4回の操作で到達できます。
- 減算することにした場合は、を取得します。その後、除算してに到達する必要があります。 ここから、2つのオプションがあります。
- 追加すると、に到達します。 次に、分割して取得します。 したがって、を取得するには4つの操作が必要です。
- 減算するとに到達し、その後分割してに到達します。 したがって、を取得するために4つの操作を使用しました。
ご覧のとおり、2進数表現で終わる数値の場合は、1を加算する演算を使用する方が常に優れています。
数を4で割った後、モジュラーをチェックすることにより、この奇数の分析を結論付けることができます。 1の場合は、減算することにします。 それ以外の場合は、1を追加します。これに対する唯一の例外は、が3に等しい場合です。この場合、2つの減算を行う必要があります。
5.2. 実装
このアプローチの実装を見てみましょう。
実装は、セクション5.1で説明した理論的な考え方に似ています。 偶数の場合は、除算演算を使用することをお勧めします。 それ以外の場合、が3に等しいか、4で割った後のモジュラーが1の場合、減算します。 それ以外の場合は、追加操作を使用します。
5.3. 複雑
最適な欲張りアプローチの複雑さはです。ここで、は初期数です。その理由は、減算または加算を使用した場合でも、両方の演算が偶数になるためです。 したがって、2つの操作による除算は、少なくとも2つのステップごとに1回発生します。
6. 結論
この記事では、2で割るか、1を足したり引いたりする演算を使用して、数値を1に減らす方法について説明しました。
問題を解決するための3つのアプローチについて説明し、次にどのアプローチが最適な答えを与えるかを説明しました。
