L'héritage et le polymorphisme sont deux concepts fondamentaux de la...
La suite de Fibonacci est une séquence mathématique où chaque nombre est la somme des deux nombres précédents. En programmation, il existe plusieurs façons de calculer la suite de Fibonacci. Dans cet article, nous allons nous concentrer sur une approche récursive pour résoudre ce problème en Java.
La récursivité est un concept en programmation où une fonction se rappelle elle-même pour résoudre un problème plus petit. Pour résoudre la suite de Fibonacci de manière récursive, nous devons diviser le problème en sous-problèmes plus petits et résoudre ces sous-problèmes jusqu’à atteindre le cas de base.
Voici l’algorithme récursif pour calculer le n-ème nombre de Fibonacci :
Voici une implémentation de cet algorithme en Java :
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
int n = 10; // Exemple : Trouver le 10e nombre de Fibonacci
System.out.println("Le " + n + "e nombre de Fibonacci est : " + fibonacci(n));
}
}Dans cet exemple, la méthode fibonacci() prend un entier n en entrée et retourne le n-ème nombre de Fibonacci. Si n est inférieur ou égal à 1, la méthode retourne simplement n. Sinon, elle appelle récursivement la méthode fibonacci() pour n-1 et n-2, puis retourne la somme des résultats.
Supposons que nous voulions trouver le 10e nombre de Fibonacci. En exécutant le programme Java, nous obtiendrons :
Le 10e nombre de Fibonacci est : 55La résolution récursive de la suite de Fibonacci en Java est une approche simple et élégante pour ce problème classique en informatique. Cependant, cette méthode peut devenir inefficace pour des valeurs de n élevées en raison de la répétition des calculs. Dans de tels cas, d’autres techniques comme la programmation dynamique peuvent être utilisées pour améliorer les performances.
Voici une série d’exercices corrigés sur le thème de la récursivité en Java :
Écrivez une méthode récursive pour calculer la factorielle d’un nombre.
public class Factorielle {
public static int calculFactorielle(int n) {
if (n == 0) {
return 1;
} else {
return n * calculFactorielle(n - 1);
}
}
public static void main(String[] args) {
int n = 5;
System.out.println("Factorielle de " + n + " : " + calculFactorielle(n));
}
}Écrivez une méthode récursive pour calculer la somme des chiffres d’un nombre.
public class SommeDesChiffres {
public static int sommeChiffres(int n) {
if (n == 0) {
return 0;
} else {
return n % 10 + sommeChiffres(n / 10);
}
}
public static void main(String[] args) {
int n = 12345;
System.out.println("Somme des chiffres de " + n + " : " + sommeChiffres(n));
}
}Écrivez une méthode récursive pour vérifier si une chaîne de caractères est un palindrome.
public class Palindrome {
public static boolean estPalindrome(String str) {
if (str.length() <= 1) {
return true;
} else if (str.charAt(0) != str.charAt(str.length() - 1)) {
return false;
} else {
return estPalindrome(str.substring(1, str.length() - 1));
}
}
public static void main(String[] args) {
String mot = "radar";
System.out.println(mot + " est un palindrome ? " + estPalindrome(mot));
}
}Écrivez une méthode récursive pour calculer le n-ème nombre de la séquence de Fibonacci.
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
public static void main(String[] args) {
int n = 10;
System.out.println("Le " + n + "e nombre de Fibonacci est : " + fibonacci(n));
}
}Ces exercices vous donneront une bonne pratique pour comprendre et utiliser la récursivité en Java.
Voici quelques exercices avancés sur la récursivité en Java :
Écrivez une méthode récursive pour générer tous les sous-ensembles d’un ensemble donné.
Écrivez une méthode récursive pour trouver tous les chemins possibles d’un sommet de départ à un sommet d’arrivée dans un graphe.
Écrivez une méthode récursive pour calculer le coefficient binomial (ou combinaison) “n parmi k”.
Écrivez une méthode récursive pour résoudre le problème des tours de Hanoï, qui consiste à déplacer une pile de disques d’un piquet à un autre en suivant certaines règles.
Écrivez une méthode récursive pour trier une liste d’entiers en utilisant un algorithme de tri récursif, comme le tri rapide (quicksort) ou le tri fusion (merge sort).
Écrivez une méthode récursive pour générer toutes les combinaisons de parenthèses valides pour un nombre donné de paires de parenthèses.
Écrivez une méthode récursive pour rechercher un mot donné dans une grille de mots croisés.
Écrivez une méthode récursive pour trouver le plus court chemin d’un sommet de départ à un sommet d’arrivée dans un graphe pondéré.
Écrivez une méthode récursive pour générer tous les arbres binaires possibles avec un nombre donné de nœuds.
Écrivez une méthode récursive pour résoudre un puzzle Sudoku en remplissant les cases vides avec les chiffres de 1 à 9 de manière à ce que chaque ligne, chaque colonne et chaque région de 3×3 contienne tous les chiffres de 1 à 9.
Ces exercices avancés vous permettront de mettre en pratique des concepts de récursivité plus complexes et de développer vos compétences en résolution de problèmes.
Voici les solutions aux exercices avancés avec du code Java :
import java.util.*;
public class Subsets {
public static List<List<Integer>> generateSubsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
generate(nums, 0, new ArrayList<>(), subsets);
return subsets;
}
private static void generate(int[] nums, int index, List<Integer> current, List<List<Integer>> subsets) {
subsets.add(new ArrayList<>(current));
for (int i = index; i < nums.length; i++) {
current.add(nums[i]);
generate(nums, i + 1, current, subsets);
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> subsets = generateSubsets(nums);
for (List<Integer> subset : subsets) {
System.out.println(subset);
}
}
}import java.util.*;
public class AllPathsInGraph {
public static List<List<Integer>> allPaths(int[][] graph, int start, int end) {
List<List<Integer>> paths = new ArrayList<>();
List<Integer> currentPath = new ArrayList<>();
currentPath.add(start);
findPaths(graph, start, end, currentPath, paths);
return paths;
}
private static void findPaths(int[][] graph, int current, int end, List<Integer> currentPath, List<List<Integer>> paths) {
if (current == end) {
paths.add(new ArrayList<>(currentPath));
return;
}
for (int neighbor : graph[current]) {
currentPath.add(neighbor);
findPaths(graph, neighbor, end, currentPath, paths);
currentPath.remove(currentPath.size() - 1);
}
}
public static void main(String[] args) {
int[][] graph = {{1, 2}, {3}, {3}, {}};
int start = 0, end = 3;
List<List<Integer>> paths = allPaths(graph, start, end);
for (List<Integer> path : paths) {
System.out.println(path);
}
}
}public class Combination {
public static int calculateCombination(int n, int k) {
if (k == 0 || k == n) {
return 1;
} else {
return calculateCombination(n - 1, k - 1) + calculateCombination(n - 1, k);
}
}
public static void main(String[] args) {
int n = 5, k = 2;
System.out.println("Combinaison de " + n + " parmi " + k + " : " + calculateCombination(n, k));
}
}public class TowersOfHanoi {
public static void solveHanoi(int n, char source, char aux, char destination) {
if (n == 1) {
System.out.println("Déplacer le disque 1 de " + source + " à " + destination);
return;
}
solveHanoi(n - 1, source, destination, aux);
System.out.println("Déplacer le disque " + n + " de " + source + " à " + destination);
solveHanoi(n - 1, aux, source, destination);
}
public static void main(String[] args) {
int n = 3;
solveHanoi(n, 'A', 'B', 'C');
}
}import java.util.*;
public class RecursiveSorting {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {5, 3, 7, 2, 8, 1, 4};
System.out.println("Avant le tri : " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("Après le tri : " + Arrays.toString(arr));
}
}import java.util.*;
public class ValidParentheses {
public static List<String> generateValidParentheses(int n) {
List<String> result = new ArrayList<>();
generate(n, n, "", result);
return result;
}
private static void generate(int left, int right, String current, List<String> result) {
if (left == 0 && right == 0) {
result.add(current);
return;
}
if (left > 0) {
generate(left - 1, right, current + "(", result);
}
if (right > left) {
generate(left, right - 1, current + ")", result);
}
}
public static void main(String[] args) {
int n = 3;
List<String> validParentheses = generateValidParentheses(n);
for (String parentheses : validParentheses) {
System.out.println(parentheses);
}
}
}public class WordSearch {
public static boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (search(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private static boolean search(char[][] board, String word, int i, int j, int index) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
return false;
}
char temp = board[i][j];
board[i][j] = '#';
boolean found = search(board, word, i + 1, j, index + 1) ||
search(board, word, i - 1, j, index + 1) ||
search(board, word, i, j + 1, index + 1) ||
search(board, word, i, j - 1, index + 1);
board[i][j] = temp;
return found;
}
public static void main(String[] args) {
char[][] board = {
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'}
};
String word = "ABCCED";
System.out.println("Le mot existe dans la grille ? " + exist(board, word));
}
}import java.util.*;
public class ShortestPath {
public static int shortestPath(int[][] graph, int start, int end) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[graph.length];
int[] distance = new int[graph.length];
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
if (current == end) {
return distance[current];
}
for (int i = 0; i < graph[current].length; i++) {
if (graph[current][i] != 0 && !visited[i]) {
queue.add(i);
visited[i] = true;
distance[i] = distance[current] + graph[current][i];
}
}
}
return -1; // Pas de chemin trouvé
}
public static void main(String[] args) {
int[][] graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
int start = 0, end = 4;
System.out.println("Plus court chemin de " + start + " à " + end + " : " + shortestPath(graph, start, end));
}
}
Les écarts sur charges fixes permettent d'analyser les différences entre les charges fixes budgétées et…
L’écart-type est une mesure de la dispersion des données autour de la moyenne. Excel propose…
Exercice 1 : Calcul des Écarts sur Volume et Prix Contexte :Une entreprise a prévu…
1. Généralités sur le Contrôle Budgétaire Question 1 : Quel est l’objectif principal du contrôle…
Voici un QCM Contrôle de Gestion - Pilotage de la Performance bien conçu sur le…
Une fiche d’action est un outil essentiel pour planifier, suivre et gérer les tâches dans…
This website uses cookies.