Fonction récursive ?

[francois1955]

Bonsoir,

J'ai des difficultés de programmation sur le problème suivant (fonction récursive ?):

Soit H la fonction définie, pour r entier compris entre 0 et 200, par H(r) = Max [r ; g(r)] avec
g(r)=37/38*H(r-1) + 1/38*H(r+35)
Le but est de calculer H(r) pour toute valeur de r.

Le document que j'étudie me donne l’indication d’algorithme suivante :
Initialiser le tableau H0(r) en posant H0(r)=r pour tout r.
Balayer le tableau par itération en posant H i+1(r) = Max [ r ; 37/38*H i (r-1) + 1/38*H i (r+35) ]
On me dit que la suite H(i, r) converge très rapidement vers H(r).

Pour simplifier, je me contente ici d'un cas particulier, celui de H(50).
Le document me dit que H(50) vaut environ 53.6
Mais quand j'exécute mon programme, j'obtiens H(50)=50 car ma suite H(i,50) reste constante et égale à 50
Quelqu'un peut-il me dire où je fais erreur ?

Voici ce que j'ai fait en VBA pour Excel:

**************************
' Utilisation d'un tableau H(i , r)= Hi(r) où i est l'indice et r le relatif compris entre 0 et 200
Dim H(10000, 500)
' Initialisation du tableau H(0,r)
For r = 0 To 200
H(0, r) = r
Next r

' Recherche d'un cas particulier, la valeur H(50)
' Pour cela, on cherche la limite de H(i, 50)
' d teste le Max entre 50 et 37 / 38 * H(i, 49) + 1 / 38 * H(i, 85)

For i = 0 To 9998
d = 50 - 37 / 38 * H(i, 49) - 1 / 38 * H(i, 85)
If d >= 0 Then
H(i + 1, 50) = 50
Else
H(i + 1, 50) = 37 / 38 * H(i, 49) + 1 / 38 * H(i, 85)
End If
Next i

Cells(1, 1) = H(9998, 50)
****************************

Merci d'avance pour toute aide.

 

[ODVJ]

Bonjour,

Tel que tu décris ton exo, avec une initialisation H0(r) à r, g(r) sera égale à r-2/38.
Ton Hi(r) restera donc à r.

Cdlt

 

[francois1955]

Bonjour ODVJ,

Merci de ta réponse.
Oui, j'avais constaté que g(r) semblait toujours inférieur à r et que cela laissait ma suite H constante et égale à r.
Je n'avais pas fait le rapprochement avec r-2/38 (et je ne vois pas comment tu l'as fait).
J'en conclus que j'ai dû rater quelque chose dans l'énoncé de mon problème ou dans son interprétation.
Je retourne à mes études pour essayer de voir où j'ai dérapé.
Cdlt.

 

[ODVJ]

Re,

c'est simplement (37*(r-1)+(r+35))/38 qui donne r-2/38

cdlt

 

[francois1955]

c'est simplement (37*(r-1)+(r+35))/38 qui donne r-2/38

Ah oui quand on sait que .... Hi(r)=r
Merci

 

[francois1955]

Bon, je ne m'en sors pas...
Voici ci-joint le document qui me pose problème.
Je cherche à reconstituer le tableau des valeurs v(w) pour w compris entre -126 et 89.
Par exemple, je cherche à vérifier que v(50) vaut environ 53.6
Si quelqu'un voit comment ça peut se programmer, ça m'aiderait beaucoup.
Merci

 

[ODVJ]

Bonsoir,

Tu crées une colonne w (de -200 à +200 par exemple) puis la colonne V0(w) que tu initialises comme indiqué dans ton "document" à savoir w/2 si w<0 et w si w>=0.
Tu continues avec V1(w)=Max(V0(w);37*V0(w-1)/38 +V0(w+35)/38).
Pour V1, le calcul en -200 fait appel à V0(-201) qui est égal à -201/2 et à V0(-165) qui vaut -165/2.
Le calcul du max donne V0(-200).
De même pour les V0(i) pour i=166 à 200, on obtient V1(i)=V0(i).
Le "document" indique d'ailleurs que Vi+1(w)=Vi(w) pour w<-125.498 et w>88.638.

Tu n'as plus qu'à recopier la colonne V1 sur 10 000 colonnes et tu verras ton tableau de solutions apparaître, stabilisé à la 14 ou 15ème décimale.

Cordialement

 

[francois1955]

Bonjour ODVJ,
Merci infiniment pour ton aide et tes explications extrêmement claires et détaillées!
J'étais bloqué pour "amorcer la pompe", lancer la récurrence:

Pour V1, le calcul en -200 fait appel à V0(-201) qui est égal à -201/2 et à V0(-165) qui vaut -165/2.

Oui, ça, je me l'étais autorisé...

Le "document" indique d'ailleurs que Vi+1(w)=Vi(w) pour w<-125.498 et w>88.638.

Oui mais c'est la solution donnée. Cela me gênait davantage car c'est un peu "le serpent qui se mord la queue".

Tu n'as plus qu'à recopier la colonne V1 sur 10 000 colonnes et tu verras ton tableau de solutions apparaître...

