En panne d'algorithme pour trouver une somme dans un tableau [Résolu]

persolaser 33 Messages postés jeudi 7 juin 2007Date d'inscription 12 octobre 2014 Dernière intervention - 9 avril 2012 à 00:32 - Dernière réponse :  cs_ShayW
- 11 avril 2012 à 23:51
Bonjour à tous.

Je suis en panne de logique et appelle à l'aide vos lumières :
J'ai un tableau de n montants (les factures)
Je reçois un chèque d'un montant inconnu

Comment scanner le tableau de façon intelligente (et pas trop longue) pour repérer les membres dont la somme est égale au montant du chèque ???

ça a l'air tout simple, mais j'y ai déjà laissé deux crocs et une molaire. D'où mon appel à l'aide .

Merci par avance de votre aide.
Roland


Petit proverbe chinois : plus près de la lumière, tu es éclairé!
Afficher la suite 

Votre réponse

25 réponses

Meilleure réponse
NHenry 14273 Messages postés vendredi 14 mars 2003Date d'inscription 16 octobre 2018 Dernière intervention - 9 avril 2012 à 13:31
3
Merci
Bonjour,

UcFoutu, c'est pas totalement juste, car tu oublie les sommes de plus de 2 éléments.

Avec 6 possibilités, ça en fait (sauf erreur) 59 :
A
AB
ABC
ABCD
ABCDE
ABCDEF
ABCDF
ABCE
ABCEF
ABCF
ABD
ABDE
ABDEF
ABDF
ABE
ABF
AC
ACD
ACDE
ACDF
ACE
ACEF
ACF
AD
ADE
ADEF
ADF
AE
AEF
AF
B
BC
BCD
BCDE
BCDEF
BCDF
BCE
BCEF
BCF
BD
BDE
BDEF
BDF
BE
BF
C
CD
CDE
CDF
CE
CEF
CF
D
DE
DEF
DF
E
EF
F

Bien entendu, si la somme obtenue est supérieure à la somme recherchée, il faut abandonner.

