L'Atelier Monstre

La programmation dynamique offre des solutions efficaces pour résoudre des problèmes d'optimisation combinatoire. Un classique est de déterminer la plus longue sous-séquence strictement croissante (LIS) dans une suite donnée. Cette section explore plusieurs approches algorithmiques, de la méthode naïve en O(n²) à l'optimisation en O(n log n), a ...

Cet article explore les concepts fondamentaux des tableaux, en commençant par les tableaux unidimensionnels, leur déclaration, initialisation et manipulation. Il aborde ensuite les tableaux bidimensionnels, couvrant des sujets similaires. Des exemples de code et des explications sur leur stockage en mémoire sont fournis pour une meilleure compr ...

Optimisation des entraînements militaires Approche gloutonne : Trier les soldats par nombre d'entraînements nécessaires. Calculer le coût total actuel et comparer avec le coût groupé pour prendre la décision optimale à chaque étape. #include <iostream> #include <vector> #include <algorithm> struct Soldat { long long prix; ...

Tableaux Recherche binaire Étant donné un tableau trié en ordre croissant et une valeur cible, implémentez une fonction de recherche avec une complexité O(log n) retournant l'index de la cible ou -1. Deux approches selon la définition de l'intervalle : Intervalle [gauche, droite) : right = longueur du tableau Intervalle [gauche, droite] : ri ...

La programmation 0/1, ou programmation fractionnaire 0/1, est une classe de problèmes d'optimisation. Elle implique la sélection d'un sous-ensemble d'éléments, où chaque élément a deux attributs, disons \(a_i\) et \(b_i\). L'objectif est de maximiser (ou minimiser) le ratio \(\frac{\sum a_i \times d_i}{\sum b_i \times d_i}\), sous certaines con ...

Étant donné deux tableaux triés arrA et arrB de tailles respectives lenA et lenB, l'objectif est de déterminer leur médiane avec une complexité temporelle de O(log(lenA + lenB)). On suppose que les tableaux ne sont pas simultanément vides. Exemple : Entrée : arrA = [1, 3], arrB = [2] Sortie : La médiane est 2.0 Approches algorithmiques 1. Fusio ...

L'algorithme de recherche binaire standard peut retourner n'importe lequel des éléments correspondants lorsque plusieurs occurrences existent. Pour garantir le retour de la première occurence, une modification est nécessaire. En utilisant le tableau défini par int donnees[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };, l'implémentation suivante ajuste la log ...