algorithm
Целочисленный алгоритм разделения
Поиск…
Основная информация алгоритма разделения целых чисел
Разделение целого числа является способом записи его в виде суммы положительных целых чисел. Например, разделы числа 5:
- 5
- 4 + 1
- 3 + 2
- 2 + 2 + 1
- 2 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1
Обратите внимание, что изменение порядка слагаемых не создаст другой раздел.
Функция разбиения носит по своей природе рекурсивный характер, так как результаты меньших чисел появляются как компоненты в результате большего числа. Пусть p (n, m) - число разбиений n, используя только положительные целые числа, которые меньше или равны m . Можно видеть, что p (n) = p (n, n) , а также p (n, m) = p (n, n) = p (n) при m > n .
Пример целочисленного алгоритма разбиения:
Вспомогательное пространство: O(n^2)
Сложность времени: O(n(logn))
Реализация алгоритма Interger Partition в C #
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