Déterminer une relation de récurrence

[asse211]

Bonjour à tous,

Je fait face à un problème mathématique qui est le suivant :

Je doit réaliser un petit programme en python, permettant de trouver une valeur maximale en parcourant ou non certains emplacement dans une liste de taille "i".

Je fournirais le sujet précis par email à celui qui voudrais bien m'aiguiller, et pas me donner la solution ^^

Je dois trouver une relation de récurrence permettant de généraliser mon cas dans un algorithme récursif naïf, c'est à dire une petite fonction qui s'appel elle même "i" nombre de fois.

Je bloque complètement pour déterminer cette relation .... pouvez vous m'aiguillez ?

Merci par avance de votre aide,
Thibaut

[chadok]

Bonjour,
Une recherche Google en anglais donne souvent plus de résultats qu'une recherche en français
La recherche "find maximum using recursion" devrait t'aiguiller vers la solution :
https://www.google.com/search?client=ubuntu&channel=fs&q=find+maximum+using+recursion&ie=utf-8&oe=utf-8

[fatal_error]

hi,

peut etre uploade ton sujet quelquepart et mets le lien ici, ca pourra profiter à d'autres personnes

[asse211]

Merci pour votre temps,

En effet j'ai l'habitude de faire des recherches donc c'est la première chose que j'ai fait ne tkt pas sauf que ca ne répond pas à mon problème.

En ce qui concerne le problème, le voici :

https://i.postimg.cc/CMRrm26s/sujet.png

Il faut que je trouve une formule de récurrence pour mettre en place un algorithme de type récursif naïf.

Voici la question exact :

https://i.postimg.cc/3NZPY05Q/question.png

PS: Je précise que je ne veux pas la solution, mais dans un premier temps m'aiguiller

Merci encore de votre temps accordé.

[fatal_error]

slt,

la première chose qui parait débile, c'est que dans les emplacements ya que des valeurs positives. Donc en prenant une somme, on pourrait penser que forcément, le résultat est maximal si on pioche tout.

MAIS en fait on calcule pas la somme pure et dure, mais par exemple A*T[i] et si A est (entier) négatif, ca complique le problème, puisqu'il faut du coup, peut être ne _pas_ visiter un emplacement.

Concernant la question, t'as envie decrire un truc de type
V(i) = max(0, B*Ti) + X
avec max... selon qu'on visite la case d'indice i, et X la somme à prélever parmi les indices restants (i+1...n-1)
evidemment X ca ressemble pas mal à V(i+1), mais faut être précis parce que la première valeur prise dans X c'est pas forcément B*T(i+1) mais ca peut etre A*T(i)

la condition d'arret étant betement V(n-1) = max(0, B*T(n-1))

[asse211]

C'est pas évident du tout en effet ! Sachant que a ou B peuvent être négatif. Le fait que A et B soient négatif est exclu je pense, sinon l'exercice n'a plus d’intérêt .

Je pensais dissocier les deux cas dans la récurrence :

- Si A est négatif (donc B positif) : Trouver un maximum de symbole différent dans C[], sinon si x symboles sont égaux, prendre celui qui a le plus grand T[i]

- Si A est positif (donc B négatif) : Dès que 2 ou plus symboles dans C[] sont égaux, il faut les visiter. Sinon il faut sauter les emplacements.

Je pense qu'on aurait donc ces 2 cas dans la récurrence :

Initialisation : Quand "i = 0"

V0=B*T[0]

Hérédité :

Vi+1 = - Si A < 0 < B : .... + X
- Si A > 0 > B : ..... + X

Ce que je ne comprends pas c'est que trouver la somme maximum ne dépend pas juste de choisir la valeur la plus élevée à l'emplacement "i". Il faut choisir de visiter ou non certain emplacement en fonction de si A ou B est négatif ou positif.

C'est ce qui me bloque dans la récurrence.

