N을 0이 아닌 K개의 정수로 표현하는 다양한 방법

"N을 0이 아닌 K 정수로 표현하는 다양한 방법"이라는 질문은 많은 실제 사용 사례에 적용됩니다.

암호화 - 암호화에서 특정 암호화 방법은 숫자 N을 0이 아닌 K개의 정수의 합으로 인코딩하는 개념을 사용하여 설계되었습니다.

정수 N을 0이 아닌 K개의 정수의 합으로 표현하는 것은 최적화 방법의 다양한 최적화 문제의 하위 문제에 나타날 수 있습니다.

Machine Learning− 기계 학습에서는 정수 N을 0이 아닌 K개의 정수의 합으로 표현하는 문제를 사용하여 데이터 포인트의 분포를 설명하는 특징 벡터를 생성할 수 있습니다.

Explanation

의 중국어 번역은

Explanation

입니다.

이제 문제를 풀어보겠습니다.

두 개의 양의 정수 N과 K가 있다고 가정하고, 합이 N과 같은 0이 아닌 정수 K개를 찾아야 합니다. 예를 들어, N=10이고 K=3이면 합이 10인 0이 아닌 정수 3개를 찾아야 합니다. 이 경우 가능한 해결책은 −

으아악

이 솔루션에는 K=3개의 0이 아닌 정수가 있으며 이를 더하면 N=10이 됩니다.

이 문제를 해결하는 방법은 여러 가지가 있습니다. 각각에 대해 토론해 보겠습니다.

재귀적 방법

재귀 방법의 단계별 알고리즘을 사용하여 0이 아닌 K개의 정수로 N을 표현하는 다양한 방법을 찾습니다.

• 주함수에 N과 K의 값을 입력해 보세요.

• N을 0이 아닌 K개의 정수로 표현할 수 있는 총 방법 수를 반환하는 함수 f(N, K)를 만듭니다.

• K = 1인 경우 N이 0을 초과하면 1을 반환하고, 그렇지 않으면 0을 반환합니다. (기본 상황).

• N == 0이거나 K > N이면 0을 반환합니다. (기본 상황).

• 결과를 저장할 변수 개수를 만듭니다.

• 변수 개수의 값을 0으로 설정합니다.

• 각 정수 I에 대해 1부터 최소(N-K+1, N-1)까지 I

• f(N-i, K-1)를 재귀적으로 계산합니다.

• 카운트에 결과를 추가하세요.

• 반품 횟수.

예

위 알고리즘의 구현

으아악

출력

으아악

복잡성

시간 복잡도: O(N ^ K).

공간 복잡성: O(K)

이항 계수 공식

성조기 조합법을 사용하면 양의 정수 N이 0이 아닌 K개의 정수의 합으로 표현될 수 있는 방식에 대한 공식을 얻을 수 있습니다.

주어진 정수의 N개의 파티션 단위를 나타내는 N개의 별(*) 행을 상상해 보세요. K-1 수직 막대(|)를 사용하여 별을 K 세그먼트로 배열하여 파티션의 0이 아닌 K 정수를 나타낼 수 있습니다.

10을 0이 아닌 정수 3개로 나누는 예를 들어보세요. 이 프로세스를 나타내는 데 다음 별표와 대시를 사용할 수 있습니다.

* * * * * * * * * *

이 그림의 첫 번째 부분은 숫자 2를 묘사하고, 두 번째 부분은 숫자 3, 세 번째 부분은 숫자 5를 묘사합니다.

N개의 별 행에 K-1개의 막대를 배열하는 방법의 수는 N을 0이 아닌 K개의 정수로 표현하는 방법의 수와 같습니다. 이 수량을 계산하려면 $mathrm{C(N:+:K:-:1,:K:-:1)}$ 공식을 사용합니다.

이항 계수 공식에 따르면 $mathrm{C(n,k):=:n!:/(k!*(n-k)!)}$.

하지만 우리의 경우에는 0이 포함될 가능성을 배제해야 합니다. 가수 중 하나로 0을 포함하는 나눗셈을 제외하려면 다음 방법을 사용할 수 있습니다. −

• N에서 1을 빼면 N-1이 됩니다.

• N-1을 음이 아닌 정수 K-1로 나눕니다.

• 2단계에서 얻은 음수가 아닌 모든 K-1 정수에 1을 더하여 0이 아닌 K개의 정수를 얻으며 그 합은 N입니다.

이 방법이 작동하는 이유는 각 가수의 가능한 가장 작은 값이 1이기 때문입니다(0이 아닌 정수가 되기를 원하기 때문). 따라서 K개의 가수에 할당할 수 있는 충분한 단위가 있는지 확인하기 위해 N에서 1을 뺍니다.

따라서 공식은 다음과 같습니다:ways = C(N-1, K-1)

0이 아닌 정수 4개로 6을 표현하는 방법의 수를 찾고 싶다고 가정해 보겠습니다. 이전에 파생된 공식을 사용할 수 있습니다. 즉, −

C(N-1, K-1) = C(6-1, 4-1) = C(5, 3) = 10

이것은 6을 0이 아닌 정수 4개로 나누는 10가지 방법이 있음을 알려줍니다.

그들은 −

• 1 + 1 + 1 + 3

• 1 + 1 + 2 + 2

• 1 + 1 + 3 + 1

• 1 + 2 + 1 + 2

• 1 + 2 + 2 + 1

• 1 + 3 + 1 + 1

• 2 + 1 + 1 + 2

• 2 + 1 + 2 + 1

• 2 + 2 + 1 + 1

• 3 + 1 + 1 + 1

방법

위 방법을 구현하기 위한 단계별 알고리즘에 대해 논의해 보겠습니다. -

• 주함수에 N과 K의 값을 입력해 보세요.

• 위 공식을 사용하여 방법의 수를 계산하세요.

• 가변방식의 값을 인쇄해 보세요.

이제 코드를 작성해 보겠습니다.

예

이항계수법을 이용한 코드 구현

으아악

출력

으아악

복잡성

시간 복잡도: O(K).

공간 복잡성: O(1)

결론

이 글에서는 N을 0이 아닌 K개의 정수의 합으로 표현하는 방법을 알아보는 방법을 설명하려고 했습니다. 이 기사가 이 개념을 더 잘 이해하는 데 도움이 되었기를 바랍니다.

위 내용은 N을 0이 아닌 K개의 정수로 표현하는 다양한 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!