---------------------------------------------------------------------
[list=ordered][*]Pour poser correctement une question et optimiser vos chances d'obtenir des réponses, pensez à lire le règlement CS, celui-ci pour bien poser votre question ou encore celui-ci pour les PFE et autres exercices[*]Quand vous postez un code, merci d'utiliser la coloration syntaxique (3ième icône en partant de la droite : )
[*]En VB.NET pensez à activer Option Explicit et Option Strict (propriété du projet) et à retirer l'import automatique de l'espace de nom Microsoft.VisualVasic (onglet Références dans les propriétés du projet).
[*]Si votre problème est résolu (et uniquement si c'est le cas), pensez à mettre "Réponse acceptée" sur le ou les messages qui vous ont aidés./list
---

Merci NHenry 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 96 internautes ce mois-ci

Commenter la réponse de NHenry
NHenry 14273 Messages postés vendredi 14 mars 2003Date d'inscription 16 octobre 2018 Dernière intervention - 9 avril 2012 à 00:54
0
Merci
Bonjour,

Je pense que mettre les montants avec un lien vers l'Id de la ligne dans un tableau (de structure par exemple) trié par montant.

Ensuite, tu fais une boucle récursive pour vérifier toutes les associations possibles :
Id Montant
1 10
2 15
3 30
4 40
5 50
10 100

Montant cherché : 115

Tu commence par le 1, puis tu fais les sommes à partir de la ligne 2
Une fois fait, tu passe à la ligne 2 et les somme à partir de la ligne 3
Etc.

Tu auras ensuite une liste de possibilité (ici 2+10 et 1+2+4+5) et tu auras à faire un choix.

Est-ce assez clair ?

---------------------------------------------------------------------
[list=ordered][*]Pour poser correctement une question et optimiser vos chances d'obtenir des réponses, pensez à lire le règlement CS, celui-ci pour bien poser votre question ou encore celui-ci pour les PFE et autres exercices[*]Quand vous postez un code, merci d'utiliser la coloration syntaxique (3ième icône en partant de la droite : )
[*]En VB.NET pensez à activer Option Explicit et Option Strict (propriété du projet) et à retirer l'import automatique de l'espace de nom Microsoft.VisualVasic (onglet Références dans les propriétés du projet).
[*]Si votre problème est résolu (et uniquement si c'est le cas), pensez à mettre "Réponse acceptée" sur le ou les messages qui vous ont aidés./list
---
Commenter la réponse de NHenry
LIBRE_MAX 1403 Messages postés mardi 1 mai 2007Date d'inscription 7 octobre 2012 Dernière intervention - 9 avril 2012 à 01:06
0
Merci
Bonsoir,

C' est nous qui avons besoin de tes lumières !!

[i]-tu reçois un chèque d'un montant inconnu
-tu veux repérer les membres dont la somme est égale au montant du chèque/i

Quoiqu' il en soit:

Commences par trier la colonne montant du tableau dans un ordre croissant.

Parcourres le en cumulant jusqu' à ce que..


[] Ce qui va sans dire. va mieux en le disant.
Commenter la réponse de LIBRE_MAX
LIBRE_MAX 1403 Messages postés mardi 1 mai 2007Date d'inscription 7 octobre 2012 Dernière intervention - 9 avril 2012 à 01:11
0
Merci
Bonsoir NHenry,

Désolé ! Posts croisés.
J' ai pas rafraichi avant de poster. [] Ce qui va sans dire. va mieux en le disant.
Commenter la réponse de LIBRE_MAX
persolaser 33 Messages postés jeudi 7 juin 2007Date d'inscription 12 octobre 2014 Dernière intervention - 9 avril 2012 à 02:26
0
Merci
Merci à vous deux. Au moins, je ne suis pas le seul à taffer.

OUI le montant de mon chèque est inconnu ... dans la liste puisqu'en fait il est la somme de plusieurs factures.
Je ne vois pas l'utilité de trier mes montants puisque le chèque peut être, par exemple, la somme du plus petit et du plus grand des montants.
De plus, la simple récursivité me fait un peu peur parcequ'il m'arrive d'avoir plusieurs dizaines de factures et je me dit que cela va faire beaucoup de boucle. Je cherchait plutôt des optimisation à apporter dans la récursivité.

Quelques idées ???
Commenter la réponse de persolaser
persolaser 33 Messages postés jeudi 7 juin 2007Date d'inscription 12 octobre 2014 Dernière intervention - 9 avril 2012 à 02:31
0
Merci
Par ailleurs, auriez-vous les qlq lignes d'une récursive qui donnerait, pour un tableau de N éléments, toutes les combinaisons possibles comportant de un à N éléments. (c'est quoi la formule de calcul du nombre de possibilité, dans ce cas là ?)

Merci par avance
Commenter la réponse de persolaser
Utilisateur anonyme - 9 avril 2012 à 03:51
0
Merci
Bonjour,

Par ailleurs, auriez-vous les qlq lignes d'une récursive qui donnerait, pour un tableau de N éléments, toutes les combinaisons possibles comportant de un à N éléments.

C'est dangereux d'utiliser la récursivité dans ce cas. La formule fait appel à des factorielles. Ce n'est pas trop long que l'on approche le dépassement de capacité

(c'est quoi la formule de calcul du nombre de possibilité, dans ce cas là ?)
Elles sont là les deux (pour les arrangements et pour les combinaisons)
Commenter la réponse de Utilisateur anonyme
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionContributeurStatut 11 avril 2018 Dernière intervention - 9 avril 2012 à 07:35
0
Merci
Bonjour,
1) La méthode la moins lente a été donnée d'entrée de jeu par NHenry.
2) j'ai dans le passé "remercié" un agent qui s'y était ainsi pris (non avec exactement le même but, mais pour rechercher et "corriger" une erreur comptable) et provoqué un méli-mélo quasi inextricable, deux mois plus tard !
Imagine donc le pire, persolaser : que le débiteur se trompe lui-même en libellant le montant du chèque et que (hé oui) le montant erroné corresponde comme par hasard à une somme de factures autres que celles qu'il veut acquitter ! Peu de chances, penses-tu ? Relis donc la 1ère phrase de mon 2) !


____________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches d'autres forumeurs.
Pas d'aide en ligne installée ? ==> ne comptez pas sur moi pour simplement vous dire ce qu'elle contient
Commenter la réponse de ucfoutu
persolaser 33 Messages postés jeudi 7 juin 2007Date d'inscription 12 octobre 2014 Dernière intervention - 9 avril 2012 à 09:33
0
Merci
Merci CMarcotte et UCFoutu.

