C++アルゴリズムの探索アルゴリズムのコード
1971 ワード
工程の過程のよく使ういくつかのコードの断片を一回バックアップして、下のコードのセグメントはC++アルゴリズムの道を探すアルゴリズムのコードについてです.
#define MAX_NUMBER_LENGTH 6
static int gPath[MAX_NUMBER_LENGTH][MAX_NUMBER_LENGTH] = { {0 , 0, 0, 0, 1, 1}, {1, 1, 0, 0, 1, 0}, {0 , 1, 1, 1, 1, 0}, {0 , 0, 1, 0, 1, 2}, {0 , 0, 1, 0, 1, 0}, {0 , 0, 1, 1, 1, 0} };
b)現在のノードが正当か否かを判断する判断関数を作成する
int check_pos_valid(int x, int y) { if(x < 0 || x>= MAX_NUMBER_LENGTH || y < 0 || y >= MAX_NUMBER_LENGTH) return 0;
}
c)次に,再帰的探索アルゴリズムを記述すればよい.
int find_path(int x, int y) { if(check_pos_valid(x,y)) { if(2 == gPath[x][y]){ gValue[x][y] = ‘#’; return 1; }
}
d)我々のアルゴリズムが正しいかどうかを検証するために、印刷関数を作成することができる.
void print_path() { int outer; int inner;
}
e)上記のcに記述されたアルゴリズムはただ1つの道を探しているだけで、もしすべての道を遍歴したいならば、アルゴリズムはどのように修正すればいいのでしょうか.
void find_path(int x, int y) { if(check_pos_valid(x,y)) { if(2 == gPath[x][y]){ gValue[x][y] = ‘#’; print_path(); gValue[x][y] = 0; return ; }
}
思考問題:上の問題は道を探す方法を紹介し、すべての可能な経路をどのように遍歴するかを紹介した.もちろん、このすべての検索経路から最も短い経路を見つけることができます.しかし、友达は考えてみることができて、1種の方法があって、一気に最も良い道を探すことができますか?
#define MAX_NUMBER_LENGTH 6
static int gPath[MAX_NUMBER_LENGTH][MAX_NUMBER_LENGTH] = { {0 , 0, 0, 0, 1, 1}, {1, 1, 0, 0, 1, 0}, {0 , 1, 1, 1, 1, 0}, {0 , 0, 1, 0, 1, 2}, {0 , 0, 1, 0, 1, 0}, {0 , 0, 1, 1, 1, 0} };
b)現在のノードが正当か否かを判断する判断関数を作成する
int check_pos_valid(int x, int y) { if(x < 0 || x>= MAX_NUMBER_LENGTH || y < 0 || y >= MAX_NUMBER_LENGTH) return 0;
if(0 == gPath[x][y])
return 0;
if('#' == gValue[x][y])
return 0;
return 1;
}
c)次に,再帰的探索アルゴリズムを記述すればよい.
int find_path(int x, int y) { if(check_pos_valid(x,y)) { if(2 == gPath[x][y]){ gValue[x][y] = ‘#’; return 1; }
gValue[x][y] = '#';
if(find_path(x, y-1))
return 1;
if(find_path(x-1, y))
return 1;
if(find_path(x, y+1))
return 1;
if(find_path(x+1, y))
return 1;
gValue[x][y] = 0;
return 0;
}
return 0;
}
d)我々のアルゴリズムが正しいかどうかを検証するために、印刷関数を作成することができる.
void print_path() { int outer; int inner;
for(outer = 0; outer < MAX_NUMBER_LENGTH; outer++){
for(inner = 0; inner < MAX_NUMBER_LENGTH; inner++){
printf("%c ", gValue[outer][inner]);
}
printf("n");
}
}
e)上記のcに記述されたアルゴリズムはただ1つの道を探しているだけで、もしすべての道を遍歴したいならば、アルゴリズムはどのように修正すればいいのでしょうか.
void find_path(int x, int y) { if(check_pos_valid(x,y)) { if(2 == gPath[x][y]){ gValue[x][y] = ‘#’; print_path(); gValue[x][y] = 0; return ; }
gValue[x][y] = '#';
find_path(x, y-1);
find_path(x-1, y);
find_path(x, y+1);
find_path(x+1, y);
gValue[x][y] = 0;
}
}
思考問題:上の問題は道を探す方法を紹介し、すべての可能な経路をどのように遍歴するかを紹介した.もちろん、このすべての検索経路から最も短い経路を見つけることができます.しかし、友达は考えてみることができて、1種の方法があって、一気に最も良い道を探すことができますか?