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

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

WBOY

リリース： 2023-09-16 13:13:22

転載

709 人が閲覧しました

上記の問題ステートメントから、私たちのタスクは、各ステップで加算または減算を使用して指定された数値 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 以上になるまでステップ数の減算を続けます。

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

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

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

-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 に到達する最小ステップ数を見つける方法を説明します。この記事がこの概念をより深く学ぶのに役立つことを願っています。