[es] - Problem Farma - Pijaca (Inf.Olimpijada)

dzona065
Nikola Radovic

Član broj: 119864
Poruke: 31
*.teol.net.

+1 Profil

Problem Farma - Pijaca (Inf.Olimpijada)

^{29.03.2009. u 16:52 - pre 183 meseci}

Kvadratni prostor je podjeljen na N^2 kvadrata. Farma se nalazi u gornjem lijevom uglu kvadratnog prostora, a pijaca u doljem lijevom uglu kvadratnog prostora. Pero ide sa farme na pijacu prolazeci kroz svaki kvadrat samo jednom. Na primjeru je prikazan prostor za n=3. Napisati program koji ce izracunati koliko razlicitih ruta Pero ima od njive do pijace.

PRIMJER:

Code:

----------------
|    |    |    |
| F**********  |
|    |    | *  |
------------*---
|    |    | *  |
|  *****  | *  |
|  * | *  | *  |
---*---*----*---
|  * | *  | *  |
|  M | ******  |
|    |    |    |
----------------
N=3, a broj ruta je 2

Evo mog rjesenja:

Code:

#include <stdio.h>

int n;

void provjeri(int niz[100][100]){
    int i, j;
    int b=1;
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            if(!(i==n-1 && j==0))
                if(niz[i][j]!=1)
                    b=0;
        }
        //printf("%d  ", put[i][j]);
        //printf("\n");
    }
    if(b)
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                printf("%d  ", niz[i][j]);
        printf("\n");
}

void nadjiPut(int x, int y, int put[100][100]){
    int i, j;
    int pom[100][100];

    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            pom[i][j] = put[i][j];

/*
    for(i=0; i<n; i++){
        for(j=0; j<n; j++)
            printf("%d  ", pom[i][j]);
        printf("\n");
    }
*/
    //uslov da smo u okviru table, kao i da ovo nije krajnje polje
    //takodje provjeravamo da li je polje put[x][y] vec posjeceno
    if(x < n && x >= 0 && y < n && y <= 0 && pom[x][y]==0){
        if(x==(n-1) && y==0){
            provjeri(pom);
            //return;
        }
        else{
            //GORE
            pom[x][y]= (x-1)*n+y+1; //upisujem "adresu" sledeceg polja
            nadjiPut(x-1, y, pom);
            //DESNO
            pom[x][y]= x*n+(y+1)+1; //upisujem "adresu" sledeceg polja
            nadjiPut(x, y+1, pom);
            //LIJEVO
            pom[x][y]= x*n+(y-1)+1; //upisujem "adresu" sledeceg polja
            nadjiPut(x, y-1, pom);
            //DOLE
            pom[x][y]= (x+1)*n+y+1; //upisujem "adresu" sledeceg polja
            nadjiPut(x+1, y, pom);
        }
    }
    else{
        return;
    }
}

void main(){
    int i, j;
    int p[100][100];

    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            p[i][j]= 0;
    scanf("%d", &n);

    nadjiPut(0, 0, p);

}

problem mi je sto mi rekurzija ne prosledjuje dobro vrijednosti matrice pom odnosno put. Da li neko ima lijek za ovo :(

Apartmani na Jahorini http://www.apartmanimaja.com

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Problem Farma - Pijaca (Inf.Olimpijada)

^{14.04.2009. u 21:54 - pre 183 meseci}

Mnogo je bolje rešenje da imaš samo jednu matricu u celom algoritmu (umesto po jednu novu za svaki poziv funkcije). Prametar rekurzivne funkcije treba da bude referenca na tu matricu, a ne sama matrica. Kad rekurzivno pozivaš funkciju onda možeš

1. da promeniš sadržaj matrice, pozoveš funkciju, i vratiš sadržaj kakav je bio pre promene. Ili možeš
2. da pozoveš funkciju, na početku funkcije promeniš sadržaj (dodatni parametar funkcije mora da bude podatak kako se menja sadržaj), a na izlasku iz funkcije vratiš sadržaj na staro.

Meni se više sviđa prva opcija. Ako ovako napraviš stvar onda će izvršavanje biti brže, a memorija će se sporije trošiti. Ne gubiš apsolutno ništa. Jedina neugodnost je da matrica mora da postoji izvan same funkcije.

Uzgred, tvoj algoritam ima grešku upravo zato što ne vraća matricu na prethodno stanje kad završi s jednim rekurzivnim pozivom funkcije.

Odgovor na temu