La nuit portant conseil, je pense avoir avancé avec les points suivants :

D'une part, nombre de sommes possibles dans un tableau de N éléments :
Nous parlons de sommes qui peuvent contenir de 2 à N éléments, il s'agit donc de toutes les combinaisons où chaque membre de la liste est présent ou absent. Présent ou absent me permet de me rapprocher d'un système binaire et donc d'en déduire que le nombre de possibilité est égal à 2^N-1-N (moins un pour ne pas calculer zéro, moins N pour ne pas calculer de somme d'un seul élément). Merci de me corriger si je me trompe.
Par exemple, si je prends quatre factures de montant 1,2,4 et 8 (tout à fait au hazard ) je n'ai en tout et pour tout que 15 sommes possibles dont 10 à au moins deux éléments. Nous sommes loin de la factorielle de 4 (4!=24). Ici, l'ordre des éléments n'a aucune importance, seules leur présence ou leur absence est significative.

D'autre part, les optimisations :
Commençons par enfoncer une porte ouverte : inutile de conserver dans la liste les éléments supérieur à la valeur du chèque reçu. quelques opérations en moins.
Egalement, inutile de continuer à compiler une somme dès l'instant qu'elle dépasse le montant du chèque reçu

Je vais creuser ...

@UCFoutu :

1/ le but du jeu est d'imputer un règlement "si possible". Si le Client n'a pas juger utile de préciser quelles factures étaient concernées par son règlement, c'est son pb, pas le nôtre (nous parlons d'échanges commerciaux sans conséquence). Ce qui est important, c'est l'imputation des montants sur le compte du Client, pas la ou les pièces sur lesquelles il est imputé. Ce dernier aspect n'est en fait qu'une aide à la gestion de trésorerie, qui permet de savoir quelles factures doivent être relancées en l'absence de règlement. dans mon cas, le Client est identifié (le chèque) et les factures de la liste lui "appartiennent" toutes; donc pas d'erreur DE COMPTE d'imputation possible.

Tu n'as pas mentionné le cas possible de deux factures de mm montant; ceci m'amène au deuxième volet de ma réflexion sur ta réponse : ça n'est pas le débiteur qui choisit la facture qu'il règle, c'est l'ancienneté des factures qui prévaut. donc une imputation ne peut paraitre erronée que si le client est à jour de ses règlements. Mais s'il est à jour, l'imputation se fait sans problème. Qu'en penses-tu ?

à vous lire
Roland
Commenter la réponse de persolaser
persolaser 33 Messages postés jeudi 7 juin 2007Date d'inscription 12 octobre 2014 Dernière intervention - 9 avril 2012 à 09:42
0
Merci
@CMarcotte

Toutes mes excuses, j'avais pris le lien au pied de ta réponse pour une signature. Je viens de le consulter
Il ne s'agit pas d'arrangement puisque l'ordre nous est indifférent.
Il ne s'agit pas non plus de combinaisons puisqu'en fait il s'agit de la somme des combinaisons possibles parmi N éléments comportant de 2 à N éléments (donc la somme de N-1 combinaisons).

si je ne m'abuse ...
Commenter la réponse de persolaser
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionContributeurStatut 11 avril 2018 Dernière intervention - 9 avril 2012 à 10:42
0
Merci
Tu fais comme tu veux, mais :
Faire comme tu le vois, à savoir : 1) établir tous les arrangements puis 2) en extraire le sigma de leur composition est bien plus fastidieux que ce qui t'a été proposé par NHenry !
Exemple de 6 montants :
1) ta méthode === >> 63 arrangements à déterminer plus, pour chacun, le sigma de ses éléments !
2) méthode de NHenry : 16 totaux
Pour le reste (régler les plus anciennes ou autrement), c'est ton affaire de choix de tri



____________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches d'autres forumeurs.
Pas d'aide en ligne installée ? ==> ne comptez pas sur moi pour simplement vous dire ce qu'elle contient
Commenter la réponse de ucfoutu
persolaser 33 Messages postés jeudi 7 juin 2007Date d'inscription 12 octobre 2014 Dernière intervention - 9 avril 2012 à 11:55
0
Merci
@UCFoutu :