Seconde chose, suite à cette relation de récurrence, je dois écrire un algorithme en python de type récursif naïf pour trouver la valeur maximal d'un parcours. Arrête moi si me trompe, mais un algorithme récursif naïf doit calculer tous les cas possibles afin de choisir le meilleur ... or comment peut-on calculer tous les cas sans revenir en arrière dans la récurrence avec à un moment donné un truc du genre "i - 1" ?

Merci encore pour ton aide

[fatal_error]

dans ton approche:
tu peux écrire recurANegBPos et recurAPosBNeg qui sont deux fonctions récurrentes qui n'ont strictement rien à voir. La valeur de A va pas changer pendant l'appel récursif.

à partir de là, concentrons nous sur un seul cas, eg: A>0, B<0

tu as écris:

Trouver un maximum de symbole différent dans C[], sinon si x symboles sont égaux, prendre celui qui a le plus grand T[i]

. Les symboles doivent être consécutifs.

l'idée est plutot de fait:
tu itères sur C (c_i, c_(i+1)) pour i=0...n-2
si c_i==c_(i+1), alors tu prélèves A*T(i+1)
sinon tu le prélèves pas et prends 0
evidemment tu n'as jamais prélevé le premier elem mais comme ca serait B*T0 tu en veux pas donc c'est bon.

Ta récursion peut s'écrire:

Code: Tout sélectionner

    recurAPosBNeg(i,n)
        if i==n-1
            retour
        if c_i==c(i+1)
            s += A*T(i+1)
        recurAPosBNeg(i+1, n)

    appel avec s (variable globale==0), recurAPosBNeg(0, n)


maintenant, ca répond que PARTIELLEMENT à ta question.

tu peux bidouiller ton algo pour écrire

Code: Tout sélectionner

    recurAAnyBNeg(i,n)
        if i==n-1
            retour 0

        if c_i==c(i+1)
            retourner max(0, A*T(i+1))  + recurAPosBNeg(i+1, n)
        retourner recurAPosBNeg(i+1, n)


c'est la meme chose sauf que tu ajoutes ton max qui gère le cas ou A pourrait être négatif
assez intuitivement, maintenant tu peux gérer le cas ou c_i !=c(i+1)

Code: Tout sélectionner

    recurAAnyBAny(i,n)
        if i==n-1
            retour 0

        if c_i==c(i+1)
            retourner max(0, A*T(i+1))  + recurAPosBNeg(i+1, n)
        if c_i!=c(i+1)
            retourner max(0, B*T(i+1))  + recurAPosBNeg(i+1, n)



sachant que cette fois, l'appel est
max(0, B*T(0)) + recurAAnyBAny(0,n)

Là, tu as quasiment exhibé ta formule si tu renommes recurAAnyBAny(i,n) en V(i)

[asse211]

evidemment tu n'as jamais prélevé le premier elem mais comme ca serait B*T0 tu en veux pas donc c'est bon.

Il est obligatoire de visiter la première valeur je suppose, comme on peut le voir dans l'exemple 2 :

https://i.postimg.cc/tCmSDw1d/Capture.png

Sinon nous n'avons aucun symbole à comparer pour l'emplacement "i=1"

Et c'est la que tout ce joue au final ... et que la complexité est énorme

Je pense que tu as oublié un détail dans le sujet, sans vouloir te contredire. Il faut qu'à chaque fois qu'un emplacement "i" est visité on stocke sont indice dans une liste "emplacementsVisités". Ce qui signifie qu'à chaque emplacement, on ne va pas vérifier si C[i] == C[i - 1], mais on va vérifier si C[i] == C[emplacementsVisités[-1]].

C'est pour cette raison qu'en fonction du parcours que l'on fait au début, la somme V[i] max changera considérablement si on ne fait pas les bons choix en fonction des symboles en "i + 2", "i + 3" etc ....

PS : emplacementsVisités[] est une liste, donc "emplacementsVisités[-1] "accède au dernier élément stocké dans cette liste, soit le dernier emplacement parcouru.

[fatal_error]

Il est obligatoire de visiter la première valeur je suppose, comme on peut le voir dans l'exemple 2 :

