[C++] Miglior cammino (semplice)

[Mesh89]

Salve a tutti.
Il problema è semplice: dobbiamo attraversare un castello 5x5 stanze, ed ogni stanza ha un certo costo di attraversamento. Si parte sempre da quella più sud. La versione è semplice e di prestazioni scarse, senza quindi utilizzare programmazione dinamica e altri artefici.

Codice:

 #include <iostream>

using namespace std;

#define INF 1000000

int n=5;
int castle[5][5]={{6,7,4,7,8},{7,6,1,1,4},{3,5,7,8,2},{2,6,7,0,2},{7,3,5,6,1}};


int min(int n1, int n2, int n3)
{
    int tmin=n1;
    if (tmin > n2)
        tmin = n2;
    if (tmin > n3)
        tmin = n3;
    
    return tmin;
}


int minCost(int x, int y)
{
    if (x < 0 || x >= n)
        return INF;
    else if (y == 0)
        return castle[x][y];
    else
        return min(minCost(x-1, y-1), minCost(x, y-1), minCost(x+1, y-1)) + castle[x][y];
}


int main()
{
    int x, y=4;
    
    cout << "x da cui partire (0-4): "; cin >> x;
    
    cout << minCost(x,y);
    system("PAUSE");    
}

Eppure il risultato è sempre sbagliato... Qualcuno mi sa dire perchè? Il codice è esattamente quello trovato su Wikipedia, alla seguente pagina
http://it.wikipedia.org/wiki/Programmazione_dinamica
e non è nulla di trascendentale... dove sbaglio?

[Luke31]

Potrei sbagliare o aver avuto una svista io, ho maggior dimestichezza con altri linguaggi piuttosto che il c, ma la variabile n non mi pare che fosse stata precedentemente dichiarata da nessuna parte, potrebbe essere quella la fonte dell'errore.

int minCost(int x, int y)
{
    if (x < 0 || x >= n)
        return INF;
    else if (y == 0)
        return castle[x][y];
    else
        return min(minCost(x-1, y-1), minCost(x, y-1), minCost(x+1, y-1)) + castle[x][y];
}

[oregon]

Come "da nessuna parte" ... ?

Hai scritto

int n=5;


La mia impressione, a prima vista, e' che non hai *sempre* considerato che i limiti per gli indici sono 0 ... 4 e non 1 ... 5 come nell'esempio ... dico *sempre* perche' a volte lo fai e a volte no ...

[Mesh89]

n è dichiarata in cima, come variabile globale al sorgente...

In che senso non uso sempe 0-4? Dove uso 1-5?

[oregon]

Non e' che usi 1-5 ... per capirci, tu fai riferimento a questo codice (il link che hai indicato)

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else    
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

e il tuo e' diventato

int minCost(int x, int y)
{
    if (x < 0 || x >= n)
        return INF;
    else if (y == 0)
        return castle[x][y];
    else
        return min(minCost(x-1, y-1), minCost(x, y-1), minCost(x+1, y-1)) + castle[x][y];
}

Ora, mentre la prima if e' diventata

minore di 0 e maggiore uguale a n (invece di 1 e n)

e la seconda if e' diventata

uguale a 0 (invece di 1)

tutti gli altri indici (nel return i e j, tu usi x e y ...) non sono stati modificati per tenere conto della questione 0...4 ...

... non so se mi sono spiegato ...

[Mesh89]

Beh, ma xkè cmq per il resto è indifferente...

In pratica secondo te cosa dovrei correggere?

[oregon]

No ... non e' indifferente ...

Se al posto di usare 1 nel confronti usi 0, allora invece di usare x devi usare x-1 e al posto di x-1 devi usare x-2 ... e cosi' per la y ... non so se mi spiego ...

[Mesh89]

Questo se continuassi ad usare il range 1-5 per la x! Ma il range va da 0 a 4...

Cmq è strano, gli utenti di un altro forum l'hanno provato e a loro funziona! Boh...