Je dois être un peu fatigué par cette longue nuit de pointage.
NHenry écrit "Ensuite, tu fais une boucle récursive pour vérifier toutes les associations possibles". hors, pour une liste à 6 éléments, qd je "fais une boucle récursive", j'obtiens 57 possibilités différentes unique (non ordonnées), pas 16 :
2 éléments : ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef
3 éléments : abc,abd,abe,abf,acd,ace,acf,ade,adf,aef,bcd,bce,bcf,bde,bdf,bef,cde,cdf,cef,def
4 éléments : abcd,abce,abcf,abde,abdf,abef,acde,acdf,acef,adef,bcde,bcdf,bcef,bdef,cdef
5 éléments : abcde,abcdf,abcef,abdef,acdef,bcdef
6 éléments : abcdef

Si je remplace chaque lettre par une puissance de deux, pour éviter les cas particuliers de sommes à mm résultat, soit a vaut 1, b vaut 2,...,f vaut 32, j'obtiens bien 57 résultats différents (2^6-1-6)

Bien sur, si je trouve la bonne somme avant la fin, je ne vais pas toutes les calculer; mais dans le pire des cas, il peut arriver d'avoir à calculer les 57.

ou alors, j'ai vraiment loupé un mammouth

Peux-tu stp m'expliquer comment tu descends à 16 totaux ?

Je suis preneur de ta solution
Commenter la réponse de persolaser
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionContributeurStatut 11 avril 2018 Dernière intervention - 9 avril 2012 à 13:02
0
Merci
Par exemple :
Me suis trompé : pas 16, mais 21 ===>>
Au depart : A,B,C,D,E,F === Classé par ordre croissant :
1) on part de A ===>> A , A+B, +C, +D, +E, +F ( = 6)
2) on passe à B et on regarde "en dessous" ====>> B, +C , +D,+E, +F (= 5)
3) on passe à C et on regarde "en dessous" ===>>> C, +D, + E, +F (=4)
4) on passe à D et on regarde "en dessous" ===>>> D, +E, +F (=3)
5) on passe à E et on regarde "en dessous" ===>>> E, E+F (=2)
6) il ne reste que F ===>> F (=1)

