再帰呼び出しと完全ナビゲーション
2749 ワード
質問です。
0から順に番号付けされるn個の要素のうち4個を選択した場合。
n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
//n:전체 원소 수
//picked :지금까지 고른 원소들의 번호
//toPick : 더 고를 원소의 수
// 일때 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다
void pick(int n, vector<int>& picked, int toPick){
//기저 사례 : 더 고를 원소가 없을때 고른 원소들을 출력한다.
if(toPick==0){printPicked(picked); return;}
//고를 수 있는 가장 작은 번호를 계산한다.
int smallest = picked.empty() ? 0 : picked.back() +1;
//이 단계에서 원소 하나를 고른다.
for(int next = smallest; next < n; ++next){
picked.push_back(next);
pick(n,picked,toPick-1);
picked.pop_back();
}
}
質問です。
5*5ハンドボールゲームのアルファベット単語を検索
보글 게임판에서 단어를 찾는 재귀호출 알고리즘
const int dx[8]= {-1,-1,-1,1,1,1,0,0};
const int dy[8]= {-1,0,1,-1,0,1,-1,1};
//5x5 보글 게임판의 해당 위치에서 주어진 단어가 시작하는지를 반환
bool hasWord(int y, iny x, const string& word){
//기저사례 1 : 시작위치가 범위 밖이면 무조건 실패
if(!inRange(y,x)) return false;
//기저 사례 2 : 첫글자가 일치하지 않으면 실패
if(board[y][x] != word[0]) return false;
//기저 사례 3: 단어 길이가 1이면 성공
if(word.size()==1) return true;
//인접한 8칸을 검사
for(int direction =0; direction < 8 ; ++direction){
int nextY = y+dy[direction], nextX = x+dx[direction];
//다음 칸이 범위 안에 있는지 첫글자는 일치하는지 확인할 필요 없음
if(hasWord(nextY,nextX,word.substr(1)))
return true;
}
return false;
}
이 알고리즘은 단어의 길이가 짧은 경우에만 완전탐색으로 해결할 수 있다.
단어가 긴 경우는 후에 다시 다루도록 하겠다.
質問です。
ハイキング問題
소풍 문제를 해결하는 재귀 호출 코드
int n;
bool areFriends[10][10];
//tackenp[i]= i 번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
//남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
int firstFree = -1;
for(int i=0; i< n;i++){
if(!taken[i]){
firstFree = i;
break;
}
}
//기저 사례 : 모든 학생이 짝을 찾았으면 한가지 방법을 찾았으니 종료
if(firstFree == -1) return 1;
int ret =0;
//이학생과 짝지을 학생을 결정한다.
for(int pairWith = firstFree+1; pairWith < n; ++pairWith){
if(!taken[pairWith] && areFriends[fisrtFree][pairWith]{
taken[firstFree] = taken[pairWith] = true;
ret += countPairings(taken);
taken[firstFree] = taken[pairWith] = false;
}
}
return ret;
}
/*
(0,1)과 (1,0)은 같다. 같은 방법을 중복으로 세지 않도록 주의하자.
-> 각 단계에서 남아있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 한다.
-> 가장 번호가 빠른 학생의 짝은 그보다 번호가 뒤일수밖에 없기에 방법이 중복될일이 없다.
*/
**プログラミングコンテストで学習したアルゴリズム問題解決策(9種類のみ).Reference
この問題について(再帰呼び出しと完全ナビゲーション), 我々は、より多くの情報をここで見つけました https://velog.io/@aelim0409/재귀호출과-완전탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol