1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| // Ceci importe la classe Scanner du package java.util
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Iterator;
// Voici ma classe Partition, contenant ma fonction principale.
public class test {
// Fonction 'décomposition' utilisée avec la récursivité pour créer les différentes branches de mon arbre.
public static void decomposition(int n, Branche branche, int k){
// Déclaration d'une variable permettant de décrémenter n à chaque récursivité afin de composer une partition.
int difference;
difference = n - branche.somme;
// Si une erreur se glisse dans la création de l'arbre et que la différence est supérieur à la nouvelle branche, je repars de sa valeur maximale.
if(difference > branche.max){
difference = branche.max;
}
// Boucle 'pour' partant de notre n "actuel" et ce décrémentant petit à petit pour donner, au premier passage par exemple, la deuxième ligne de mon PDF (celle en dessous du 'n' solitaire).
for(int nombre = difference; nombre > 0; nombre--){
// Création de l'objet 'enfant' héritant de la classe branche.
Branche enfant = new Branche();
branche.liste.add(nombre);
enfant.liste = branche.liste;
enfant.max = nombre;
// La profondeur est notre 'k', on incrémente celle de l'enfant avec celle du parent + 1 pour toujours savoir où on en est et dès qu'on atteint k : terminer.
enfant.profondeur = branche.profondeur + 1;
// Calcule la somme du noeud avec la somme du noeud superieur, afin de vérifier si on est encore '<= n'.
enfant.somme = branche.somme + nombre;
// La fonction 'Push' va ajouter une nouvelle case, un nouvel élément, à la fin du tableau enfant avec la valeur entre parenthèses.
branche.enfantListe.addAll(enfant.enfantListe);
// Si notre somme est toujours inférieur à n, on repars dans une décomposition en créant une nouvelle branche.
if(enfant.somme < n){
decomposition(n, enfant, k);
}
// Si notre somme est atteinte et que notre nombre de partitions voulues ('k') est respectée, alors on peut imprimer la solution.
else{
if(enfant.profondeur == k){
System.out.println(enfant.liste);
}
}
}
}
// Fonction principale.
public static void main(String[] args){
// L'objet 'sc' hériant de la classe 'Scanner' est là pour me permettre de récupérer un nombre entré au clavier par l'utilisateur.
Scanner sc = new Scanner(System.in);
// Création de l'objet 'arbre' héritant de la classe branche.
Branche arbre = new Branche();
// Ici je demande à l'utilisateur de sélectionner un nombre à décomposer.
System.out.println("Veuillez saisir un nombre n à décomposer en k parties :");
// Je récupère la valeur saisie par l'utilisateur pour la variable 'n'.
int n = sc.nextInt();
// Je renseigne l'utilisateur sur sa saisie pour qu'il se rende compte s'il y'a erreur ou non.
System.out.println("Vous avez saisi : " + n);
// Départ de l'arbre (ensuite le '.max' sera utilisé pour chaque départ de branche).
arbre.max = n;
// Ici je demande à l'utilisateur de sélectionner le nombre de partitions qu'il souhaite pour décomposer son nombre.
System.out.println("Veuillez saisir un nombre k représentant le nombre d'éléments désirés pour décomposé le nombre n :");
// Je récupère la valeur saisie par l'utilisateur pour la variable 'k'.
int k = sc.nextInt();
// Je renseigne l'utilisateur sur sa saisie pour qu'il se rende compte s'il y'a erreur ou non.
System.out.println("Vous avez saisi : " + k);
// Enfin, j'appelle la fonction 'décomposition' pour effectuer les partitions du nombre 'n' désirées et les afficher à l'écran.
decomposition(arbre.max, arbre, k);
}
} |
Partager