Il est bien clair que, pour chaque boucle "en dessous" : inutile de continuer si addition > que montant cherché.
____________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches d'autres forumeurs.
Pas d'aide en ligne installée ? ==> ne comptez pas sur moi pour simplement vous dire ce qu'elle contient
Commenter la réponse de ucfoutu
persolaser 33 Messages postés jeudi 7 juin 2007Date d'inscription 12 octobre 2014 Dernière intervention - 9 avril 2012 à 15:59
0
Merci
Nous sommes d'accord.
J'en trouve 4 de plus :
BEF
ABEF
CDEF
ACDEF
moins les 6 à un seul terme (ce que je n'appelle pas à proprement parler une "somme" ) et nous arrivons à 59+4-6= 57.

Merci à tous, nous arrivons au mm résultat
Si je ponds qlq chose de sympa, je le mets en ligne

à bientôt

Roland
Commenter la réponse de persolaser
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionContributeurStatut 11 avril 2018 Dernière intervention - 9 avril 2012 à 16:13
0
Merci
Ouais...
Autant pour moi ! Avec 6 éléments ===>>> 63 possibilités, en effet.
Voilà ce que j'ai fait (un peu bâclé) avec une listbox et un bouton de commande :

Private Sub Command1_Click()
 Dim choses
 choses = Array("A", "B", "C", "D", "E", "F")
 Dim nb As Integer, i As Integer, debut As Integer, fin As Integer, j As Integer, aa As String, bb As String, ps As Integer
 listbox1.Clear
 listbox1.Visible = False
 nb = UBound(choses) + 1
 For i = 1 To nb
     listbox1.AddItem i
 Next
 debut = 0
 fin = listbox1.ListCount - 1
 Do
   For i = debut To fin
     aa = Val(listbox1.List(i))
     If aa = 0 Then Exit Do
     bb = listbox1.List(i)
     ps = InStr(bb, "-")
     If ps Then
       listbox1.List(i) = choses(Val(bb) - 1) & Mid(bb, ps)
     Else
       listbox1.List(i) = choses(Val(bb) - 1)
     End If
     For j = aa + 1 To nb
       listbox1.AddItem j & "-" & listbox1.List(i)
     Next
   Next
   debut = fin + 1
   fin = listbox1.ListCount
 Loop
 listbox1.Visible = True
 MsgBox listbox1.ListCount & " possibilités"
End Sub

reste plus qu'à, pour chaque combinaisaon, calculer le total de ses éléments.
____________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches d'autres forumeurs.
Pas d'aide en ligne installée ? ==> ne comptez pas sur moi pour simplement vous dire ce qu'elle contient
Commenter la réponse de ucfoutu
Utilisateur anonyme - 9 avril 2012 à 17:04
0
Merci
Bonjour,

À repenser à tout cela, j'ai l'impression que tu te perds. En principe, si tu reçois un paiement d'un client, tu devrais avoir soit son numéro de client, soit un talon avec les factures payées. Quoi qu'il en soit, tu devrais pouvoir extraire au préalable les documents (chèque et factures ) de ce client-là. Cela te permettrait de réduire sensiblement le nombre d'opérations après.
Commenter la réponse de Utilisateur anonyme
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionContributeurStatut 11 avril 2018 Dernière intervention - 9 avril 2012 à 17:20
0
Merci
Bonjour, cmarcotte,
Mais même en ne traitant que les factures encore impayées de ce client, le risque demeure (relire ce que j'en ai dit plus haut).
Et ce risque peut avoir dans certains cas de sérieuses implications juridiques :
Au hasard :
- le client clientA a encore une trentaine de factures impayées
- voilà un mois qu'il refuse (pour une raison X ou Y) de régler le montant correspondant à une facture facturex. Il a même intenté une action en justice à ce propos.
- il envoie par contre un chèque de z euros en règlement de trois autres factures (F1, F2 et F3) à régler
- "manque de pot", le montant de ce chèque correspond pile poil à l'addition du montant de la facture contestée et du montant de l'une de ses autres factures, factureK
- Le comptable régularise sans sourciller les factures facturex et factureK
Imaginons maintenant que parmi les facture F1, F2 et F3 que le client voulait régler, en figure une à conséquences juridiques (prime d'assurance, taux différent de TVA, tranche d'avancement de travaux, etc ...) ===>>> bonjour les complications, hein !

____________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches d'autres forumeurs.
Pas d'aide en ligne installée ? ==> ne comptez pas sur moi pour simplement vous dire ce qu'elle contient
Commenter la réponse de ucfoutu
Utilisateur anonyme - 9 avril 2012 à 18:22
0
Merci
Bonjour,

Je ne suis pas Français et je ne me prononcerai pas sur le Droit français. Quoi qu'il en soit toutes ces recherches ont une faiblesse intrinsèque. Si ton programme prend une facture de 3 euros et une facture de 2 euros, au lieu de prendre La facture de 5 euros, tu ne seras pas plus avancé. Même chose, si ton client te paie 50 euros, au lieu de 60 euros, à cause d'un produit défectueux ou facturé en double.
Commenter la réponse de Utilisateur anonyme
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionContributeurStatut 11 avril 2018 Dernière intervention - 9 avril 2012 à 18:41
0
Merci
ou tout simplement que le client se trompe en faisant son total, ne serait-ce qu'avec les centimes
tout cela est on ne peut plus hasardeux, que de se rendre ainsi dépendant de plusieurs facteurs. Et rien n'est pire, en matière de comptabilité, que d'ajouter une erreur à une autre (c'est même le meilleur moyen d'aboutir à l'irréparable, dans certains cas de figure).


____________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches d'autres forumeurs.
Pas d'aide en ligne installée ? ==> ne comptez pas sur moi pour simplement vous dire ce qu'elle contient
Commenter la réponse de ucfoutu
LIBRE_MAX 1403 Messages postés mardi 1 mai 2007Date d'inscription 7 octobre 2012 Dernière intervention - 9 avril 2012 à 19:01
0
Merci
Bonjour,

D' après ce que je sais, les factures se payent par antériorités des soldes (les premières facturées , les premières payées).
Si le montant dn chèque dépasse la somme des 3 premières et inférieur à celle des 2 premières, les 2 premières sont règlées en totalité et la 3 ième partiellement.C' est le principe de la ventilation.
Cette méthode permet de faire marche-arrière en cas d'annulation du payement.



[] Ce qui va sans dire. va mieux en le disant.
Commenter la réponse de LIBRE_MAX

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.