J'ai une liste de numéros comme 1,2,3 et je veux trouver tous les modèles de combinaison qui résument à un nombre particulier comme 5. Par exemple:Comment générer des partitions entières?
Sum=5
Numbers:1,2,3
Patterns:
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3
Vous êtes autorisé à répéter les numéros pour autant qu'ils ne dépassent pas votre somme. Dans quel sens serait-il préférable de programmer cela?
Je le ferais récursivement en commençant par les nombres les plus élevés en premier. puis, à chaque fois, commencez avec le niveau le plus élevé et entrez autant de niveaux que de nombres. Dès que le niveau cumulé dépasse votre valeur, descendez au numéro suivant. S'il est encore trop grand (ou petit), revenez immédiatement à un niveau et diminuez le nombre suivant au niveau suivant, puis au niveau plus profond suivant en commençant par le haut.
Ceci est une légère modification du problème de changement . Vous devriez être en mesure de trouver beaucoup de documents sur ce problème, et une solution de programmation dynamique ne prendrait pas plus de 20 lignes de code.
Cela pourrait aussi aider: Dynamic Programming: Combination Sum Problem
On les appelle the partitions of a number et votre problème semble imposer la contrainte dont les numéros que vous êtes autorisé à utiliser dans la partition.
public static List<List<string>> Partition(int n, int max, string prefix)
{
if (n == 0)
{
_results.Add(prefix.Split(new char[] { ',' }).ToList());
}
for (int i = Math.Min(max, n); i >= 1; i--)
{
Partition(n - i, i, prefix + "," + i);
}
return _results;
}
Ce problème est connu sous le nom de "partition d'entier doublement restreinte". Si les nombres "autorisés" à sommer à 5 provenaient d'un ensemble V, alors il est connu comme "partition à multiplication restreinte entière". Il y a un article de Riha et James: "Algorithme 29: Algorithmes efficaces pour des partitions à double et à double restriction" Computing Vol 16, No 1-2, pp 163-168 (1976). Vous devriez lire ce document et implémenter leur algorithme. Comprendre comment le faire vous permettra d'implémenter des optimisations uniques à votre problème spécifique.
Vous pouvez utiliser le code ci-dessous .. il wiil vous donner une réponse exacte que vous voulez ..
void print(int n, int * a)
{
int i ;
for (i = 0; i <= n; i++)
{
printf("%d", a[i]);
}
printf("\n");
}
void integerPartition(int n, int * a, int level)
{
int first;
int i;
if (n < 1)
return ;
a[level] = n;
print(level, a);
first = (level == 0) ? 1 : a[level-1];
for(i = first; i <= n/2; i++)
{
a[level] = i;
integerPartition(n - i, a, level + 1);
}
}
int main()
{
int n = 10;
int * a = (int *) malloc(sizeof(int) * n);
integerPartition (n, a, 0);
return(0);
}
Quelle langue utilisez-vous? Qu'avez-vous essayé? Où êtes-vous coincé? Qu'avez-vous jusqu'ici? –
La langue n'a pas d'importance, c, C++, C#. J'ai un moyen d'obtenir certains des modèles, mais il en reste encore quelques-uns. Je pense que nous avons besoin d'un algorithme récursif pour faire le travail – user180812
Qu'avez-vous essayé. C'est vraiment nul, mais quand on apprend à programmer, demander à quelqu'un de vous dire comment le faire ne vous aidera pas. Vous devez essayer quelque chose et voir si cela fonctionne ou non. Par ailleurs, nous savons à quoi ressemblent les devoirs, la plupart d'entre nous sont allés à l'université et ont pris la programmation 1, 2, 3, etc. Postez quelques informations supplémentaires sur la façon dont vous voulez résoudre le code et vous obtiendrez beaucoup plus d'aide. – Spence