Oui, c'est très visuel et impressionnant. Je ne soupçonnais pas que les valeurs évoluaient de la sorte.
Je pense même que j'ai abandonné du code à cause de valeurs insuffisantes parce que je ne voyais pas d'évolution vers la solution indiquée.

sur 10 000 colonnes et tu verras ton tableau de solutions apparaître stabilisé à la 14 ou 15ème décimale.

Ce n'est pas le cas chez moi pour l'instant.
Au stade i=10000, je ne suis pas encore aux valeurs attendues. Voici quelques exemples:
V10000(50)= 50.2635, loin encore des 53.6 attendus
V10000(0)=8.861, loin de 13.87 attendu
V10000(-50)= -23.8207, loin encore de 20.217 attendu
J'ai sans doute fait une erreur dans les formules. Je vais vérifier.
Même si j'ai beaucoup apprécié le travail dans la feuille Excel, je vais essayer de programmer le calcul pour voir si je m'approche davantage des résultats donnés dans le document.
Merci encore !

 

[ODVJ]

Bonjour,

jette un z'yeux sur le fichier.
Je n'ai pas mis les 10000 colonnes bien entendu.

cordialement

 

[francois1955]

Bonjour,
jette un z'yeux sur le fichier.

Que c'est beau !
Fantastique, j'ai le même tableau !
Arghh, à un détail près...en C4, par exemple, tu as =MAX(B4;(37*B3+B39)/38) alors que j'avais écrit =MAX(B4;(37*B3+B38)/38) !!

Merci beaucoup !!
Je vais essayer de le coder pour la suite de mon étude...

 

[francois1955]

Ci-dessous, le code qui me permet de retrouver les valeurs du tableau.
Merci beaucoup à ODVJ !

********************************
' Déclaration du tableau v(i , t) où t=w+200
Dim v(10000, 500)
' Initialisation du tableau v(0,t) pour tout t de 0 à 400

For t = 0 To 400
If t < 200 Then v(0, t) = 0.5 * (t - 200)
If t >= 200 Then v(0, t) = t - 200
Next t

'Sur les conseils d'OVDJ, initialisation d'autres valeurs:
'Vi(0)= -100 pour tout i
'Vi(t)=t pour tout i et tout t>=365
'v(1, 1) = -99.5

For i = 0 To 9999
v(i, 0) = -100
For t = 0 To 400
If t >= 365 Then v(i, t) = t - 200
Next t
Next i
v(1, 1) = -99.5

' calcul de v(i,t)
For i = 0 To 9999
For t = 1 To 400
d = v(i, t) - 37 / 38 * v(i, t - 1) - 1 / 38 * v(i, t + 35)
If d >= 0 Then
v(i + 1, t) = v(i, t)
Else
v(i + 1, t) = 37 / 38 * v(i, t - 1) + 1 / 38 * v(i, t + 35)
End If
Next t
Next i

'Affichage:
For t = 74 To 289 'For w=-126 to89
Cells(t - 72, 6) = t - 200
Cells(t - 72, 7) = v(9998, t)
Next t

 

[ODVJ]

Bonsoir,

comme l'affichage prenait un temps fou, j'ai mis :

'Affichage:
Dim affiche(216, 2)
For t = 74 To 289 'For w=-126 to89
    affiche(t - 74, 0) = t - 200
    affiche(t - 74, 1) = v(9998, t)
Next t
Cells(2, 6).Resize(UBound(affiche, 1), UBound(affiche, 2)) = affiche

D'autre part, tu peux remplacer

For t = 0 To 400
If t >= 365 Then v(i, t) = t - 200
Next t

par

For t = 365 To 400
    v(i, t) = t - 200
Next t

cordialement

 

[francois1955]

Bonjour,

comme l'affichage prenait un temps fou...

Je n'ai pas trouvé ici (mais nous n'avons pas forcément les mêmes critères)...
C'est peut-être parce que tu as travaillé dans ton fichier avec les 10000 colonnes ?
Quoi qu'il en soit et même si mon souci premier était les résultats, on ne peut qu'accueillir tout ce qui vise à améliorer.

For t = 0 To 400
If t >= 365

Oui, en effet... c'est ballot !

Dim affiche(216, 2) ..... Cells(2, 6).Resize(UBound(affiche, 1), UBound(affiche, 2)) = affiche

Ah, je ne savais pas qu'on pouvait économiser de cette façon.

Merci !

 

[ROGER2327]

Bonsoir francois1955, ODVJ.

Contribution annulée. Voir #17, #18 et #22.​

Simplifions :​

'Supprimé

Bonne soirée.​

ℝOGER2327
#8359

Mardi 10 Haha 144 (Saint Panmuphle, huissier - fête Suprême Quarte)
24 Vendémiaire An CCXXV, 8,2138h - amaryllis
2016-W41-6T19:42:48Z

 

[francois1955]

Bonsoir Roger,
Je suis très impressionné par le résultat mais pas en mesure malheureusement de comprendre le code pour l'instant.
Je reverrai ça quand je serai plus grand
Merci pour ton intérêt sur le sujet, ta participation et ton aide.