Discussion :

[delma]

Hello à tous.

Je suis à la recherche d'un algorithme me permettant de répartir les quantités d'une ligne d'un tableau pour avoir finalement zéro dans chaque cellule (La somme de la ligne étant forcément égale à zéro).

Un exemple de ligne:
| 100 | 70 | -10 | -20 | -40 | -100 |

Je souhaite maintenant répartir mes quantités pour me trouver avec la ligne suivante:
| 0 | 0 | 0 | 0 | 0 | 0 |

Je prends par exemple 10 de la cellule 1 et les transfert à la cellule 3 pour mettre la cellule 3 à zéro.
mouvement 1:
10------>
| 90 | 70 | 0 | -20 | -40 | -100 |


Ceci en ayant impérativement le moi de transferts possible. Je pense que ce nombre (t) devrait être toujours soit:
t = n-1

ou

t = n-1-x

n le nombre de cellules
x le nombre de paire de cellules dont la valeur et la même mais de signe opposé. (ex 50 | -50) => x=1

J'espère être clair dans ma demande.

Merci d'avance et bonne journée!

[PRomu@ld]

x le nombre de paire de cellules dont la valeur et la même mais de signe opposé. (ex 50 | -50) => x=1

Non, si tu prends l'exemple qui suit :

| 50 | - 50 |

n = 2
x = 1

et donc t = n - x - 1 = 0. Ce qui voudrait dire que sans faire de transfert, tu as des zéros. La seule chose que tu peux savoir c'est que tu es en O(n).

Ensuite, tu peux toujours chercher des heuristiques pour qu'à un certain moment tu fasses apparaître des 0 plus rapidement (l'idée est simplement de chercher les couples qui donnerait un zéro)