Discussion :

[Spone]

Bonsoir à tous.

Une discussion avec un ami nous a amené sur un problème qui "semble" simple mais auquel on n'arrive pas a trouver une solution propre. Il est informaticien et je suis automaticien.

La solution doit exister et doit deja porter un nom savant. Peut etre que vous pourrez nous renseigner.

1) Nous avons une suite de N nombres aleatoires.
2) Nous avons un nombre x

Comment chercher dans cette liste tous les groupes de nombres dont la somme est egale à x

Il doit sans doute y avoir un moyen aussi de limiter le nombre de termes maximum que composent la somme.

Désolé si je m'exprime avec des mots mal adaptés, mais l'algo n'est pas mon domaine

[dourouc05]

C'est plutôt un problème classique d'interview technique . Ton problème correspond à la somme de sous-ensembles : https://fr.wikipedia.org/wiki/Probl%...sous-ensembles. Si tu utilises plus que deux nombres pour atteindre la valeur cible, tu risques d'avoir des problèmes de complexité algorithmique…

Les techniques pour résoudre ce problème sont souvent des variantes d'un algo bourrin (tester toutes les combinaisons). Tu peux trier ton tableau de valeurs ; pour chaque valeur du tableau, tu sais quelle autre nombre tu cherches pour obtenir le nombre cible, tu peux utiliser une recherche binaire pour retrouver cet autre nombre. Si tu as des propriétés spécifiques sur ton tableau, comme uniquement des entiers "pas trop grands", tu peux regarder du côté d'algorithmes de tri spécifiques, comme https://fr.wikipedia.org/wiki/Tri_par_d%C3%A9nombrement, qui te permet aussi de ne plus utiliser de recherche binaire.

[WhiteCrow]

Bonjour,

Une discussion avec un ami nous a amené sur un problème qui "semble" simple mais auquel on n'arrive pas a trouver une solution propre. Il est informaticien et je suis automaticien.

Nobody's perfect

La solution doit exister et doit deja porter un nom savant. Peut etre que vous pourrez nous renseigner.

1) Nous avons une suite de N nombres aleatoires.
2) Nous avons un nombre x

Comment chercher dans cette liste tous les groupes de nombres dont la somme est egale à x

En fait, comme bien souvent en algorithmique, ce n'est pas la solution qui porte un nom mais le problème. Il s'agit d'un problème d'arithmétique nommé SUBSET-SUM dans la littérature anglophone.

Il doit sans doute y avoir un moyen aussi de limiter le nombre de termes maximum que composent la somme.

Dans le problème général, non. Tu ne peux pas simplement trouver une limite simple au nombre de termes de la somme. Mais tu peux limiter ta recherche en fonction du nombre de termes. Par exemple, en utilisant un ensemble trié de nombres, tu peux trouver un somme de 1 terme en O(log n) en temps, 2 termes en O(n log n) et 3 termes en O(n²) ; dans un cadre plus général le problème est difficile à résoudre (NP-complet).

Il y aune étude assez complète de ce problème dans Introduction to algorithms (Cormen, Leiserson, Rivest & Stein) sections 34.5.5 et 35.5.

[Spone]

Merci pour vos réponses. Nous allons regarder ça