algorithm
Algorithme de partition entier

Informations de base sur l'algorithme de partition entière

La partition d'un entier est une manière de l'écrire comme une somme d'entiers positifs. Par exemple, les partitions du numéro 5 sont:

• 5
• 4 + 1
• 3 + 2
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

Notez que la modification de l'ordre des sommets ne crée pas une partition différente.

La fonction de partition est intrinsèquement récursive puisque les résultats des nombres plus petits apparaissent comme des composants dans le résultat d'un nombre plus grand. Soit p (n, m) le nombre de partitions de n en utilisant uniquement des entiers positifs inférieurs ou égaux à m . On peut voir que p (n) = p (n, n) , et aussi p (n, m) = p (n, n) = p (n) pour m > n .

Exemple d'algorithme de partition d'entier:

Espace auxiliaire: O(n^2)
Complexité temporelle: O(n(logn))

Implémentation de l'algorithme de partition d'interaction en 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);
    }
}