Après environ 7 heures consécutives, j'ai vraiment besoin d'aide, j'ai besoin de revenir de la récursivité sur le nombre d'options qui peut être en définissant des nombres de 1 au nombre choisi (nombre maximum), c'est interdit d'utiliser des boucles / tableaux, uniquement récursivité, les nombres sont tous positifs (plus de 0) et ne va que plus positivement, exemple: bon: {1,2}, mauvais: {2,1}.
exemple:
n=2
max=3
{1,1}
{1,2}
{1,3}
{2,2}
{2,3}
{3,3}
n: Les nombres qui devraient être dans la ligne , max: Le nombre maximum qui peut être dans la ligne.
{1,1,1}
{1,1,2}
{1,2,2}
{2,2,2}
de cet exemple qui devrait renvoyer 4 car il y a 4 options de 3 nombres dont la valeur est maximum 2.
un autre:
n = 3 , max = 2
de cet exemple, il devrait renvoyer 6 car il y a 6 options.
3 Réponses :
J'ai écrit du code moins efficace en raison du temps, essayez de regarder ceci, cela vous donnera dir, j'espère,
package com.exercise;
import java.util.Arrays;
public class Permutation {
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
}
}
private static void permutationOnInt(String prefix, String str, int max) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i <= n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
}
}
public static int[] return_Array(int length) {
int[] a = new int[length];
for (int i = 0; i < length; i++) {
a[i] = i + 1;
}
return a;
}
public static void main(String[] args) {
String fn = Arrays.toString(return_Array(3));
String apple = String.join(",", fn.replace("[", "").replace("]", "").replace(",", "").replaceAll("\\s+", ""));
permutationOnInt("", apple, 3);
}
}
Après avoir obtenu le résultat, vous pouvez le reconvertir en le tableau. Important : ce code n'est pas du tout optimisé. Je publierai optimisé plus tard
La récursivité peut être difficile à comprendre au début, mais elle est très claire à lire une fois que vous la connaissez. L'inconvénient est que la récursivité nécessite beaucoup plus d'espace que la boucle for de base ( Complexité spatiale de la fonction récursive ). Pour certains problèmes, il peut être plus facile d'écrire d'abord la version récursive et ensuite de l'écrire en boucle for. De plus, si l'espace n'est pas un problème, cela aide à rendre votre code propre (pas de boucles for!) J'ai fait une récursion basique qui donne la bonne réponse pour au moins les deux exemples que vous avez écrits. Il est possible que j'ai raté un cas limite: peut-être une bonne pratique pour écrire chaque appel de fonction et certains cas de test (énervés). En bref:
Dans le deuxième exemple: n = 2
max = 3 Notez le modèle des nombres qui apparaît en raison de la règle selon laquelle les nombres de gauche à droite doivent être égaux ou plus grands:
Deuxième colonne: 1> 2> 3> 2> 3> 3
Première colonne: 1> 1> 1> 2> 2> 3 Le paramètre 'borne inférieure' dans la récursivité est fondamentalement le plus petit nombre possible que la nouvelle 'séquence' peut prendre (où chaque séquence est Remarque: Il est peut-être possible de faire la récursivité avec moins de paramètres. Assurez-vous de lire beaucoup de choses sur la récursivité (par exemple wikipedia ou votre livre d'étude?). Les récursions facilitent la recherche de solutions et la compréhension de problèmes complexes et abstraits. {1,1}
{1,2}
{1,3}
{2,2}
{2,3}
{3,3}
public int recursiveWrapper(int n, int max) {
return recursive(n, max, 1, 1);
}
public int recursive(int n, int max, int lower, int current) {
// // for your convenience
// System.out.println("n:" + n + " max:" + max + " lowerbound:" + lower + " current:" + current);
// Base case
if (n <= 1 && lower == max) {
return 1;
}
// Recursive step
// Sequence complete, move to next column
if (current == max) {
// Make sure the lower bound does not go beyond the max. number
int updatedLower = (lower + 1 > max) ? lower : lower + 1;
return 1 + recursive(n - 1, max, updatedLower, updatedLower);
}
return 1 + recursive(n, max, lower, current + 1);
}
borne inférieure -> nombre maximum ). Le cas de base est alors lorsque la borne inférieure est égale à la borne supérieure et que chaque colonne a fait tout ce qu'elle «séquence». Peut-être pas une explication très claire - peut-être que cela aide quand vous voyez ce qui est imprimé par la ligne commentée dans le code que j'ai copié-collé.
Sans connaissances préalables, ce serait probablement une question difficile, même pour un mathématicien expérimenté. C'est le décompte des multisets , l'un des éléments fondamentaux de la combinatoire. Je vais vous expliquer ma compréhension de l'idée de la relation de récurrence dans Wikipedia.
En général, k est utilisé pour la cardinalité multiset (ce que votre question appelle n ) , tandis que n est utilisé comme cardinalité de l'ensemble ( pas multiset ) à choisir (le max dans votre question). p >
Pour f (n, k) , les cas de base sont:
function f(n, k){
if (n == 0)
return 0;
if (k == 0)
return 1;
return f(n - 1, k) + f(n, k - 1);
}
console.log(f(2, 3));
console.log(f(3, 2));Et,
f(n, k - 1)
Qu'avez-vous écrit jusqu'à présent après environ 7 heures de suite ?
@NicholasK Je l'ai écrit avec des tableaux pendant quelques heures, puis j'ai remarqué que c'était interdit, et maintenant je suis complètement confus et je ne sais même pas comment le démarrer.
me semble une opération de permutation.
Eh bien, cela aiderait à ajouter votre tentative et aider serait plus facile. Pour le moment, c'est trop large.
Copie possible de la Méthode de récurrence Java de base
quel est votre cas d'entrée de test? Fournissez-moi.
@parladneupane, que voulez-vous dire? Il y a deux exemples / cas avec des résultats attendus dans la question.
@ K.Nicholas Je ne vois pas comment vous avez trouvé cela en double .. parce qu'il pose des questions sur la récursivité? toutes les questions de récursivité ne sont pas les mêmes, sa question est une récursion java de base réelle ...
Il semble que vous ayez besoin d'aide pour comprendre la récursivité Java de base