algorithm
정수 파티션 알고리즘
수색…
정수 파티션 알고리즘의 기본 정보
정수 의 파티션은 그것을 양의 정수의 합으로 쓰는 방법입니다. 예를 들어 숫자 5의 파티션은 다음과 같습니다.
- 5
- 4 + 1
- 3 + 2
- 2 + 2 + 1
- 2 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1
summand의 순서를 변경해도 다른 파티션이 생성되지는 않습니다.
파티셔닝 함수는 더 작은 수의 결과가 더 큰 수의 결과에서 구성 요소로 나타나기 때문에 본질적으로 재귀 적입니다. p (n, m) 을 m 보다 작거나 같은 양의 정수만 사용하는 n 의 분할 수로 봅니다. m > n에 대한 p (n) = p (n, n) 및 p (n, m) = p (n, n) = p
정수 파티션 알고리즘의 예 :
보조 공간 : O(n^2)
시간 복잡도 : O(n(logn))
C #에서 Interger 분할 알고리즘 구현
public class IntegerPartition
{
public static int[,] Result = new int[100,100];
private static int Partition(int targetNumber, int largestNumber)
{
for (int i = 1; i <= targetNumber; i++)
{
for (int j = 1; j <= largestNumber; j++)
{
if (i - j < 0)
{
Result[i, j] = Result[i, j - 1];
continue;
}
Result[i, j] = Result[i, j - 1] + Result[i - j, j];
}
}
return Result[targetNumber, largestNumber];
}
public static int Main(int number, int target)
{
int i;
for (i = 0; i <= number; i++)
{
Result[i, 0] = 0;
}
for (i = 1; i <= target; i++)
{
Result[0, i] = 1;
}
return Partition(number, target);
}
}
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow