Új hozzászólás Aktív témák

• Szmeby tag

  #9123

  #9121 #74220800

  2017-01-21 13:22:24

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  Szmeby

  tag

  #9121 #74220800

  #9121 #74220800

  Sziasztok!

  Egy rekurzív képlet kapcsán kérlek segítsetek.

  Röviden: Van egy 2D-s tömbből álló 5x5 mátrixom véletlen értékekkel. Minden mezőből indulva meg kell vizsgálni, hogy kisebb értékekkel rendelkező szomszédos elemek menten (föl, le, balra, le) el lehet-e jutni a mátrix széléig. Fontos, hogy rekurzív képlettel kell megoldani Egy irányba meg tudtam oldani. Most a 9. és 11. valamint 13. és a 16.sorok összeakadnak.

  Itt a drágám:

  public class water{

public static boolean flows(int row, int column, int arr [][]){

int x = arr[row][column];

if (row ==arr.length -1 || row == 0 || column == arr[row].length -1 || column == 0)
return true;
else if (flows(row-1,column, arr) && arr[row-1][column] < x)
return true;
else if (flows(row+1,column, arr) && arr[row+1][column] < x)
return true;
else if (flows(row,column-1, arr) && arr[row][column-1] < x)
return true;
else
return (flows(row,column+1, arr) && arr[row][column+1] < x);
}

public static void main(String[] args){

int arr[][] = new int [5][5];

for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr[i].length; j++){
System.out.print( (arr[i][j]= (int) (Math.random()*90)+10) + " ");
}
System.out.println();
}

System.out.println();

for(int i = 0; i <arr.length; i++){
for(int j = 0; j < arr[i].length; j++){
if (flows(i,j, arr))
System.out.print("-");
else
System.out.print("W");
}
System.out.println();
}


}

}

  Hali,

  mondjuk én első körben nem egyből egy random mátrixszal indítanék, hanem egy kicsit ellenőrzöttebb körülmények között tesztelném a cuccot. Pl. egy ilyennel:

  1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

  És akkor debug módban szépen lépkedve kiderítheted, hogy az a baj, hogy először mindig felfelé próbálkozol kijutni, majd ha nem megy, akkor lefelé. Csakhogy a próbálkozásod előtt nem csekkolod, hogy egyáltalán érdemes-e (<x). Mindenképp megpróbálod, így visszajutunk egy korábbi állapotba, ahonnan nem sikerült felfelé kijutni, így azt megpróbálni sem lenne érdemes, de ő csakazértis újra felfelé próbál. Nem tud, ezért megint lefelé indul el. A lefele ágban először újra felfelé indulna, és... gondolom érted, hogy ez a végtelenségig tart, ide-oda pingpongozik a két sor egymással.

  Egy ilyen térképpel például szépen működik a progi, mert mindig csak felfelé kell másznia:

  1 1 1 1 1
1 2 2 2 1
1 3 3 3 1
1 4 4 4 1
1 5 5 5 1

  Rekurzív hívásnál nagyon fontos a sorrend, amint tudod, terminálni kell a folyamatot. Érdemes először ellenőrizni, hogy a szomszédos szám valóban jó irány-e, és csak akkor ráhívni rekurzívan, ha tényleg van esély a kijutásra.

  ----
  Apró adalék, hogy egy kis emlékezet bevezetésével, drasztikusan gyorsítható a program. Ugyanis ha számon tartod (pl. egy kimeneti mátrixban), hogy adott cellából sikerült-e korábban kijutni, akkor nem kell újra és újra végigjátszani a teljes útvonal bejárást.

Új hozzászólás Aktív témák