bon l'algo reste le même, tu prends pas max(0,BT(0)) mais BT(0) directement

Il faut qu'à chaque fois qu'un emplacement "i" est visité on stocke sont indice dans une liste "emplacementsVisités". Ce qui signifie qu'à chaque emplacement, on ne va pas vérifier si C[i] == C[i - 1], mais on va vérifier si C[i] == C[emplacementsVisités[-1]].

oui, après relecture j'ai mal compris l'énoncé.
prendre 0 c'est ne PAS visiter un element

je vois également ce que tu veux dire par "considérablement"
l'algo s'écrit de fait quasi pareil (toujours avec la récursion sur les i) avec l'adaptation de visiter...

Code: Tout sélectionner

recAAnyBAny(i,n,lastVisitedSymbole)
    if i==n-1
        retourner 0
    retourner max(
        recAAnyBAny(i+1,n, lastVisitedSymbole)# pas de visite
        si c_(i+1)==lastVisitedSymbole:
            A*T(i+1) + recAAnyBAny(i+1, n, lastVisitedSymbole)
        sinon
            B*T(i+1) + recAAnyBAny(i+1, n, C(i+1))

    )


[asse211]

Merci pour ton aide je vais me pencher dessus, je te tiens au courant quand j'ai adapté tout ça sur mon programme.

Encore merci, bonne fin d'aprem à toi

[fatal_error]

je pense quad même que ya un postulat qui est faux:

Il est obligatoire de visiter la première valeur je suppose

dans les exemples proposés, on prend toujours la première valeur parce qu'elle maximise (la somme)
si dans ex1 on prend pas 9, ca revient à calculer la somme totale sur T[7,8,7,10,7] et C=[1,1,4,4,2], dont la somme max est 5*8 - 2*7 + 5*7

jpense que les exemples c'est juste un hasard que on prend obligatoirement le premier

[asse211]

Effectivement c'est un pur hasard, mais si on ne met pas une valeur au premier indice, on va comparer dans le vide pour la suite du raisonnement ... non ?

Donc pour le cas ou (A pos / B neg) :

je trouve un algo de ce type : https://i.postimg.cc/YSNb6QXc/Capture.png

Mais il ne break pas comme il faut comme en témoigne la console ... je ne comprends pas trop comment je peut le faire break une fois que "i > 5" :

https://i.postimg.cc/gJFrWZd0/Capture.png

PS: "first" en console est un print("first") quand il rentre dans le "if i == len(c) - 1:"

Au final j'obtient V[i] = -1 pour l'exemple 2 du sujet.

Merci par avance de ton aide.

[fatal_error]

