Не е нужно да се регистрирате!
| Предишната тема :: Следващата тема |
| Автор |
Съобщение |
Apocalyp5e
Регистриран на: 29 Mar 2008
Мнения: 21
|
 Пуснато на: Mon Jan 05, 2009 11:36 pm Заглавие: Път между 2 града |
 |
|
| Код: | import java.util.Scanner;
/**
* Дадена e квадратна матрица n x n, където a[i][j] = 1, ако има
* директен път между градовете с номера i и j, a[i][j] = 0 ако няма
* директен път. Да се напише рекурсивна функция коята проверява дали
* съществува път между дадени два града.
*/
public class program {
public static void main(String[] args)
{ Scanner sc = new Scanner (System.in);
int [][] matrix = {
{-1, 0, 0, 0, 0, 0, 1},
{ 0,-1, 1, 0, 0, 1, 1},
{ 0, 1,-1, 0, 1, 0, 0},
{ 0, 0, 0,-1, 0, 0, 0},
{ 0, 0, 1, 0,-1, 0, 0},
{ 0, 1, 0, 0, 0,-1, 0},
{ 1, 1, 0, 0, 0, 0,-1}
};
System.out.print("Въведете номера на реда (от 1 до 7)." + '\n'+ "i=");
int i = sc.nextInt();
System.out.print("Въведете номера на стълба(от 1 до 7)." + '\n'+ "j=");
int j = sc.nextInt();
if(isPath(frame(matrix), i, -1, j))
System.out.println("Съществува път от i до j.");
else
System.out.println("Не съществува път от i до j.");
}
public static int[][] frame (int[][]a)
{
int n = a[0].length, m=a.length;
int[][] b = new int[n+2][m+2];
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
b[i][j]=a[i-1][j-1];
for(int i = 0; i <= n + 1; i++)
b[i][0] = b[i][m + 1] = 0;
for(int j = 1; j <= m+1; j++)
b[0][j] = b[n + 1][j] = 0;
return b;
}
public static boolean isPath (int[][] matrix, int from, int last, int to)
{
if(matrix[from][to] == 1) return true;
if( to != from && to != last)
{
if(to == 0 && from == 0)return false;
isPath(matrix, from, to, to--);
}
return false;
}
} |
Как да оправя метода isPath? |
|
| Върнете се в началото |
|
 |
Реклама
|
| Пуснато на: Заглавие: |
|
|
|
|
|
| Върнете се в началото |
|
|
Baronov
Регистриран на: 08 Sep 2008
Мнения: 29
|
| Пуснато на: Tue Jan 06, 2009 2:41 pm Заглавие: |
|
|
| Код: |
private static boolean visited[];
private static int[][] matrix;
private static void dfs(int i){
visited[i] = true;
for(int j = 0;j < matrix.length;j++){
if(matrix[i][j] == 1 && !visited[j])
dfs(j);
}
}
public static boolean isPath( int from, int to) {
visited = new boolean[matrix.length];
dfs(from);
return visited[to];
}
|
Направи си масива глобален. Трябва ти и масив visited, където ще отбелязваш посетените вече градове, за да си сигурен, че не посещаваш един град 2 пъти. По яко е така с 2 функции, защото няма смисъл да предаваш повече параметри, когато ти трябва само номера на града. |
|
| Върнете се в началото |
|
|
Apocalyp5e
Регистриран на: 29 Mar 2008
Мнения: 21
|
| Пуснато на: Tue Jan 06, 2009 4:24 pm Заглавие: |
|
|
Благодаря много за помощта  На това ли му викат "метод на вълничката"?
Последната промяна е направена от Apocalyp5e на Wed Jan 07, 2009 4:48 pm; мнението е било променяно общо 1 път |
|
| Върнете се в началото |
|
|
Baronov
Регистриран на: 08 Sep 2008
Мнения: 29
|
| Пуснато на: Tue Jan 06, 2009 8:06 pm Заглавие: |
|
|
| Не точно. Това е търсене в дълбочина или dfs. Метода на вълната е търсене в ширина или bfs. Написах ти dfs, защото то се реализира по-лесно, а и е тъкмо рекурсивно, както ти искаше. Иначе задачата може да се реши и по двата начина. Бонус на търсенето в ширина е, че ти дава най-краткия път по брой ребра. |
|
| Върнете се в началото |
|
|
|
|
Можете да пускате нови теми
Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
|
|
Правила(обновени на 11.05.2008)
Търсене
Потребители
Потребителски групи
Регистрирайте се
Профил
Влезте, за да видите съобщенията си
Вход
