Cherche désespérément formule/algorithme.

[tamik]

Bonjour tout le monde

Je cherche svp une formule/algorithme pour résoudre un cas et je ne sais pas où me tourner, quelqu'un pourrait-il m'aider (si ce n'est qu'en m'indiquant où chercher) ?

Voici ce cas :

Nous avons n valeurs valant initialement 0 : R1 R2 .. Rn = 0
Nous avons n-1 valeurs étant initialement >=0 (peuvent naturellement être différentes) : d1 d2 .. dn-1 >=0.

Il faudrait que j'annule tous ces di (i : 1 .. n-1) en employant la règle suivante :

Si je fais Ri = Ri + v (v>0, Ri sera toujours >=0) ; alors :

i=1 : di = di - v
1<i<n : di = di - v ; di-1 = di-1 - v
i=n : di-1 = di-1 - v


Merci, A+

dike
-----

[Resartus]

Bonjour,
On peut simplifier en supposant v=1.
Si les di ne sont pas entiers, on ne pourra pas les annuler, mais je suppose alors qu'on doit s'arrêter lorsque l'opération les ferait devenir négatifs... En prenant la partie entière des di, on peut se ramener au cas où les di sont tous entiers et où il faut les annuler tous.

Si vous êtes familiers avec les calculs matriciels, on peut traiter cela en considérant la matrice de transformation T suivante :
exemple avec n=6 (n-1=5)
1 1 0 0 0
0 1 1 0 0
0 0 1 1 0
0 0 0 1 1
0 0 0 0 1

Cette matrice multipliée par le vecteur R représentant l'état final des Ri, doit donner l'état initial des di (appelons-là D)
On a donc à résoudre D=T.R.
Il est toujours possible de trouver un R puisque T est une matrice diagonale supérieure (les valeurs propres sont toutes égales à 1). On peut l'inverser, et trouver R=T^(-1).D
A noter qu'on n'a pas besoin de Rn.

Mais (et c'est un gros MAIS) la solution ainsi trouvée risque de donner des valeurs négatives à certains Ri. Si ce n'est pas acceptable, il y aura des impossibilités (par exemple, si d2 vaut 2 et le reste 0)

[Cuv]

Salut,

Tu pourrais nous dire exactement ce que tu veux faire ? Je ne comprends pas à quoi te servent les Ri, nous ne savons pas non plus si ton "v" est une valeur constante.
Essaie de nous l'expliquer avec des mots parce que là je suis un peu perdu ^^

[Resartus]

Bonjour,
Ah oui en effet, v doit pouvoir avoir n'importe quelle valeur positive à chaque étape. Mais l'équation matricielle et sa résolution restent les mêmes

[A voir en vidéo sur Futura]

[tamik]

Bonjour et merci de vos réponses.

Je précise au sujet de v que ce sont là des valeurs qui peuvent changer ; j'aurais dû dire vi car on vient en greffer un (>=0) sur chaque Ri.

Ri -> Ri + vi ; ce qui modifie les di environnants. Le but est d'arriver à faire que tous les di valent 0.

Ri, di, vi : tout >=0

A+

[tamik]

Et, vu qu'au départ Ri = 0, alors Ri final vaut vi.

Une autre façon de formuler :

J'ai une série de valeurs >=0, que je nomme di (i : 1->n-1). Le problème est de trouver une autre série de valeurs, Ri >=0 (i : 1->n), telles que :

Ri + Ri+1 = di. Et surtout rien de négatif dans l'histoire merci.

C'est peut-être plus simple ainsi, dsl.

A+ j'espère

[tamik]

Oupss, j'oubliais de reformuler la première règle, que j'exprime de la sorte :

Une augmentation de x d'un Ri entraîne, en plus de la diminution de x de di, une pareille diminution de x de di-1.
Valable pour 1<i<n ; pour i=1 alors que le d1 diminue ; pour i=n alors que dn-1 diminue.

Je crois que j'ai enfin fait le tour.