덧셈이나 뺄셈을 사용하여 각 단계에서 N의 최소 단계 수를 구하세요.

위 문제 설명에서 우리의 임무는 각 단계에서 덧셈과 뺄셈을 사용하여 주어진 숫자 N을 얻을 수 있는 최소 단계 수를 구하는 것입니다. 우리는 0부터 시작하는 숫자에 도달하기 위해 단계 번호를 더하고 빼서 수행할 수 있는 최소 단계 수와 주어진 정수 N에 대한 단계 순서를 인쇄해야 한다는 것을 이해할 수 있습니다.

이 문제 세트에서는 각 단계에서 현재 위치까지의 단계 수에 해당하는 숫자를 더하거나 뺄 수 있습니다. 예를 들어 1단계에서 1 또는 -1을 추가할 수 있습니다. 또한 2단계에서 2 또는 -2를 추가할 수 있습니다. 상황에 따라 각 단계에서 숫자를 더하거나 뺄 수 있습니다.

이 문제의 주요 과제는 0부터 N에 도달하기까지 최소 단계 수를 수행해야 한다는 것입니다. 예를 들어 이 문제를 더 잘 이해해 봅시다.

아래 예제에서는 위 작업을 수행하여 0부터 시작하여 2단계로 얻을 수 있는 모든 숫자를 보여줍니다.

예를 들어 N=1이라고 가정해 보겠습니다.

출력

으아악

지침

우리는 두 가지 방법으로 1을 달성할 수 있습니다 -

• 0에서 1로 이동하려면 1단계에 1을 더하면 1단계가 소요됩니다.

• 0에서 -1로 이동하려면 1단계에서 1을 빼고, -1에서 1로 이동하려면 2단계에서 2를 더하세요. 이는 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

  의 경우

  1+2+3+4=10, 즉 8보다 큽니다.

  10-8=2는 짝수이기 때문이죠. 그래서 우리는 2/2씩 뺄셈을 하려고 합니다. 즉,

  1단계. 따라서 단계 순서는 -1 2 3 4이고 최소

  입니다.

  N에 도달하는 단계 수는 4가 됩니다.

• (sum-N)이 홀수인 경우 먼저 이전 단계에서 합계가 N을 초과하는 숫자가 짝수인지 홀수인지 확인합니다.

  이전 단계가 홀수인 경우 다음 단계 번호를 추가하여 (sum-N)을 짝수로 만들고 위 단계를 수행하여 원하는 결과를 얻습니다.

  예: N=9

  1+2+3+4=10, 즉 9보다 큽니다.

  10-9=1이므로 홀수입니다. 다음 단계는 홀수인 5이므로 한 단계만 수행하고 합계에 5를 더해 15가 되어 (sum-N)=6이 됩니다. 3단계에서 뺄셈을 수행하면 원하는 출력인 1 2 -3 4 5 시퀀스가 ​​제공됩니다.

  이전 단계가 짝수라고 가정합니다. 이 경우 두 단계를 수행해야 하며, i번째 단계를 더하고 (i+1) 단계를 빼서 (sum- N)을 짝수로 구해야 합니다. 원하는 단계 순서.

  N=5의 경우

  1+2+3=6, 5개 이상.

  (sum-N) =1이므로 su가 숫자 N을 초과하는 경우 마지막 단계를 고려합니다. 짝수이므로 4단계와 5단계 두 단계를 수행하겠습니다. 그럼에도 불구하고 우리의 임무는 (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 중국어 웹사이트의 기타 관련 기사를 참조하세요!