加算または減算を使用して、各ステップでの N の最小ステップ数を取得します。

上記の問題ステートメントから、私たちのタスクは、各ステップで加算または減算を使用して指定された数値 N を取得できる最小ステップ数を取得することです。実行可能な最小ステップ数と、指定された整数 N のステップの順序を、ステップ番号を加算および減算して 0 から始まる数値に到達することによって出力する必要があることがわかります。

この問題集では、ステップごとに現在位置にステップ数に等しい数値を加算または減算できます。たとえば、ステップ 1 で 1 または -1 を追加できます。さらに、ステップ 2 で 2 または -2 を追加することもできます。状況に応じて、各ステップで数値を加算または減算できます。

この問題の主な課題は、0 から開始して N に到達するまでの最小数のステップを実行する必要があることです。例を挙げてこの問題をよりよく理解してみましょう。

以下の例では、上記の操作を実行することにより、0 から始まる 2 つのステップで取得できるすべての数値が表示されます。

たとえば、N=1 があると仮定します。

＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

イラスト これは 2 つの方法で実現できます 1 -

ステップ 1 に 1 を追加するだけで、0 から 1 に移動できます。これには 1 ステップかかります。

• ステップ 1 で 1 を減算して 0 から -1 に移動し、次にステップ 2 で 2 を加算して -1 から 1 に移動します。これには 2 ステップかかります。

• 質問では、任意の数値 N に到達するには最小ステップ数が必要であると述べているため、この入力に対する望ましい出力は 1 になります。

の場合、

N=3

＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

イラスト ステップ 1 で 1 を追加して 0 から 1 に移動し、ステップ 2 で 2 を追加して 1 から 3 に移動します。

＃＃＃方法＃＃＃

問題を解決する最良の方法は、まず N が正の数か負の数かを判断することです。問題を解決するには、適切なステップ数をそれぞれ加算または減算する必要があります。

N が正の数の場合、合計が N 以上になるまでステップの追加を続けます。

同様に、N が負の数の場合、合計が N 以上になるまでステップ数の減算を続けます。

上記の場合、合計が N に等しい場合は、ステップ数とステップの順序を返します。主な問題は、N を超えた場合の状況の処理です。
合計が N を超えたら、(合計 - N) が偶数か奇数かを確認します。
(sum-N) が偶数の場合、N に到達するまでに (sum-N)/2 のステップで減算を実行する必要があります。

• 適切な例を挙げて、このケースをよりよく理解しましょう。

N=8

の場合 ＃＃＃＃１ ２ ３ ４＝１０、これは８より大きいです。

10-8=2 は偶数だからです。したがって、2/2 ずつ減算します。これは

です。 ＃＃＃ステップ1。したがって、ステップの順序は
• -1 2 3 4

  となり、最小値は

  になります。

  N に到達するまでのステップ数は

  4

  になります。

  (sum-N) が奇数の場合、まず、前のステップで合計が N を超える数が偶数か奇数かを判断します。

  前のステップが奇数の場合は、(合計-N) が偶数になる次のステップ番号を追加してステップを実行し、上記のステップを実行して目的の結果を取得します。 例: N=9

  ＃＃＃＃１ ２ ３ ４＝１０、これは９より大きいです。

  10-9=1 なので、これは奇数です。次のステップは 5 で、これは奇数であるため、1 つのステップを実行し、合計に 5 を加算して 15 を取得し、(sum-N)=6 となります。ステップ 3 で減算を実行すると、シーケンス 1 2 -3 4 5

  が得られ、これが目的の出力になります。
• 前のステップが偶数であると仮定します。この場合、i 番目のステップを加算し、

  (i 1)

  ステップを減算して、(sum- N) を偶数として使用して、必要なステップのシーケンスを取得します。
  N=5の場合

  ＃＃＃１ ２ ３＝６、５以上です。

  (sum-N) = 1 なので、su が数値 N を超えたときの最後のステップを検討します。偶数なので、ステップ4とステップ5の2つのステップを実行します。私たちのタスクは、それでも (sum-N) を作ることです。ステップ 4 で足し、ステップ 5 で減算することで、合計から 1 を引いても (sum-N) を作ることができます。 (sum-N) は 0 に等しいため、N が得られます。したがって、シーケンスは

  1 2 3 4 -5 になります。
  ＃＃＃例＃＃＃

  以下はこのメソッドの C コードです - リーリー ＃＃＃出力＃＃＃ リーリー

  時間計算量: O(sqrt(N))
  空間計算量: O(sqrt(N))

  ＃＃＃結論は＃＃＃ この記事では、各ステップで加算または減算して数列を出力することにより、N に到達する最小ステップ数を見つける方法を説明します。この記事がこの概念をより深く学ぶのに役立つことを願っています。

以上が加算または減算を使用して、各ステップでの N の最小ステップ数を取得します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。