si possible essaie de mettre des bouts de
<code></code> (sauf que c'est [] et [/])
plutot que des images ca permet de faire des copier coller...

dans ton algo,
tu respectes pas l'énoncé parce que tu regardes c(i+1) et si ca vaut lastVisited, tu ajoutes T(i)...
or tu devrais ajouter T(i+1)

Code: Tout sélectionner

T = (9,7,8,7,10,7)
C = (2,1,1,4,4,2)
A = -2
B = 5
def V(i, n, last=-5):
    if i == n-1:
        return 0

    if C[i+1] == last:
        return max( V(i+1, n, last), A*T[i+1] + V(i+1, n, last) )
    return max( V(i+1, n, last), B*T[i+1] + V(i+1, n, C[i+1]) )

print(V(-1, 6))
T = (3,9,2,7,3,1)
C = (2,2,5,4,2,1)
A=2
B=-5
print(V(-1, 6))


output:

Code: Tout sélectionner

170
9



[asse211]

Ca y est j'ai enfin compris !! merci beaucoup

[asse211]

Je t'ai envoyé par MP un petit doute qui me turlupine ^^

Sinon encore merci pour ton aide !! Heureusement que des personnes comme vous consacre du temps à de banales inconnus sur des forum. Ça fait plaisir

[fatal_error]

hi,

si tu peux poser ta question ici, j'aime pas passer par mp (vu que ca profite partiellement qu'à une seule personne, et que personne d'autre peut éventuellement se rendre compte des boulettes)

ya pas de raison d'avoir peur d'écrire des conneries, j'en écris moi même beaucoup, en atteste ce fil XD

[asse211]

Slt,

En ce qui concerne la relation de récurrence je peux écrire ce genre de relation :

La formule de récurrence permettant de déterminer la somme maximale que l’on peut collecter entre les emplacements d’indice « i » et « n – 1 » est :

V[i]= { Si C[i+1] = lastVisited[-1] ∶ max⁡(V[i+1], B*T[i+1] + V[i+1])
-------Si C[i+1] != lastVisited[-1] ∶ max⁡(V[i+1], A*T[i+1] + V[i+1])}

Pour i tel que : n – 1 > i > 0
La condition d’arrêt équivaut à : n - 1 = len(T) - 1

Merci par avance

[fatal_error]

oui et non
hormis le fait que tu aies interverti A et B (A*T(i+1) si C(i+1)==lastVisited)

il faut faire gaffe à tes conditions d'arret:
tu dis n-1 > i > 0 mais la question te dis pour i==0 et i==n-1 inclus donc à gérer aussi

en particulier, si tu prends V(0) tu vois que (dans le code, on calcule V(0)(V au sens de la question) avec lappel de V(-1) (V au sens du code))
donc si tu te bases sur l'implem V du code, il faut que tu bidouilles avec les i+1
donc par ex:

V[i]= { Si C[i] = lastVisited[-1] ∶ max⁡(V[i+1], A*T[i] + V[i+1])
-------Si C[i] != lastVisited[-1] ∶ max⁡(V[i+1], B*T[i] + V[i+1])}

avec la def de V ci-dessus, on respecte pour i==0 et ainsi que pour i==n-1 SI tu imposes V(n)==0

donc qqch comme

V[i]= { Si C[i] = lastVisited[-1] ∶ max⁡(V[i+1], A*T[i] + V[i+1])
-------Si C[i] != lastVisited[-1] ∶ max⁡(V[i+1], B*T[i] + V[i+1])}
pour i==0 à n-1
V(i) = 0 sinon

personnellement je mettrais en argument de V lastVisited, mais bon, je sais pas trop quelle notation écrire..

[asse211]

En effet grosse erreur d'inattention de ma part !

Pour ce qui est de la condition d’arrêt je m'en suis aperçu hier soir tard en relisant ^^

Non je préfère garder le "V[i]", je trouve ça plus parlant.

Maintenant la question que je me suis posé une partie de l'aprèm' :

Il faut améliorer cette algo avec une version "top down". C'est à dire qu'il faut stocker les calculs V[i] pour un "i" précis, dans un tableau afin de ne pas re-calculer cette même valeur si on en a besoins à nouveau dans la récurrence.

Il s'avère que j'ai énormément galéré .... pour au final ne pas trouver de solution ...

Merci

[fatal_error]

hi,

je suis pas sûr que top down soit le bon nom. Normalement la dénomination est "mémoïsation"
l'idée est simple:
quand tu récurses: la suite T=5 5 5 6 7, (avec C aussi==5 5 5 6 7) tu peux choisir au premier 5 de le visiter
puis au deuxieme 5, de le prendre (ou pas)
ensuite dans les deux cas tu vas explorer la suite 5,6,7, (et dans les deux cas ton exploration est la même car le dernier symbole visité était 5)
Donc assez intuitivement, tu peux stocker la somme (maximale) associée à [i, lastVisited] et si jamais tu as un appel de fonction (i+1, lastVisited), tu as juste à regarder dans ton cache si tu l'as pas déjà calculé. Si oui, tu restitues, sinon, tu calcules et tu stockes

grossièrement:
def V(i, lastVisited):
si (i,lastVisited) in cache:
return cache(i,lastVisited)
sinon
si C(i)==lastVisited:
resultat = max(..)
sinon resultat = max(..)
cache(i,lastVisited) = resultat
retourner resultat
finV