Je fais une application mathématique pour l'Android. Dans l'un de ces champs, l'utilisateur peut entrer un int (pas de chiffres et plus 0). L'idée est d'obtenir toutes les sommes possibles qui rendent cette int, sans doubler (4 + 1 == 1 + 4 dans ce cas). La seule chose connue est celle-ci.
Par exemple:
Dites que l'utilisateur entre 4, j'aimerais que l'application renvoie:
Évidemment 4 == 4 de sorte que cela devrait être ajouté aussi. Toute suggestion quant à la façon dont je devrais faire cela?
6 Réponses :
Pour un numéro N, vous savez que le nombre de termes max est N. Donc, vous commencerez par énumérer toutes ces possibilités.
Pour chaque nombre possible de termes, il existe un certain nombre de possibilités. La formule me échappe maintenant, mais essentiellement, l'idée est de commencer par (N + 1-I + 1 + ... + 1) où je suis le nombre de termes et pour déplacer 1s de gauche à droite, le second cas être (ni + 2 + ... + 1) Jusqu'à ce que vous ne puissiez pas faire un autre mouvement sans obtenir une combinaison non formée.
(aussi, pourquoi avez-vous étiqueté cet Android à nouveau?)
Parce que c'est pour une application, n'affecte pas vraiment l'algorithme Tho ... :)
Voici un algorithme simple qui prétend faire cela
de: http://tintrocs.cs.princeton.edu/java/23recursion/partition.java.html p>
public class Partition {
public static void partition(int n) {
partition(n, n, "");
}
public static void partition(int n, int max, String prefix) {
if (n == 0) {
StdOut.println(prefix);
return;
}
for (int i = Math.min(max, n); i >= 1; i--) {
partition(n-i, i, prefix + " " + i);
}
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
partition(N);
}
}
Ceci est lié au Sous-Sum Problème Algorithme.
n = {n * 1, (n-1) +1, (n-2) +2, (N-3) +3 .., N-1 = {(N-1), ((N-1) -1) +2, ((N-1) -1) +3 ..}
etc.
C'est donc une fonction récursive impliquant la substitution; Que cela soit logique ou non lorsqu'il s'agisse de nombreux chiffres, cependant, vous devrez décider vous-même.
Ceci est le concept mathématique connu sous le nom de Partitions . En général, c'est ... difficile, mais il y a des techniques pour petits nombres. Une charge de choses utiles liées à partir de la page wiki.
Il existe une solution récursive courte et élégante pour les générer, mais les éléments suivants peuvent être plus faciles à utiliser et à mettre en œuvre dans le code existant: Vous pouvez l'utiliser comme ceci: qui imprimerait:
Très beau code, mais celui de Ashkan Aryan est plus propre et que ceci est pour un client qui aime le code propre, je vais l'utiliser. Je t'ai suscité que c'est parce que c'est un très beau morceau de code!
Le code manque des combinaisons où un nombre en plus de 1 répétitions (5 + 5, 6 + 2 + 2, 3 + 3 + 3 + 1, 4 + 4 + 2, etc.).
Toutes ces solutions semblent un peu complexe. Ceci peut être réalisé en "incrémentation" une liste initialisée pour contenir 1 = n.
Si les gens ne vous dérangent pas convertir de C ++, l'algorithme suivant produit la sortie nécessaire. P>
[1, 1, 1, 1, 1] [1, 1, 1, 2] [1, 1, 2, 1] [1, 1, 3] [1, 2, 1, 1] [1, 2, 2] [1, 3, 1] [1, 4] [2, 1, 1, 1] [2, 1, 2] [2, 2, 1] [2, 3] [3, 1, 1] [3, 2] [4, 1] [5]
Ce serait mieux si vous pouvez ajouter du drapeau d'algorithme
Qu'en est-il de 5? :::: 5 4 + 1 2.5 + 2.5? 1 + 1 + 1 + 1 + 1
Vous devez savoir que le nombre de partitions d'un nombre augmente rapidement. De plus de 22 Il y a déjà plus de 1000 partitions et au moment où vous atteignez 100, vous consultez environ 190 000 000 partitions.
@nik Nope Seuls les nombres entiers (comme il ne dit aucun chiffre)
Techniquement, l'INT est la "somme". Les chiffres qui ajoutent une somme sont appelés "adverses"