algorithm
Heltal för partitionsalgoritm
Sök…
Grundläggande information om heltal för partitionsalgoritm
Partitionen av ett heltal är ett sätt att skriva det som en summa av positiva heltal. Till exempel är partitionerna i numret 5:
- 5
- 4 + 1
- 3 + 2
- 2 + 2 + 1
- 2 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1
Observera att ändring av ordningsföljden för summands inte kommer att skapa en annan partition.
Partitionsfunktionen har i sig natur rekursiv karaktär eftersom resultaten från mindre antal visas som komponenter i resultatet av ett större antal. Låt p (n, m) vara antalet partitioner av n med endast positiva heltal som är mindre än eller lika med m . Det kan ses att p (n) = p (n, n) och även p (n, m) = p (n, n) = p (n) för m > n .
Exempel på heltalspartitionsalgoritm:
Hjälprum: O(n^2)
Tidskomplexitet: O(n(logn))
Implementering av Interger-partitionsalgoritm i 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
Licensierat under CC BY-SA 3.0
Inte anslutet till Stack Overflow